Unidad IV Estructuras no lineales

4.1 Arboles.
4.1.1 Concepto de árbol.
4.1.2 Clasificación de árboles.
4.1.3 Operaciones básicas sobre árboles
binarios.
4.1.4 Aplicaciones.
4.1.5 Arboles balanceados (AVL).
4.2 Grafos.
4.2.1 Terminología de grafos.
4.2.2 Operaciones básicas sobre grafos.


Pagina de Lectura
http://es.wikibooks.org/wiki/Estructuras_de_datos_din%C3%A1micas/%C3%81rboles#.C3.81rboles


Concepto de árbol.

Un árbol es una estructura de datos homogénea, dinámica y no lineal, en la que cada nodo (elemento) puede tener varios nodos posteriores, pero sólo puede tener un nodo anterior.



Un árbol es dinámico porque su estructura puede cambiar durante la ejecución de un programa. Y no lineal, ya que cada nodo del árbol puede contener varios nodos que dependan de él.

 La estructura de un árbol se forma de nodos y arcos (línea que une dos nodos), el primero de los nodos del árbol recibe el nombre de raíz, del cual se desprenden los nodos interiores y de éstos los nodos llamados hoja, que son los nodos que se encuentran al final del árbol; todos ellos en conjunto forman un árbol.

 Además de comprender el concepto y la estructura de un árbol, debemos tomar en cuenta otros conceptos básicos que pueden ser útiles en el momento de construir o programar un árbol, estos conceptos los clasificaremos en tres rubros:

 -               Relación con otros nodos,

-               Posición dentro del árbol y

-               Tamaño del árbol

 En relación con otros nodos:

-               Padre, es el nodo del cual se derivan otros nodos.

-               Hijo, es el nodo que depende de otro.

-              Hermano, es el nodo que se encuentra al lado del nodo hijo y que dependen del mismo nodo padre.

 En cuanto a la posición dentro del árbol:

-               Raíz, es el primero de los nodos y el único que no contiene un padre.

-               Hoja, es el nodo que se encuentra al final del árbol.

-               Interior, es un nodo que no es raíz ni hijo y se encuentre ellos.

 En relación a su tamaño:

 -              Orden, es el número potencial de nodos hijos que tiene un nodo padre (orden 2).

            -               Grado, es el número máximo de hijos que tiene un nodo (grado 2).

-              Nivel, es el número de arcos que deben ser recorridos para llegar a un determinado nodo más uno (nivel 3).

-              Altura, es el número de niveles que deben pasar para llegar al final del árbol o de la ramificación (altura 3).

            -               Peso, es el número de nodos del árbol sin contar la raíz (peso 6).

-              Camino, es la serie de nodos que tienes que pasar para llegar hasta un nodo.

-              Longitud de camino, es el número de arcos más uno que debe cruzar para llegar a un nodo.

            -               Rama, es el camino que se forma desde el nodo raíz hasta un nodo hoja.

 

Clasificación de árboles.

 Los árboles se clasifican de la siguiente manera:

-               Árboles binarios.

o                  Distintos

o                  Similares

o                  Equivalentes

o                  Equilibrado

o                  Completo


-               Árboles Multicaminos.

o                  B

o                  B+

o                  B*

o                  R

o                  2-4




Un árbol binario es una estructura de datos homogénea, dinámica y no lineal en donde a cada nodo le pueden seguir como máximo dos nodos hijos (que pueden estar vacíos), y cada hijo se designa ya sea como hijo izquierdo o como hijo derecho.

 Un árbol binario es distinto cuando su estructura es diferente a la de otros árboles binarios.


Un árbol binario es similar cuando su estructura es idéntica a la de otros árboles binarios, pero la información que guardan los nodos es diferente entre sí.


Un árbol binario es equivalente cuando su estructura e información de sus nodos es idéntica a la de otros árboles binarios.


Un árbol binario es equilibrado es aquel que todos sus nodos cumplen con la propiedad:

             altura (subárbol izquierdo) – altura (subárbol derecho) <= 1


Ejemplo. Si usamos los árboles anteriores para determinar si son o no equilibrados.

 El primero tiene una altura izquierda de 2 y derecha 1, 2-1 <= 1, la condición es verdadera, por lo tanto es un árbol equilibrado.

 El segundo tiene una altura izquierda de 2 y derecha 0, 2-0 <= 1, la condición es falsa, por lo tanto es un árbol no equilibrado.

 Un árbol binario es completo cuando todos sus nodos excepto los del último nivel, tienen dos hijos y todas las hojas están en el mismo nivel. Para calcular el número de nodos de un árbol completo se aplica la formula:

 

            Número de nodos = 2altura - 1


Ejemplo. La altura de este árbol anterior es 3, aplicando la fórmula del número de nodos seria.

             Número de nodos = 23 – 1 = 8 – 1 = 7

 Un árbol multicamino es una estructura de datos homogénea, dinámica y no lineal, en donde a cada nodo le pueden seguir una cantidad n de nodos hijos, y cada hijo se designa por el número de hijo que le corresponde.

 Operaciones Básicas sobre árboles binarios.

 Las operaciones que se pueden aplicar a un árbol binario son las siguientes:

 -               Creación de un árbol

-               Inserción de un nodo nuevo.

-               Eliminación de un nodo.

-               Recorrido del árbol.

-               Balanceo del árbol.

 Creación.

 Un árbol se forma de una serie de nodos y un nodo se integra de una serie de campos, para este caso, el nodo de un árbol binario debe estar integrado por los siguientes campos:

Dato

Der.

Izq.

Padre

 

-               Padre,

-               Dato,

-               Izquierda y

-               Derecha.

 

Donde los campos padre, izquierdo y derecho son los que permiten la relación con otros nodos dentro del árbol y el campo de dato es donde se almacena la información.

 

Otra estructura que puede tener un nodo para un árbol binario es contar con solo tres de los campos antes mencionados (dato, izquierdo y derecho), dicha estructura se representa de la siguiente manera:

               

Dato

Der.

Izq.

-         Dato,

-               Izquierda y

-               Derecha.

 

La única diferencia entre una estructura y la otra, es que en la primera se puede recorrer el árbol de arriba hacia abajo y de abajo hacia arriba; en la segunda  solo se puede recorrer de arriba hacia abajo.

 

Además debe tomar en cuenta que cada nodo es un objeto creado a partir de una clase auto-referenciada y dicha clase debe contener los campos antes mencionados.

 

Ejercicio. Construir una clase que permita crear objetos que se comporten como un nodo de un árbol.

 

public class NodoB

{

                        Object elemento;

                        NodoB padre, izquierdo, derecho;

                        //métodos

            }


Inserción.

 La operación de inserción permite agregar un nuevo nodo hoja al árbol, pero antes de agregarlo, debemos tomar en cuenta como se hace el acomodo u organización de los nodos dentro de la estructura del árbol. El primer nodo que entra en el árbol se le conoce como nodo raíz, del cual se desprendes los nodos intermedio y hojas.

 El segundo elemento que entra en el árbol, después del nodo raíz, tiene dos opciones para su inserción dentro de la estructura, el lado izquierdo o el lado derecho del árbol, para determinar por cuál lado debe entrar el segundo nodo tenemos que determinar el valor del campo dato del nuevo nodo, si el dato es menor que el nodo actual, el nuevo nodo se inserta por el lado izquierdo, o si el dato es mayor que el nodo actual, el nuevo nodo se inserta por el lado derecho. De esta forma la estructura del árbol organiza los nodos para un rápido acceso y búsqueda de un elemento.

 Algo más que debe contemplar después elegir el camino por donde se insertara el nuevo nodo, es, si existe un espacio libre para la inserción del nuevo nodo, es decir, si el nodo actual no contiene hojas, el nuevo nodo se puede insertar, en caso contrario debe continuar la búsqueda de un lugar disponible dentro del árbol.

 Ejemplo. Si tenemos un árbol con un nodo raíz con el dato 10 y queremos insertar seis nodos más con los datos 20, 5, 8, 1, 15 y 30 el árbol se estructuraría de la siguiente manera.




Ejercicio. Crear un árbol con los siguientes datos: H, G, A, M, R, O, Z, Y, Ñ, y L, tome en cuenta el ordenamiento de los nodos según lo visto anteriormente.

 Ejercicio. Crear un árbol con su nombre completo todo escrito en minúsculas, eliminando los espacios y los caracteres duplicados.

 Ejercicio. Crear un árbol, con las palabras de esté enunciado (en minúsculas).

 Después de conocer la forma de organización de los nodos en un árbol binario, debe contemplar que los árboles binarios no deben contener nodos duplicados. Por lo tanto, antes de insertar un nuevo nodo, debe revisar que el nodo no exista antes de su inserción, si el nodo ya existe, el nuevo nodo no se insertará.

 Los pasos para la insertar un nuevo nodo en un árbol binario son:

 

1.            Crear el nodo nuevo.

2.            Si el árbol se encuentra vacío, el nodo nuevo se asigna a la raíz.

3.            Si no se encuentra vacío, se revisa si el nodo nuevo existe, de ser así, el proceso termina.

4.            Si el nodo nuevo no existe, se busca el camino y el nodo del cual dependerá el nuevo nodo.

5.            Se determina si el nuevo nodo se inserta del lado izquierdo o derecho.

6.            Por último, se establecen las relaciones entre el nuevo nodo y el nodo que ahora será su padre.

 Recorridos en los árboles binarios

 Recorrer significa visitar  cada uno de los nodos de un árbol exactamente una sola vez, este proceso puede interpretarse como poner todos los nodos en una línea o linealizar el árbol.

Existen tres formas de efectuar el recorrido y todas son de manera recursiva:

a) Recorrido en preorden

·         Visitar la raíz

·         Recorrer el subárbol izquierdo

·         Recorrer el subárbol derecho

b) Recorrido en inorden

·         Recorrer el subárbol izquierdo

·         Visitar la raíz

·         Recorrer el subárbol derecho

c) Recorrido en postorden

·         Recorrer el subárbol izquierdo

·         Recorrer el subárbol derecho

·         Visitar la raíz

 

Funcionamiento de cada recorrido para el siguiente árbol binario paso por paso:




Preorden (15,8,4,10,20,17,35)

 

Paso

Nodo Actual

Nodo Visitado

Rama a visitar

Pila: rama pendiente de visitar

1

15

15

15.izq->8

15.der->20 (1)

2

8

8

8.izq->4

8.der->10  (2)

3

4

4

4.izq->null

4.der->null (3)

4

null

 

 

 

5

(3) null

 

 

 

6

(2) 10

10

10.izq->null

10.der->null (4)

7

null

 

 

 

8

(4) null

 

 

 

9

(1) 20

20

20.izq->17

20.der->35 (5)

10

17

17

17.izq->null

17.der->null (6)

11

null

 

 

 

12

(6) null

 

 

 

13

(5) 35

35

35.izq->null

35.der->null(7)

14

Null

 

 

 

15

(7) null

 

 

 


Inorden (4,8,10,15,17,20,35)

 

Paso

Nodo Actual

Nodo Visitado

Rama a visitar

Pila: rama pendiente de visitar

1

15

 

15.izq->8

15.der->20 (1)

15 (2)

2

8

 

8.izq->4

8.der->10 (3)

8 (4)

3

4

 

4.izq->null

4.der->null (5)

4 (6)

4

Null

4 (6)

 

 

5

(5) null

8 (4)

 

 

6

(3) 10

 

10.izq->null

10.der->null (7)

10 (8)

7

Null

10 (8)

 

 

8

(7) null

15 (2)

 

 

9

(1) 20

 

20.izq->17

20.der->35 (9)

20(10)

10

17

 

17.izq->null

17.der->null(11)

17 (12)

11

null

17 (12)

 

 

12

(11) null

20 (10)

 

 

13

(9) 35

 

35->izq-null

35.der->null (13)

35 (14)

14

null

35 (14)

 

 

15

(13) null

 

 

 


Postorden(4,10,8,17,35,20,15)

 

Paso

Nodo Actual

Nodo Visitado

Rama a visitar

Pila: rama pendiente de visitar

1

15

 

15.izq->8

15 (1)

15.der->20 (2)

2

8

 

8.izq->4

8 (3)

8.der->10 (4)

3

4

 

4.izq->null

4 (5)

4.der->null (6)

4

null

 

 

 

5

(6) null

4 (5)

 

 

6

(4) 10

 

10.izq->null

10 (7)

10.der->null (8)

7

null

 

 

 

8

(8) null

10 (7)

 

 

9

 

8 (3)

 

 

10

(2) 20

 

20.izq->17

20 (9)

20.der->35(10)

11

17

 

17.izq->null

17(11)

17.der->null(12)

12

null

 

 

 

13

(12) null

17 (11)

 

 

14

(10) 35

 

35.izq->null

35(13)

35.der->null (14)

15

null

 

 

 

16

(14) null

35 (13)

 

 

17

 

20 (9)

 

 

18

 

15 (1)

 

 


Eliminación.

La operación de eliminación de un nodo consiste en borrar el nodo del árbol binario de una forma definitiva, para este proceso la relación del nodo que se quiere eliminar con otros nodos debe desaparecer, pero que sucede con los nodos que dependen del nodo que se quiere eliminar. Para esto analizaremos los tres casos de eliminación en un árbol binario:

  1. Eliminación de una hoja,
  2. Eliminación de un padre con un hijo o subárbol y
  3. Eliminación de un padre con dos hijos o subárboles.

 La eliminación de una hoja, es simple, solo es necesario encontrar el padre y establecer en nulo la relación con el nodo hoja.

La eliminación de un padre con un hijo, también es simple, solo se requiere conocer quién es el nodo anterior al padre y establecer una relación con el nodo hijo y que el nodo hijo establezca la relación con el que será su nuevo padre.

La eliminación de un padre con dos hijos, no es tan simple como las anteriores ya que en este caso la eliminación del padre genera dos nodos hijos que posiblemente no se puedan relacionar con el nodo anterior al padre, ya que se puede romper la integridad del árbol binario y agregar tres hojas a un padre. Para solucionar este problema se encuentran dos posibles soluciones:

-       Eliminación por fusión y

-       Eliminación por copiado.

 La eliminación por fusión, genera un árbol nuevo de los dos subárboles que quedaron sin padre y el padre del nuevo árbol lo incorpora en el lugar donde está el nodo que se quiere eliminar.

Para fusionar dos subárboles, se debe realizar el siguiente proceso: Dentro del subárbol izquierdo encuentre el elemento mayor, que por la naturaleza de los árboles binario, es el que está más a la derecha del subárbol izquierdo y que no contiene hijo en su parte derecha o simplemente no contiene hijos, el nodo mayor encontrado se transforma en el nodo padre del subárbol derecho, estableciendo su campo derecha la relación con el padre del subárbol derecho. Con esto formaremos un solo árbol, el cual debemos fusionarlo al árbol original, en el lugar donde se elimino el nodo.

Ejemplo. Si queremos eliminar el nodo con el número 20 del siguiente árbol, el procedimiento sería el siguiente:


  1. Encontrar el nodo que se quiere eliminar y el anterior a él, para este caso son los nodos marcados con los números 20 y 10.
  1. Encontrar el nodo mayor del subárbol izquierdo, que para este caso sería el nodo con el número 15.
  2. Al campo derecho del nodo mayor asignarle el nodo padre del subárbol derecho, continuando con el ejemplo al nodo con el número 15 en su campo derecho asignarle el nodo con el número 30, que es el padre del subárbol derecho.
  3. Al nodo conocido como el anterior en su campo derecho asignarle el nodo padre del subárbol izquierdo, para terminar con este ejemplo al nodo con el número 10 en su campo derecho asignarle el nodo con el número 15.


Procesos de eliminación por Fusión.


Proceso para eliminar un nodo sin hijos o con 1 hijo:

·         Verificar que el árbol no está vacío

o   Verificar si existe el número a eliminar (Se obtiene el ant y exi)

o   Si existe se respalda el nodo existente (resp=exi)

§  Si el hijo derecho es null (no tiene hijo derecho tal vez solo hijo derecho)

·         Se pone a resp=resp.hijoi

§  Si el hijo izquierdo es null (no tiene hijo izquierdo tal vez solo hijo derecho)

·         Se pone a resp=resp.hijod

§  Se checa si el nodo a eliminar es la raíz (Si exi==raíz)

·         Si es así se pone a la raíz=resp

§  En  el caso que no sea la raíz se checa si está al lado izquierdo el nodo a eliminar (Si ant.hijoi==exi)

·         ant.hijoi=resp

·         Si está del lado derecho entonces ant.hijod=resp.

 

Proceso para eliminar un nodo que contiene ambos hijos

·         Verificar que el árbol no está vacío

·         Ver si el nodo a eliminar existe dentro del árbol ( Se obtiene el ant y el exi)

o   Si existe se respalda en no existente, resp=exi

o   Se busca el nodo mayor del subárbol izquierdo

§  El mas a la derecha del hijoi (No tendría hijos derechos)

§  Se le asigna al nodo encontrado en si hijo derecho la rama derecha del nodo a eliminar

§  Se reemplaza el nodo resp con el hijoi (resp=resp.hijoi)

§  Se checa si el nodo a eliminar es la raíz (Si exi==raíz)

·         Si es así se pone a la raíz=resp

§  En  el caso que no sea la raíz se checa si está al lado izquierdo el nodo a eliminar (Si ant.hijoi==exi)

·         ant.hijoi=resp

·         Si está del lado derecho entonces ant.hijod=resp.


La eliminación por copiado, se encarga de borrar el elemento del nodo que se quiere eliminar, cambiándolo por el elemento del nodo sucesor inmediato.

Debe recordar que cuando el nodo que se quiere eliminar tiene sus dos hijos, los hijos se transforman en padre o raíz de dos subárboles, izquierdo y derecho, y el sucesor de cada subárbol se encuentra de la siguiente manera: a la derecha el sucesor del subárbol izquierdo o a la izquierda el sucesor del subárbol derecho.

Para localizar el sucesor del nodo que se quiere eliminar, lo primero que se debe hacer es moverse un nodo a la izquierda del nodo que se quiere eliminar y avanzar a la derecha lo más que sea posible, almacenando el nodo anterior al sucesor en cada movimiento. Posteriormente el elemento del nodo sucesor remplaza el elemento del nodo que se quiere eliminar y el nodo izquierdo del sucesor se relaciona con el nodo anterior al  sucesor en su campo derecho.

 Ejemplo. Si queremos eliminar el nodo con el número 20 del siguiente árbol, el procedimiento sería el siguiente:

Encontrar el nodo que se quiere eliminar y en anterior a él, para este caso son los nodos marcados con los números 20 y 10.



  1. Marcar como el sucesor el nodo que apunta el campo izquierdo del nodo a eliminar y el campo que se quiere eliminar es el anterior al sucesor, para este caso el sucesor es el nodo con el número 15 y el anterior es el nodo con el número 20.
  2. Moverse lo más a la derecha posible marcando el nodo hacia donde se mueve como el sucesor y el anterior a él, al terminar esta búsqueda el  sucesor es el nodo con el número 18 y el anterior al sucesor es el nodo con el número 15.
  3. Cambiar el elemento del nodo que se quiere eliminar por el elemento que tiene el nodo sucesor, para este caso quitar el 20 y ponerle el número 18 en su lugar.
  4. Por último al nodo anterior en su campo derecho asignarlo como nulo si el sucesor no contiene un nodo en su parte izquierda.
  5. Si el sucesor contiene un nodo en su parte izquierda, el nodo anterior al sucesor en su campo derecho debe apuntar al nodo izquierdo del sucesor, que para este caso no se presento esa situación.

Proceso de eliminación por Copiado.

Proceso para eliminar un nodo sin hijos o con 1 hijo:

·         Verificar que el árbol no está vacío

o   Verificar si existe el número a eliminar (Se obtiene el ant y exi)

o   Si existe se respalda el nodo existente (resp=exi)

§  Si el hijo derecho es null (no tiene hijo derecho tal vez solo hijo derecho)

·         Se pone a resp=resp.hijoi

§  Si el hijo izquierdo es null (no tiene hijo izquierdo tal vez solo hijo derecho)

·         Se pone a resp=resp.hijod

§  Se checa si el nodo a eliminar es la raíz (Si exi==raíz)

·         Si es así se pone a la raíz=resp

§  En  el caso que no sea la raíz se checa si está al lado izquierdo el nodo a eliminar (Si ant.hijoi==exi)

·         ant.hijoi=resp

·         Si está del lado derecho entonces ant.hijod=resp.

 

Proceso para eliminar un nodo que contiene ambos hijos

·         Verificar que el árbol no está vacío

·         Ver si el nodo a eliminar existe dentro del árbol ( Se obtiene el ant y el exi)

o   Si existe se respalda en no existente, resp=exi

o   Se busca el nodo mayor del subárbol izquierdo

§  El más a la derecha del hijoi (No tendra hijos derechos, se respalda al sucesor y al anterior al sucesor).

§  Se reemplaza el dato del nodo a eliminar por el del nodo sucesor ( resp.dato=suc.dato)

§  Se verifica si el nodo resp es igual al anterior al sucesor (asuc.hijoi=suc.hijoi)

§  En caso de que resp no sea igual a al anterior al sucesor (asuc.hijod=suc.hijoi)

§  Se checa si el nodo a eliminar es la raíz (Si exi==raíz)

·         Si es así se pone a la raíz=resp

§  En  el caso que no sea la raíz se checa si está al lado izquierdo el nodo a eliminar (Si ant.hijoi==exi)

·         ant.hijoi=resp

·         Si está del lado derecho entonces ant.hijod=resp.


Balanceo.

Un árbol binario se encuentra balanceado si la diferencia en la altura de los dos subárboles de cualquier nodo en el árbol es cero o uno.

El árbol izquierdo se encuentra balanceado ya que la diferencia en la altura entre sus dos subárboles (izquierdo y derecho) es 1. En cambo el árbol de la derecha no se encuentra balanceado ya que la diferencia en la altura entre sus dos subárboles es 2.

Existen varias técnicas para balancear de manera adecuada un árbol binario, dichas técnicas se pueden clasificar en dos grupos:

-       Las que  balancean en el momento que un nuevo nodo ingresa en el árbol y

-       Las que utilizan el mismo árbol o una estructura adicional para balancear el árbol.

 

Las primeras técnicas reestructuran constantemente el árbol, cuando los elementos llegan y producen un árbol desbalanceado, lo cual requiere un pequeño retraso en la inserción de un nuevo nodo.

El segundo grupo de técnicas, realiza el balanceo en dos procesos, el primero, ordena los datos del árbol en forma ascendente (menor a mayor), ya sea en el mismo árbol o en otra estructura adicional (pila, cola o lista) y el segundo, construye un nuevo árbol con los datos ordenados, lo que garantiza que el árbol resultante se balancea.

Utilizando el segundo grupo de técnicas y en particular la que utiliza una estructura adicional (lista) para almacenar los elementos del árbol de forma ordenada, el balanceo de un árbol requiere de los siguientes procedimientos:


  1. Para transformar un árbol en una lista ordenada aplicando recursividad:

 

    1. El método debe recibir como argumento (el nodo raíz) en un nodo temporal.
    2. Si el nodo temporal es igual a nulo, el método se termina con la sentencia de retorno.
    3. Aplicar la recursividad mandando como argumento el nodo que se encuentra del lado izquierdo del nodo temporal.
    4. Almacenar en la lista el elemento del nodo temporal.
    5. Aplicar la recursividad mandando como argumento el nodo que se encuentra del lado derecho del nodo temporal.

Para crear el nuevo árbol a partir de la lista ordenada:
    1. El método debe recibir  como argumentos: la lista, la posición inicial y la posición final de la lista;
    2. Si la posición inicial es menor o igual a la posición final, se ejecutan los siguientes pasos, si no el método termina.
    3. Encontrar la mitad de la lista sumando la posición inicial y la final dividiéndola entre dos.
    4. Agregar al nuevo árbol el elemento que se encuentra en la nueva posición generada (la mitad).
    5. Aplicar la recursividad mandando como argumentos la lista, la posición inicial de la lista y la mitad menos una posición.
    6. Aplicar la recursividad mandando como argumentos la lista, la mitad mas una posición y la posición final de la lista.

Funcionamiento del balanceo


1)    Se extraen todos los elementos del árbol a una lista de manera ordenada

4

5

8

10

15

17

20

35

2)    Si la posición inicial es menor o igual que la posición final entonces se hacen los siguientes pasos:

a.    Se obtiene la posición inicial, la final, se suman y se dividen entre 2. (0+7)/2=3

b.    Asignar al árbol el elemento que se encontró en la mitad(3)

c.    Mandar de manera recursiva la mitad izquierda al mismo método enviando la lista y la posición inicial y la posición final

                                          i.    Lista,0,mitad-1= Lista,0,2

d.    Mandar de manera recursiva la mitad de la derecha al mismo método enviando la lista y la posición inicial y la final.

                                          i.    Lista,mitad+1,final= Lista,4,7

e.    Regresar al paso 2.


Ejecución llamado por llamado

No. Paso

Llamado

Índices

Insertar

Llamados recursivos pendiente)

1

(Lista,0,Lista.size()-1)

(0+7)/2=3

10 (raíz)

(Lista,4,Lista.size()-1)

2

(Lista,0,2)

(0+2)/2=1

5

(Lista,2,2)

3

(Lista,0,0)

(0+0)/2=0

4

Ya no se cumple la condición

4

(Lista,2,2)

(2+2)/2=2

8

Ya no se cumple la condición

5

(Lista,4,Lista.size()-1)

(4+7)/2=5

17

(Lista,6,7)

6

(Lista,4,4)

(4+4)/2=4

15

Ya no se cumple la condición

7

(Lista,6,7)

(6+7)/2=6

20

(Lista,7,7)

8

(Lista,7,7)

(7+7)/2=7

35

Ya no se cumple la condición

Árboles Binarios con la clase TreeSet.

 La clase TreeSet, permite crear una estructura de datos con nodos llamada árbol binario o árbol rojo-negro. El objeto creado a partir de la clase TreeSet es por lo tanto una estructura flexible que crece de forma dinámica. Está estructura se encuentra definida en la librería util.

Constructores de la clase TreeSet:

            TreeSet arbol=new TreeSet();

            TreeSet arbol=new TreeSet(Collection colección);

            TreeSet arbol=new TreeSet(Comparator colección comparada);

            TreeSet arbol=new TreeSet(SortedSet colección ordenada)

Todos los constructores crean un objeto llamado árbol. El primero lo crea vacío pero permite implementar comparable para su ordenamiento de los elementos. El segundo lo crea a partir de la colección de elementos recibida como argumento y ordenados de acuerdo al método compareTo, arroja ClassCastException si la colección de elementos no son comparables entre si y NullPointerException si la colección es nula. El tercero crea el árbol con una colección de elementos estableciendo un orden de comparación, ya sea compareTo o equals. Y el cuatro crea el árbol con la colección respetando el orden establecido en la colección de los elementos, genera NullPointerException si la colección ordenada está vacía.

Métodos de la clase TreeSet:

 

Método

Función del método y sintaxis.

add()

Inserta un elemento en el árbol, si no existe en él, genera ClassCastException si no se puede comparar con los elementos que ya están en el árbol.

var_boolean=arbol.add(Object elemento);

addAll()

Inserta la colección de elementos pasados como argumento, genera ClassCastException si los elementos de la colección no son compatibles con los del árbol y NullPointerException si la colección es nula.

var_boolean=arbol.addFirst(Collection colección);

clear()

Elimina todos los elementos del árbol.

arbol.clear();

clone()

Regresa una copia de la lista.

arbol_destino=arbol.clone();

comparator()

Regresa el comparador usado para ordenar los elementos en el árbol o null si el método compareTo se define para el árbol.

var_String=arbol.comparator();

contains()

Retorna un valor boleano si el elemento se encuentra en el árbol (true si esta y false si no), genera ClassCastException si el elemento no se puede comparar con el contenido del árbol.

var_boolean=arbol.contains(Object elemento);

first()

Retorna el elemento más pequeño del árbol, o genera la excepción NoSuchElementException si el árbol está vacío.

var_Object=arbol.first();

headSet()

Retorna el subconjunto con los elementos que preceden al elemento recibido como argumento, genera la excepción  NullPointerException si el elemento es nulo, o genera la excepción ClassCastException si el elemento no se puede comparar con el método compareTo, o genera la excepción IllegalArgumentException si el elemento no está dentro del árbol.

var_SortedSet=arbol.headSet(Object elemento);

isEmpty()

Retorna true si el árbol está vacío o false si no lo está.

var_boolean=arbol.isEmpty();

iterator()

Genera y regresa una iteración del árbol completo.

var_Iterator=arbol.iterator();

last()

Retorna el elemento mayor del árbol, o genera la excepción NoSuchElementException si el árbol está vacío.

var_Object=arbol.last();

remove()

Elimina el elemento pasado como argumento del árbol y regresa true, o genera la excepción ClassCastException si no puede comparar el elemento.

var_boolean=arbol.remove(Object elemento);

size()

Retorna el número de elementos en el árbol.

var_int=arbol.size();

subSet()

Regresa el subconjunto de elementos del árbol (no una copia) que se encuentran entre el primero y el último de los elementos pasados como argumentos, incluyendo el primero, basándose en el método compareTo, genera la excepción NullPointerException si el primero y el último son nulos; genera ClassCastException si el primero y el último no se pueden comparar; genera IllegalArgumentException si el primero precede al último.

var_sortedSet=arbol.subSet(Object primero, Object último);

tailSet()

Regresa el subconjunto de elementos del árbol que son iguales o exceden al elemento pasado como argumento; genera NullPointerException si el elemento es nulo; genera ClassCastException si el elemento no se puede comparar; genera IllegalArgumentException si el elemento no está en el árbol.

var_sortedSet=arbol.tailSet(Object elemento);

toArray()

Copia todos los elementos del árbol a un arreglo.

arr_Object=arbol.toArray();

Comments