Árboles AA | Serie 1 (Introducción)

Los árboles AA son la variación de los árboles rojo-negro , una forma de árbol de búsqueda binaria .

Los árboles AA utilizan el concepto de niveles para ayudar a equilibrar los árboles binarios . El nivel de Node (en lugar de color) se utiliza para equilibrar la información. Un enlace en el que los niveles del padre y del hijo son los mismos se denomina enlace horizontal y es análogo a un enlace rojo en el árbol rojo-negro.

• El nivel de cada Node hoja es uno.
• El nivel de los Nodes rojos es el mismo que el nivel de sus Nodes principales y los enlaces se denominan enlaces horizontales .
• El nivel de los Nodes negros es uno menos que el nivel de su Node principal.

El requisito de almacenamiento adicional con cada Node es O (Log n) en árboles rojos y negros en lugar de O (1) (solo color en árboles rojos y negros), pero los árboles AA simplifican la reestructuración al eliminar muchos casos.

Un árbol AA sigue la misma regla que los árboles rojo-negro con la adición de una sola regla nueva de que los Nodes rojos no pueden estar presentes como hijos izquierdos.

1. Cada Node puede ser rojo (enlazado horizontalmente) o negro.
2. No hay dos Nodes rojos adyacentes (o enlaces horizontales).
3. Cada ruta desde la raíz hasta un Node NULO tiene el mismo número de Nodes negros (en enlaces negros).
4. El enlace izquierdo NO puede ser rojo (horizontal). (Nueva regla añadida)

Por qué árboles AA:
La implementación y el número de casos de rotación en árboles rojos y negros es complejo. Los árboles AA simplifican el algoritmo.

• Elimina la mitad del proceso de reestructuración al eliminar la mitad de los casos de rotación, lo que es más fácil de codificar.
• Simplifica el proceso de eliminación al eliminar varios casos.

El siguiente árbol es el ejemplo del árbol AA:

Tenga en cuenta que en el árbol anterior no quedan niños rojos, que es la nueva regla agregada de AA Trees.

Después de volver a dibujar el árbol AA anterior con niveles y enlaces horizontales (los Nodes rojos se muestran conectados a través de enlaces horizontales o rojos), el árbol se ve así:

Tenga en cuenta que todos los Nodes en el nivel 1, es decir, 5, 10, 20, 35, 40, 55, 65, 80, 90 se conocen como Nodes hoja.

Entonces, de manera resumida, para que un árbol sea un árbol AA, debe satisfacer las siguientes cinco invariantes:

1.) El nivel del Node hoja es 1.
2.) El nivel del hijo izquierdo es exactamente uno menos que el de su padre.
3.) El nivel de cada hijo derecho es igual o uno menos que el de su padre.
4.) El nivel de cada nieto derecho es estrictamente menor que el de su abuelo.
5.) Cada Node de nivel mayor que uno tiene dos hijos.

Referencias:
http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_andersson.aspx
https://ycpcs.github.io/cs350-fall2017/lectures/AA-tree_lecture.pdf
https://en.wikipedia.org/ wiki/Árbol_AA