Árbol AA

En informática un árbol AA es un tipo de árbol binario de búsqueda auto-balanceable utilizado para almacenar y recuperar información ordenada de manera eficiente. Los árboles AA reciben el nombre de su inventor, . Los árboles AA son una variación del árbol rojo-negro, que a su vez es una mejora del árbol binario de búsqueda. A diferencia de los árboles rojo-negro, los nodos rojos en un árbol AA sólo pueden añadirse como un hijo derecho. En otras palabras, ningún nodo rojo puede ser un hijo izquierdo. De esta manera se simula un árbol 2-3 en lugar de un , lo que simplifica las operaciones de mantenimiento. Los algoritmos de mantenimiento para un árbol rojo-negro necesitan considerar siete diferentes formas para balancear adecuadamente el árbol: En un árbol AA, al cumplirse el estricto requisito de que sólo los enlaces derechos pueden ser rojos, sólo es necesario considerar dos formas: