Date post: | 17-Oct-2015 |
Category: |
Documents |
Upload: | mario-riquelme-chavez |
View: | 34 times |
Download: | 0 times |
of 36
Complejidad Computacional
IIS366-1
Profesor: Patricio Galeas
2013 - Patricio Galeas
CAPTULO 7 : rboles Binarios
Introduccin Los rboles binarios son estructuras de
almacenamiento fundamentales para la programacin
Combina las ventajas de de un arreglo ordenado y de una lista enlazada: Bsqueda rpida Insercin y eliminacin rpida
rboles Binarios
Bsqueda Insercin Eliminacin
Arreglo Ordenado O(LogN) O(N) O(N) Lista Enlazada O(N) O(1) O(1) rbol Binario
qu es un rbol ? Un rbol consiste en la conexin de nodos (nodes) a travs de aristas (edges).
Los rboles son casos especiales de una estructura ms general llamada grafo, que revisaremos ms adelante.
Los nodos representan normalmente entidades (personas, autos, reservaciones, etc.)
Las aristas representan la forma en que los nodos estn relacionados.
rboles Binarios
rbol no-binario
nodo principal
arista
nodo
Las aristas son referencias y sirven para llegar de uno nodo a otro.
Hay normalmente un nodo principal en la parte superior del rbol, el cual se conecta a otros nodos del nivel siguiente.
Hay diferentes tipos de rboles: binarios y mltiples.
Terminologa Ruta: es el camino de un nodo a otro. Raz : nodo (nico) ubicado en la parte
superior del rbol. Existe slo un camino entre la raz y cualquier otro nodo.
Padre: es un nodo superior de otro nodo conectado por una arista.
Hijo : es un nodo inferior a otro nodo conectado por una arista.
Hoja : Es un nodo que no tiene hijos.
Sub-rbol : cualquier nodo puede considerarse como la raz de un sub-rbol.
Visitar : Un nodo es visitado cuando cuando el control del programa llega al nodo, para ejecutar una operacin. (slo asar por el nodo, no es visitar).
Atravesar : Atravesar significa visitar todos los nodos en un cierto orden.
Niveles : Es el nmero de generaciones desde la raz.
Clave (Key) : Es el valor de un nodo que permite buscar y ejecutar operaciones.
rboles Binarios
A
B
G D
C
E F
B es padre de D y E
raiz
Un sub-arbol con F como raiz
I J H
Nivel 0
Nivel 1
Nivel 2
Nivel 3
E es el hijo derecho de
B
ruta
D es el hijo izquierdo de
B
rboles Binarios
Cada nodo puede tener mximo dos nodos hijo (hijo izquierdo, hijo derecho).
En un rbol de Bsqueda Binario: el nodo padre es siempre mayor que su hijo de la izquierda y mayor o igual a su hijo de la derecha.
rboles Binarios
53
30
84 14
72
39 61
79 9 23 34 47
2013 - Patricio Galeas
rboles Binarios
applet
Applet - Arboles Binarios
2013 - Patricio Galeas
rboles Binarios
rboles Desbalanceados
53
30
14
72
39 61
9 23 34 47
Algunos rboles son generados en forma desbalanceada: tienen la mayor parte de sus nodos en un de los lados de la raz.
El desbalanceo se origina a travs del orden en que son insertados los elementos. Aleatorio : ms o menos balanceado. Ascendente : hacia la derecha. Descendente: hacia la izquierda.
Los rboles desbalanceados presentan algunos problemas de eficiencia
2013 - Patricio Galeas
rboles Binarios
Representando un rbol en Java
Existen varias alternativas para representar un rbol en la memoria del computador.
La ms comn es almacenar los nodos como posiciones independientes en memoria y luego conectarlas usando referencias.
2013 - Patricio Galeas
rboles Binarios
Representando un rbol en Java Primero necesitamos una clase para los Nodos. Node contiene los datos que representan los objetos
que estamos almacenando (empleados, repuestos, etc.)
Tambin incluye las referencia a sus dos nodos hijos.
Tambin necesitamos una clase para el rbol.
Tree contiene todos los nodos.
Tree contiene una sola variable, el nodo raz (root).
No necesita campos para otros nodos, ya que estos son accedidos a travs de la raz.
2013 - Patricio Galeas
rboles Binarios
Representando un rbol en Java Finalmente necesitamos
una clase para realizar operaciones sobre el rbol.
Esta rutina Main() Crea un rbol Inserta tres nodos Busca uno de ellos
Revisemos estas operaciones bsicas con el Applet
2013 - Patricio Galeas
rboles Binarios
Simulacin de un rbol
Busquemos un nodo ubicado en las hojas.
Cmo opera el algoritmo?
applet
2013 - Patricio Galeas
rboles Binarios
La variable current contiene el nodo actualmente examinado.
key es el valor buscado.
La rutina parte en el nodo root.
Compara key con current.iData key < current.iData : se va por la
izquierda
Key > current.iData : se va por la derecha.
Si no encuentra nada, retorna Null.
Encontrando un Nodo
2013 - Patricio Galeas
rboles Binarios
La idea es buscar el padre del nodo que queremos insertar, y luego conectarlo, segn su valor a su izquierda o derecha.
Parte creando un nuevo nodo con los datos de los argumentos.
Luego utiliza cdigo similar al de find(), para encontrar la posicin del nuevo nodo e insertarlo.
Se usa parent como referencia para hacer la conexin, ya que current queda en Null cuando se encuentra la posicin final del nuevo nodo.
Insertando un Nodo
2013 - Patricio Galeas
rboles Binarios
El recorrer (traversing) rboles significa visitar los nodos de un rbol en un orden determinado.
Esta operacin no es tan comn como: find(), insert() o delete() y adems es ms lenta.
Recorrer un rbol es tericamente interesante y muy til en algunas circunstancias.
Hay 3 formas de recorrer un rbol: Pre-Orden In-Orden Post-Orden
La forma ms comn en rboles binarios es In-Orden
Recorriendo el rbol
2013 - Patricio Galeas
rboles Binarios
In-Orden
Si es un rbol de bsqueda binario. los nodos son visitados en orden ascendente.
La manera ms fcil es recursivamente. La cual parte en el nodo raz.
El mtodo slo hace tres cosas: Se llama a si mismo para recorrer el sub-rbol
izquierdo. Visita el nodo. Se llama a si mismo para recorrer el sub-rbol
derecho.
Parte con el nodo raz, y se llama recursivamente hasta que no queden ms nodos por recorrer.
Revisemos Trav en el Applet
applet
Recorriendo el rbol
2013 - Patricio Galeas
rboles Binarios
Recorridos Pre- y Post-Orden
Este tipo de recorrido es til para analizar expresiones algebraicas.
Un rbol binario (no necesariamente de bsqueda) sirve para representar expresiones algebraicas.
Recorriendo el rbol en In-Orden generar la expresin en Infix correcta. Slo hay que agregar los parntesis.
Para Pre- y Post-orden se usan los mismo pasos que en In-Orden, slo la secuencia es diferente.
Para Pre-Orden: Visitar el nodo. Se llama a si mismo para recorrer el sub-rbol izquierdo. Se llama a si mismo para recorrer el sub-rbol derecho.
Para Post-Orden: Se llama a si mismo para recorrer el sub-rbol izquierdo. Se llama a si mismo para recorrer el sub-rbol derecho. Visitar el nodo.
*
A +
B C
Infix : A*(B+C) Prefix : *A+BC Postfix : ABC+*
Recorriendo el rbol
2013 - Patricio Galeas
rboles Binarios
Para encontrar el mnimo, se parte de la raz y se elige siempre el hijo izquierdo hasta el nodo que no tenga hijo izquierdo. Este ltimo nodo es el mnimo.
Para encontrar el mximo, el procedimiento es equivalente: current = current.rightChild;
El calculo del valor mnimo es parte del procedimiento necesario para eliminar un nodo.
Valores mximos y mnimos
63
47 71
67 22
11 33
53
50 60
17 49 51
mnimo
2013 - Patricio Galeas
rboles Binarios
Eliminar un nodo es la operacin ms compleja en rboles de bsqueda binarios.
Se parte buscando el nodo que se desea eliminar: find().
Una vez encontrado el nodo hay tres casos a considerar: El nodo a eliminar es una hoja. El nodo a eliminar tiene un hijo. El nodo al eliminar tiene dos hijos.
El primer caso es fcil, el segundo es relativamente fcil, pero el tercero es complejo.
Eliminando un nodo
63
47 71
67 22
11 33
53
50 60
17 49 51
2013 - Patricio Galeas
rboles Binarios
CASO 1 : El nodo a eliminar es una hoja
Una vez encontrado el nodo a eliminar, simplemente se cambia en el padre el valor del hijo a correspondiente a Null.
El nodo seguir existiendo, pero no ser ms parte del rbol. Y ser removido automticamente de la memoria (garbage collection).
Revisemos como funciona en el applet.
Eliminando un nodo
10
5
3 7
10
5
3 7
Null
antes despus
applet
2013 - Patricio Galeas
rboles Binarios
CASO 1 : El nodo a eliminar es una hoja
La primera parte del cdigo para eliminar es similar a find() e insert().
Eliminando un nodo
2013 - Patricio Galeas
rboles Binarios
CASO 1 : El nodo a eliminar es una hoja
Despus de encontrar al nodo
Hay que verificar el caso de que no tenga hijos.
Si no tiene hijos, se verifica el caso especial de la raz.
Eliminando un nodo
2013 - Patricio Galeas
rboles Binarios
CASO 2 : El nodo a eliminar tiene un hijo
Este caso tampoco es muy complicado
El nodo tiene slo dos conexiones: Una con su padre Una con su nico hijo
Luego se extrae al nodo conectando a su padre directo con su hijo.
Revisemos como funciona en el applet.
Eliminando un nodo
antes despus
80
52
48 71
63
67
a borrar
80
52
48 63
67
applet
2013 - Patricio Galeas
rboles Binarios
CASO 2 : El nodo a eliminar tiene un hijo
Esta situacin se maneja con 4 variaciones: El hijo del nodo a ser borrado
puede ser izquierdo o derecho El nodo a ser borrado, puede ser
hijo izquierdo o derecho de su padre.
Tambin incluye el caso especial en que el nodo a eliminar es el raz.
Gracias a las referencias, el mover un sub-rbol a otra posicin es relativamente simple.
Eliminando un nodo
2013 - Patricio Galeas
rboles Binarios
CASO 3 : El nodo a eliminar tiene dos hijos
Por que no simplemente reemplazar por uno de sus hijos?
Por ejemplo: reemplazar por el hijo derecho.
Que hacemos entonces con el nodo 30 ? no nos sirve el reemplazo !
Eliminando un nodo
La buena noticia: Existe un truco para
resolver el problema. La mala noticia:
Este truco involucra una serie de casos especiales.
2013 - Patricio Galeas
rboles Binarios
CASO 3 : El nodo a eliminar tiene dos hijos
TRUCO: Para eliminar a un nodo con dos hijos, reemplazar el nodo con su sucesor (in-orden).
Eliminando un nodo
Los nodos permanecen en orden.
El reemplazo es simple en el caso de que el sucesor no tenga hijos.
Cmo encontrar al sucesor algortmicamente?
2013 - Patricio Galeas
rboles Binarios
CASO 3 : El nodo a eliminar tiene dos hijos
Para encontrar el sucesor algortmicamente: Ir al nodo hijo derecho, y luego elegir siempre al nodo de la izquierda, hasta llegar al ltimo nodo de la izquierda, el cual es su sucesor.
En realidad, estamos buscando al menor de los nodos mayores que el nodo a eliminar.
Eliminando un nodo
long to see that the successor of 25 is 30. Theres just no other number that is greaterthan 25 and also smaller than 35. However, the computer cant do things at aglance; it needs an algorithm. Here it is:
First, the program goes to the original nodes right child, which must have a keylarger than the node. Then it goes to this right childs left child (if it has one), and tothis left childs left child, and so on, following down the path of left children. Thelast left child in this path is the successor of the original node, as shown in Figure8.17.
Deleting a Node 395
No leftchild
Successor
Go toleft child
Go toleft child
Go toright child
To find successorof this node
9260
9055
26
38
72
43
78
74
41
FIGURE 8.17 Finding the successor.
Why does this algorithm work? What were really looking for is the smallest of the setof nodes that are larger than the original node. When you go to the original nodes rightchild, all the nodes in the resulting subtree are greater than the original nodebecause this is how a binary search tree is defined. Now we want the smallest valuein this subtree. As we learned, you can find the minimum value in a subtree byfollowing the path down all the left children. Thus, this algorithm finds theminimum value that is greater than the original node; this is what we mean by itssuccessor.
If the right child of the original node has no left children, this right child is itself thesuccessor, as shown in Figure 8.18.
09 0672324539 CH08 10/10/02 9:14 AM Page 395
2013 - Patricio Galeas
rboles Binarios
CASO 3 : El nodo a eliminar tiene dos hijos
Si el sucesor es el hijo derecho del nodo a borrar. Es decir, el hijo derecho del nodo a borrar no tiene hijos izquierdos.
Entonces, habra que mover el sub-rbol donde el sucesor es raiz, a la posicin del nodo eliminado.
Esta operacin requiere 2 pasos: 1. Desconectar de su padre el nodo a
borrar (current), y apuntar esta conexin del padre directamente con el sucesor.
2. Desconectar el hijo izquierdo del nodo a borrar y conectar este hijo como hijo izquierdo del sucesor.
Eliminando un nodo
2013 - Patricio Galeas
rboles Binarios
CASO 3 : El nodo a eliminar tiene dos hijos
Si el sucesor es un descendiente izquierdo del hijo derecho del nodo a eliminar. Es decir, el hijo derecho del nodo a eliminar tiene hijos izquierdos.
Esta operacin requiere 4 pasos: 1. Conectar el hijo derecho del sucesor
como hijo izquierdo del padre del sucesor.
2. Conectar el hijo derecho del nodo a eliminar como el hijo derecho del sucesor.
3. Desconectar el nodo a eliminar de la posicin de hijo derecho de su padre y colocar al sucesor en su posicin.
4. Desconectar el hijo izquierdo del nodo a eliminar y conectarlo como hijo izquierdo de sucesor.
Eliminando un nodo
2013 - Patricio Galeas
rboles Binarios
Eliminando un nodo
No es trivial !
Algunos programadores simplemente agregan una variable booleana a la clase Nodo para definir si el no fuel eliminado.
Cul podra ser la desventaja?
2013 - Patricio Galeas
rboles Binarios
Eficiencia en rboles Binarios La mayora de las operaciones en rboles se relacionan
con descender el rbol de nivel en nivel hasta un nodo en particular.
En un rbol lleno la mitad de los nodos estn en el nivel inferior. Es decir la mitad de las operaciones se llevan a cabo en el nivel inferior y los dos cuartos de operaciones en los niveles siguientes.
Nmero de Nodos Nmero de Niveles
1 1
3 2
7 3
15 4
31 5
1.023 10
32.767 15
1.048.575 20
33.554.432 25
N = 2L 1N +1= 2LL = log2(N +1)
Es decir, el orden para ejecutar operaciones en un rbol binario es : O(logN)
2013 - Patricio Galeas
rboles Binarios
rboles representados como Arreglos No es muy
eficiente. Los nodos vacos o eliminados gastan memoria.
Pero si las eliminaciones no estn permitidas, puede ser una estructura a considerar.
2013 - Patricio Galeas
rboles Binarios
Valores duplicados Al igual que en otras estructuras, el manejo de valores
duplicados debe ser considerada.
Por ejemplo en el Applet, el ingreso de un nodo con un valor duplicado es insertado a la derecha de su gemelo.
find(), debe ser modificado para chequear tems adicionales.
Si quiero prohibir valores duplicados, debo modoficar el mtodo insert().
Los rboles son nodos conectados a travs de aristas.
El raz, es el nodo superior del rbol y no tiene padres.
En un rbol de bsqueda binario, todos los nodos que son descendientes izquierdos de un nodo A, tienen valor menores que A; y todos los nodos que son descendientes derechos de A tienen valores mayores que A.
Los rboles ejecutan bsquedas, inserciones y eliminaciones en tiempo O(log N).
Los nodos representan los objetos de informacin que estn almacenados en el rbol.
Las aristas son representadas comnmente en un programa como referencias a los hijos de un nodo ( y a veces a su padre).
Recorrer un rbol significa visitar todos los nodos en un orden determinado.
Los recorridos ms simples son: pre-orden, in-orden, y post-orden.
Un rbol desbalanceado es aquel donde la raz tiene tiene muchos mas descendientes al lado izquierdo que el derecho, o viceversa.
Buscar un nodo involucra comparar el valor buscado con los valores de cada nodo, yendo por su hijo izquierdo si el valor es menor y por el lado derecho si el valor es mayor.
Resumen rboles Binarios
La insercin involucra primero encontrar el lugar donde insertar el nuevo nodo, y luego cambiar sus referencias a los hijos.
En el recorrido in-orden los valores se visitan en orden ascendente.
Pre-Orden y Post-Orden son tiles para evaluar evaluar expresiones algebraicas.
Cuando un nodo no tiene hijos, este puede ser eliminado simplemente definiendo la conexin con su padre como Null.
Cuando un nodo tiene 1 hijo, puede ser eliminado conectando la referencia del hijo de su padre con su hijo.
Cuando un nodo tiene 2 hijos, reemplazando a este con su sucesor.
El sucesor de un nodo A puede ser encontrado buscando el mnimo nodo en el sub-rbol del hijo derecho de A.
En la eliminacin de un nodo con 2 hijos, afloran varias situaciones distintas, dependiendo si el sucesor es el hijo derecho del nodo a ser eliminado o uno de los descendientes de su hijo izquierdo.
Los rboles tambin pueden ser representados en la memoria del computador como arreglos.
Los nodos con valores duplicados pueden causar algunos problemas en arreglos, por que slo el primer elemento puede ser encontrado
Resumen rboles Binarios
Use el applet del rbol binario y cree 20 arboles . qu porcentaje de estos rboles es desbalanceado?
Cree un diagrama UML de las distintas posibilidades cuando se elimina un nodo en un rbol binario. Esto debe considerar los tres casos, con ambos hijos (derecho e izquierdo) y el caso especial de la eliminacin de la raz.
Utilice el applet para verificar el borrado de nodos en todas los casos posibles descritos.
Experimentos rboles Binarios