View
436
Download
0
Category
Preview:
Citation preview
Árboles AA
Estudiantes:
Mariela Barrantes Mata
Jorge Calderón Díaz
Samuel Yoo
Gabriel Pizarro Picado
¿Qué son los árboles AA?
Es un tipo de árbol binario de búsqueda auto-
balanceable, es decir, intenta mantener su altura
o su número de nodos bajo la raíz, tan pequeña
como sea posible en todo momento,
automáticamente.
Estos son una variación del árbol rojo-negro y
una mejora del árbol binario de búsqueda.
Se debe cumplir el estricto requisito de que solo los enlaces derechos pueden ser rojos y a diferencia de los árboles rojo-negro, estos se implementan con la idea de nivel y no de color.
Para mantener el equilibrio de este se necesitan dos operaciones llamadas torsión (skew) y división (split).
Algunas funciones
Sirven para almacenar y recuperar
información ordenada de manera eficiente.
En el ámbito computacional se utiliza para
organizar información compuesta por datos
comparables.
Características importantes
Las condiciones para que el árbol sea válido son las siguientes: 1. El nivel de un hijo izquierdo debe ser menor que el nivel
de su padre.
2. El nivel de un hijo derecho debe ser menor o igual al nivel de su padre.
3. El nivel de un nieto derecho debe ser menor que el nivel de su abuelo.
4. El nivel de un nodo hoja es 1.
5. Cada nodo de nivel superior a uno debe tener dos hijos.
Los nodos tienen nivel y no color.
Algoritmos de
Balanceo
Algoritmos de Balanceo
El árbol AA es una variación de árbol rojo-negro,
que a su vez es una mejora de árbol binario de
búsqueda. A diferencia de los arboles rojo-negro,
los nodos rojos en un árbol AA solo pueden
añadirse como un hijo derecho.
En un árbol AA, al cumplirse el requisito de un
solo los enlaces derechos pueden ser rojos, solo
es necesario considerar dos formas de balanceo:
Torsión (Skew)
La torsión es una rotación derecha que se
realiza cuando una inserción o un borrado
genera un enlace horizontal izquierdo, puede
pensarse como un enlace rojo izquierdo en el
contexto del árbol rojo-negro.
División (Split)
La división es una rotación izquierda condicional que tiene lugar cuando una inserción o un borrado crea dos enlaces horizontales derechos, lo que de nuevo se corresponde con dos enlaces rojos consecutivos en el contexto de los árboles rojo-negro
Ejemplo
Balanceo al agregar un número
Primero se agrega a la raíz un nodo.
En este ejemplo será 70.
Después se inserta el 50.
Como el 50 es menor a 70 entonces se mueve a la izquierda del 70.
Sin embargo, como en los arboles AA se balancea hacia la derecha entonces aquí se da un skew (torsión).
Quedaría de la siguiente manera:
Ahora se inserta el 80.
Como el 80 es mayor que 50 y 70, entonces se va a
colocar en la parte derecha del nodo 70.
Sin embargo, como el pseudópodo (nodo de igual
rango) es muy grande, se hace una división en 50,
donde el 50 baja y queda a la izquierda del 70.
Quedaría de la siguiente manera:
Búsqueda
Búsqueda
Para hacer la búsqueda con arboles AA, se puede hacer de la siguiente manera: primero, se empieza con la raíz.
Si la raíz es igual al número que se busca, entonces retorna verdadero.
Si no es igual, entonces compara si el número es mayor o menor a la raíz.
Si es menor, entonces va hacia el nodo hijo izquierdo.
Si es mayor a la raíz entonces va hacia el nodo hijo derecho. Se hace el mismo procedimiento solo que con el nodo hijo hasta llegar hasta una hoja.
Si la hoja no es igual al número que se busca, entonces retorna falso.
Ejemplo
Se quiere buscar el número 39
Entonces se empieza desde la raíz.
Como 39 es menor a 45 y son diferentes, entonces va hacia la
el nodo hijo izquierdo.
Como el número es más grande que 21 y diferente, entonces
va hacia la derecha.
Como 39 es mayor, entonces va hacia el nodo que contiene el
43.
Como 39 es menor, entonces va hacia la izquierda, al número
36.
Como el número es más grande, va a ir hasta el 39, cual es el
número que se desea encontrar.
Como la encuentra retorna true.
Inserción
Inserción
Todos los nodos inicialmente se insertan como nodos hoja utilizando el estándar del árbol de búsqueda binaria.
Enlaces horizontales en los árboles AA
◦ Los cinco condiciones de árboles AA imponen restricciones a los enlaces horizontales
◦ Si alguno de las condiciones se violan el árbol debe ser modificado hasta que, una vez más cumple con las cinco condiciones
◦ Sólo dos casos deben ser considerados y corregidos para mantener el equilibrio de un árbol AA
Caso #1:
Enlace horizontal izquierda no se les permite
◦ Violar la condición # 2, el nivel de un hijo izquierdo
es estrictamente menor que la de su padre
◦ Una operación de sesgo o inclinación se introdujo
para manejar este caso
Caso #2
Dos enlaces horizontales correctas consecutivas
no se les permite
◦ Violar la condición # 4, el nivel de un nieto derecha es
estrictamente menor que el de su abuelo
◦ Una operación de división será introducido para manejar este caso
Ejemplo
Insertar 6
Insertar 2
Insertar 8
Insertar 16
Insertar 10
Insertar 1
Eliminar
Eliminar
A la hora de eliminar un nodo pueden presentarse 3
casos:
◦ Eliminar una hoja.
◦ Eliminar un nodo con un hijo.
◦ Eliminar un nodo interno
Caso I: Eliminar una hoja
Para eliminar una hoja (nodo sin hijos), basta con
borrarla.
Ejemplo: Se quiere eliminar el nodo 81.
Caso II: Eliminar un nodo con un hijo
En este caso, se reemplaza el nodo a eliminar con su
hijo. Por ser un árbol AA, un hijo único siempre será
derecho.
Ejemplo: Se quiere eliminar el nodo 88.
Caso III: Eliminar nodo interno
Cuando el nodo a eliminar tiene 2 hijos, este se
sustituye por el sucesor o antecesor inmediato.
Ejemplo: Eliminar nodo 86.
Rebalanceo
Luego de eliminar un nodo, puede ser necesario
rebalancear el árbol.
Para esto se deben recorrer los nodos desde la
posición del nodo eliminado hasta la raíz revisando
que sus niveles cumplan con las reglas.
Al encontrarse una anomalía, se ejecutan las
siguientes operaciones:
#1
Se debe decrementar el nivel de un nodo cuando:
Alguno de los hijos está mas de un nivel más
abajo.
Un nodo hoja es hijo de otro nodo cuyo nivel
ha sido decrementado.
#2
Torsionar el nivel de un nodo cuyo nivel fue disminuido
Torsionar el sub-árbol desde la raíz, donde el
nodo decrementado es la raíz.
Torsionar el hijo derecho de la raíz.
Torsionar el hijo derecho del hijo derecho de
la raíz.
#3
Dividir el nivel del nodo cuyo nivel fue decrementado
Dividir la raíz del sub-árbol.
Dividir el hijo derecho de la raíz.
Ejemplo 1
Tomamos el siguiente árbol, y eliminamos el
nodo 14.
Este caso corresponde con el caso II, donde el nodo a eliminar tiene solamente un hijo.
Como corresponde, se sustituye por este.
Ejemplo 2
Eliminaremos el nodo 71, la raíz.
Este es el caso #3.
Buscamos el sucesor del nodo, este es el 76.
Al ser este un nodo interno, nos topamos de nuevo con el caso #3, tomamos entonces alternativamente su nodo antecesor: el 73.
Sustituimos entonces el nodo 71 por el 73.
Seguidamente hacemos una división en el nodo hijo derecho, que es el 76, mediante una rotación hacia la izquierda.
Con esto el árbol queda balanceado.
Ejemplo 3
En el mismo árbol, eliminamos el nodo 3.
Este es una hoja, por lo tanto para eliminarlo basta con quitarlo.
Sin embargo, esto causa que el árbol se desbalancee,
pues 8 tiene más de 2 enlaces horizontales
consecutivos.
Para solucionarlo, se hace una división. Se sube el nodo del medio, es decir, el 38.
Esto deja el árbol balanceado
Ejemplo 4
Se tiene el siguiente árbol y se quiere eliminar el nodo 1:
Al eliminar el nodo 1, el nodo 2 viola la condición #5 pues queda con un solo hijo.
Se debe decrementar el nivel del nodo 2.
Esto causa que el nodo 4 esté más de un nivel sobre su nodo hijo.
Se debe decrementar el nivel del nodo 4, y por lo tanto también el del nodo 10, pues está en el mismo nivel.
El nodo 4 queda con dos nodos consecutivos en el mismo nivel y 10 viola la condición #2 al tener un hijo izquierdo en el mismo nivel.
Luego de decrementar los niveles se comienza a torsionar, primero el nodo 4 (no causa cambios) y luego el su hijo derecho (nodo 10).
Luego se torsiona el nodo derecho del derecho (nuevamente 10).
Seguidamente se aplica la división al nodo 4. Vemos como 6 pasa a ser la raíz.
Finalmente se divide el nodo derecho, es decir
el 8.
Árbol completamente balanceado.
Ejemplo 5
En el mismo árbol anterior ahora borramos el nodo 5.
Al ser una hoja, simplemente se elimina.
Esto nos deja el nodo 4 violando la condición #5 y con un hijo al lado izquierdo.
Se decrementa como es usual y hacemos una torsión al nodo 4.
Tenemos un enlace izquierdo con más de 1 elemento consecutivo, por lo tanto se hace la división y se asciende el nodo del medio: el 3.
Con ese último movimiento el árbol queda balanceado.
Bibliografía Wilburn, T. (2012, 03 de Noviembre). Adventures in data structure: AA Trees Recuperado el
10 de Noviembre del 2013, de
http://thomaswilburn.net/typedefs/index.php/tree/aa/aa_trees.html
Moscola, J. (2012, 25 de Octubre). CS 350: Data Structures. AA Trees Recuperado el 10 de
Noviembre del 2013, de http://faculty.ycp.edu/~dbabcock/cs350/lectures/AATrees.pdf
Heger, D. (s. f.). A Disquisition on The Performance Behaviour of Binary Search Tree Data
Structures The European Journal for the Informatics Professional, 5. Recuperado el 11 de
Noviembre del 2013, de http://www.cepis.org/upgrade/files/full-2004-V.pdf
Andersson, A. (1993). Balanced search trees made simple. Proc. Workshop on Algorithms
and Data Structures, 1, 60-71.
González, E. (2013, 13 de Mayo). Arbol AA Recuperado el 11 de Noviembre del 2013, de
http://www.slideshare.net/HALO2Y3/arbol-aa?from_search=1
Silva L. (2010). Estructuras de Datos y Algoritmos, capitulo 15. Recuperado de la dirección
http://www2.elo.utfsm.cl/~lsb/elo320/clases/c15.pdf
Recommended