Árbol AA

Un árbol AA en informática es una forma de árbol equilibrado que se utiliza para almacenar y recuperar datos ordenados de manera eficiente. Los árboles AA reciben su nombre de su creador, el científico informático sueco Arne Andersson. ^[1]

Los árboles AA son una variación del árbol rojo-negro , una forma de árbol de búsqueda binaria que permite la adición y eliminación eficiente de entradas. A diferencia de los árboles rojo-negros, los nodos rojos de un árbol AA solo se pueden agregar como subhijo derecho. En otras palabras, ningún nodo rojo puede ser subhijo izquierdo. Esto da como resultado la simulación de un árbol 2-3 en lugar de un árbol 2-3-4 , lo que simplifica enormemente las operaciones de mantenimiento. Los algoritmos de mantenimiento de un árbol rojo-negro deben considerar siete formas diferentes para equilibrar adecuadamente el árbol:

Por otro lado, un árbol AA solo necesita considerar dos formas debido al estricto requisito de que solo los enlaces correctos pueden ser rojos:

Mientras que los árboles rojo-negros requieren un bit de metadatos de equilibrio por nodo (el color), los árboles AA requieren O(log(log(N))) bits de metadatos por nodo, en forma de un "nivel" entero. Las siguientes invariantes se cumplen para los árboles AA:

1. El nivel de cada nodo hoja es uno.
2. El nivel de cada hijo izquierdo es exactamente uno menos que el de su padre.
3. El nivel de cada derecho de un niño es igual o inferior al de su padre.
4. El nivel de cada nieto con derecho es estrictamente inferior al de su abuelo.
5. Cada nodo de nivel mayor que uno tiene dos hijos.

Un enlace en el que el nivel del hijo es igual al de su padre se denomina enlace horizontal y es análogo a un enlace rojo en el árbol rojo-negro. Se permiten enlaces horizontales derechos individuales, pero están prohibidos los consecutivos; todos los enlaces horizontales izquierdos están prohibidos. Estas son restricciones más restrictivas que las análogas en los árboles rojo-negros, con el resultado de que reequilibrar un árbol AA es procedimentalmente mucho más simple que reequilibrar un árbol rojo-negro.

Las inserciones y eliminaciones pueden hacer que un árbol AA se desequilibre transitoriamente (es decir, que viole las invariantes del árbol AA). Solo se necesitan dos operaciones distintas para restablecer el equilibrio: "sesgar" y "dividir". Sesgar es una rotación a la derecha para reemplazar un subárbol que contiene un enlace horizontal izquierdo por uno que contiene un enlace horizontal derecho en su lugar. Dividir es una rotación a la izquierda y un aumento de nivel para reemplazar un subárbol que contiene dos o más enlaces horizontales derechos consecutivos por uno que contiene dos enlaces horizontales derechos consecutivos menos. La implementación de la inserción y eliminación que preserva el equilibrio se simplifica al confiar en las operaciones de sesgo y división para modificar el árbol solo si es necesario, en lugar de hacer que quienes las llaman decidan si sesgar o dividir.

La función skew tiene 
    como entrada: T, un nodo que representa un árbol AA que necesita reequilibrarse.
     Salida: Otro nodo que representa el árbol AA reequilibrado.

    si es nulo(T), entonces 
        devuelve Nil;
     de lo contrario, si es nulo(izquierda(T)), entonces 
        devuelve T;
     de lo contrario, si nivel(izquierda(T)) == nivel(T), entonces 
        Intercambia los punteros de los enlaces horizontales izquierdos.
        L = izquierda(T)
        izquierda(T) := derecha(L)
        derecha(L) := T
        devuelve L
     de lo contrario 
        devuelve T
     fin si 
fin de función

Sesgar:

La función split tiene 
    como entrada: T, un nodo que representa un árbol AA que necesita ser reequilibrado.
     Salida: Otro nodo que representa el árbol AA reequilibrado.

    si nil(T) entonces 
        devuelve Nil
     de lo contrario si nil(derecha(T)) o nil(derecha(derecha(T))) entonces 
        devuelve T
     de lo contrario si nivel(T) == nivel(derecha(derecha(T))) entonces 
        Tenemos dos enlaces derechos horizontales. Tome el nodo del medio, elévelo y devuélvalo.
        R = derecha(T)
        derecha(T) := izquierda(R)
        izquierda(R) := T
        nivel(R) := nivel(R) + 1
        retorna R
     de lo contrario 
        retorna T
     fin si 
fin de función

Dividir:

La inserción comienza con el procedimiento normal de búsqueda e inserción de árboles binarios. Luego, a medida que se desenrolla la pila de llamadas (suponiendo una implementación recursiva de la búsqueda), es fácil verificar la validez del árbol y realizar las rotaciones que sean necesarias. Si surge un vínculo horizontal a la izquierda, se realizará una desviación, y si surgen dos vínculos horizontales a la derecha, se realizará una división, posiblemente incrementando el nivel del nuevo nodo raíz del subárbol actual. Observe, en el código que se muestra arriba, el incremento de level(T). Esto hace que sea necesario continuar verificando la validez del árbol a medida que las modificaciones surgen de las hojas.

La función insertar tiene 
    como entrada: X, el valor que se va a insertar, y T, la raíz del árbol donde insertarlo.
     Salida: Una versión balanceada de T que incluye X.

    Realice el procedimiento normal de inserción de árboles binarios. Establezca el resultado de la 
    llamada recursiva en el hijo correcto en caso de que se haya creado un nuevo nodo o 
    cambie la raíz del subárbol. 
    if nil(T) then 
        Cree un nuevo nodo de hoja con X. 
        return node(X, 1, Nil, Nil)
     else if X < value(T) then
        izquierda(T) := insertar(X, izquierda(T))
    de lo contrario si X > valor(T) entonces
        derecha(T) := insertar(X, derecha(T))
    fin si 
    Nótese que el caso de X == valor(T) no está especificado. Como se indica, una inserción 
    no tendrá efecto. El implementador puede desear un comportamiento diferente.

    Realice la operación de sesgo y luego la de división. Las condiciones que determinan si 
    se producirá o no una rotación se encuentran dentro de los procedimientos, como se indicó 
    anteriormente.
    T := sesgo(T)
    T := dividir(T)

    función de retorno T 
final

Como en la mayoría de los árboles binarios balanceados, la eliminación de un nodo interno se puede convertir en la eliminación de un nodo hoja intercambiando el nodo interno con su predecesor o sucesor más cercano, dependiendo de cuáles estén en el árbol o según los caprichos del implementador. Recuperar un predecesor es simplemente una cuestión de seguir un enlace izquierdo y luego todos los enlaces derechos restantes. De manera similar, el sucesor se puede encontrar yendo una vez a la derecha y luego a la izquierda hasta que se encuentre un puntero nulo. Debido a la propiedad AA de todos los nodos de nivel mayor que uno que tienen dos hijos, el nodo sucesor o predecesor estará en el nivel 1, lo que hace que su eliminación sea trivial.

Para reequilibrar un árbol, existen varios enfoques. El descrito por Andersson en su artículo original es el más simple y se describe aquí, aunque las implementaciones reales pueden optar por un enfoque más optimizado. Después de una eliminación, el primer paso para mantener la validez del árbol es reducir el nivel de todos los nodos cuyos hijos están dos niveles por debajo de ellos, o que son hijos faltantes. Luego, todo el nivel debe sesgarse y dividirse. Este enfoque fue el preferido porque, cuando se establece conceptualmente, tiene tres pasos separados que se entienden fácilmente:

1. Disminuya el nivel, si es apropiado.
2. Inclinar el nivel.
3. Dividir el nivel.

Sin embargo, esta vez tenemos que sesgar y dividir todo el nivel en lugar de solo un nodo, lo que complica nuestro código.

La función eliminar tiene 
    como entrada: X, el valor a eliminar, y T, la raíz del árbol del que se debe eliminar.
     Salida: T, balanceada, sin el valor X.
   
    Si nulo(T) entonces
        devolver T
    de lo contrario si X > valor(T) entonces
        derecha(T) := eliminar(X, derecha(T))
    de lo contrario si X < valor(T) entonces
        izquierda(T) := eliminar(X, izquierda(T))
    de lo 
        contrario, reducimos al caso de hoja.  
        si hoja(T) entonces
            volver a la derecha (T)
        De lo contrario, si es nulo (izquierda (T)), entonces
            L := sucesor(T)
            derecha(T) := eliminar(valor(L), derecha(T))
            valor(T) := valor(L)
        demás
            L := predecesor(T)
            izquierda(T) := eliminar(valor(L), izquierda(T))
            valor(T) := valor(L)
        fin si 
    fin si

    Reequilibre el árbol. Si es 
    necesario, reduzca el nivel de todos los nodos de este nivel y, luego, incline y divida todos los nodos del nuevo nivel.
    T := nivel_de_disminución(T)
    T := sesgo(T)
    derecha(T) := sesgar(derecha(T))
    si no es nulo(derecho(T))
        derecha(derecha(T)) := sesgar(derecha(derecha(T)))
    terminar si
    T := dividir(T)
    derecha(T) := dividir(derecha(T))
    devolver T
función final

La función decrease_level tiene 
    como entrada: T, un árbol para el cual queremos eliminar enlaces que saltan niveles.
     Salida: T con su nivel disminuido.

    debería_ser = min(nivel(izquierda(T)), nivel(derecha(T))) + 1
    si debería ser < nivel(T) entonces
        nivel(T) := debería_ser
        si should_be < nivel(derecha(T)) entonces
            nivel(derecha(T)) := debería_ser
        fin si 
    fin si
    devolver T
función final

Un buen ejemplo de eliminación mediante este algoritmo se encuentra en el artículo de Andersson.

El rendimiento de un árbol AA es equivalente al de un árbol rojo-negro. Si bien un árbol AA realiza más rotaciones que un árbol rojo-negro, los algoritmos más simples tienden a ser más rápidos, y todo esto se equilibra para dar como resultado un rendimiento similar. Un árbol rojo-negro tiene un rendimiento más consistente que un árbol AA, pero este último tiende a ser más plano, lo que da como resultado tiempos de búsqueda ligeramente más rápidos. ^[2]

• Árbol rojo-negro
• Árbol B
• Árbol AVL
• Árbol del chivo expiatorio

• A. Andersson. Árboles de búsqueda equilibrados simplificados
• A. Andersson. Una nota sobre la búsqueda en un árbol binario de búsqueda
• BSTlib Archivado el 7 de agosto de 2011 en Wayback Machine : una biblioteca de árboles AA de código abierto para C por trijezdci
• AA Visual 2007 1.5: programa Delphi de código abierto para enseñar estructuras de árbol AA
• Completo tutorial de Julienne Walker con mucho código, incluida una implementación práctica
• Implementación orientada a objetos con pruebas
• Disquisición sobre el comportamiento del rendimiento de las estructuras de datos de árboles de búsqueda binaria (páginas 67–75): comparación de árboles AA, árboles rojo-negros, treaps, listas de omisión y árboles de base
• Una implementación de Objective-C
• Implementación de Python