Árbol AA

Este artículo necesita citas adicionales para su verificación . Por favor, ayude a mejorar este artículo añadiendo citas de fuentes fiables . El material sin fuentes puede ser cuestionado y eliminado. Buscar fuentes:  «Árbol AA» – noticias  · periódicos  · libros  · académico  · JSTOR ( junio de 2011 ) ( Aprenda cómo y cuándo eliminar este mensaje )

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 en un árbol AA solo se pueden agregar como subhijo derecho. En otras palabras, ningún nodo rojo puede ser un 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 para 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 individuales a la derecha, pero se prohíben los consecutivos; se prohíben todos los enlaces horizontales a la izquierda. 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 provocar transitoriamente que un árbol AA se desequilibre (es decir, que viole las invariantes del árbol AA). Solo se necesitan dos operaciones distintas para restablecer el equilibrio: "sesgar" y "dividir". La escisión 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. La división 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 escisión y división para modificar el árbol solo si es necesario, en lugar de hacer que quienes las llaman decidan si se debe esesgar 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 devolver R de lo contrario  devolver 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 debe eliminarse. 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 Regresar 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 Tfunció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 Tfunció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 de chivos expiatorios

• 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