Á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