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 llevan el nombre de Arne Andersson , su inventor.
Los árboles AA son una variación del árbol rojo-negro , una forma de árbol de búsqueda binaria que admite la adición y eliminación eficiente de entradas. A diferencia de los árboles rojo-negro, los nodos rojos en un árbol AA solo se pueden agregar como subhijos 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:
Un árbol AA, por otro lado, solo necesita considerar dos formas debido al estricto requisito de que solo los enlaces correctos pueden ser rojos:
Equilibrio de rotaciones
Mientras que los árboles rojo-negro 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. Los siguientes invariantes son válidos para los árboles AA:
- El nivel de cada nodo hoja es uno.
- El nivel de cada hijo izquierdo es exactamente uno menos que el de su padre.
- El nivel de cada hijo correcto es igual o uno menos que el de su padre.
- El nivel de cada nieto de derecho es estrictamente menor que el de su abuelo.
- Cada nodo de nivel superior a uno tiene dos hijos.
Un vínculo donde el nivel del niño es igual al de su padre se llama vínculo horizontal y es análogo a un vínculo rojo en el árbol rojo-negro. Se permiten enlaces horizontales de derecha individuales, pero se prohíben los consecutivos; Todos los enlaces horizontales izquierdos están prohibidos. Estas son restricciones más restrictivas que las análogas en los árboles rojo-negro, con el resultado de que reequilibrar un árbol AA es mucho más sencillo desde el punto de vista del procedimiento que reequilibrar un árbol rojo-negro.
Las inserciones y eliminaciones pueden provocar transitoriamente que un árbol AA se desequilibre (es decir, violar las invariantes del árbol AA). Solo se necesitan dos operaciones distintas para restaurar el equilibrio: "sesgar" y "dividir". Skew es una rotación a la derecha para reemplazar un subárbol que contiene un enlace horizontal izquierdo con 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 con uno que contiene dos enlaces horizontales derechos consecutivos menos. La implementación de la inserción y eliminación que preservan el equilibrio se simplifica confiando en las operaciones de sesgo y división para modificar el árbol solo si es necesario, en lugar de hacer que sus llamantes decidan si sesgar o dividir.
la función sesgo es la entrada: T, un nodo que representa un árbol AA que necesita ser reequilibrado. salida: Otro nodo que representa el árbol AA reequilibrado. if nil (T) luego devuelve Nil else if nil (left (T)) luego regresa T else if level (left (T)) == level (T) luego intercambia los punteros de los enlaces horizontales izquierdos. L = izquierda (T) izquierda (T): = derecha (L) derecha (L): = T return L else return T end if end function
Sesgar:
la función split es input: T, un nodo que representa un árbol AA que necesita ser reequilibrado. salida: Otro nodo que representa el árbol AA reequilibrado. if nil (T) entonces devuelve Nil else if nil (right (T)) o nil (right (right (T))) entonces devuelve T else if level (T) == level (right (right (T))) entonces Tenemos dos enlaces derechos horizontales. Tome el nodo del medio, levántelo y devuélvalo. R = derecha (T) derecha (T): = izquierda (R) izquierda (R): = T nivel (R): = nivel (R) + 1 return R else return T end if end function
Separar:
Inserción
La inserción comienza con el procedimiento normal de búsqueda e inserción de árbol binario. Luego, a medida que se desenrolla la pila de llamadas (asumiendo una implementación recursiva de la búsqueda), es fácil verificar la validez del árbol y realizar cualquier rotación según sea necesario. Si surge un enlace horizontal a la izquierda, se realizará un sesgo, y si surgen dos enlaces horizontales a la derecha, se realizará una división, posiblemente aumentando el nivel del nuevo nodo raíz del subárbol actual. Tenga en cuenta, en el código como se indica arriba, el incremento de nivel (T). Esto hace necesario continuar verificando la validez del árbol a medida que las modificaciones brotan de las hojas.
la función insert es la entrada: X, el valor que se insertará, y T, la raíz del árbol en el que se insertará. salida: Una versión balanceada T que incluye X. Realice el procedimiento normal de inserción de árbol binario. Establezca el resultado de la llamada recursiva en el hijo correcto en caso de que se cree un nuevo nodo o cambie la raíz del subárbol. si es nulo (T) entonces cree un nuevo nodo hoja con X. return nodo (X, 1, Nil, Nil) de lo contrario si Xentonces izquierda (T): = insertar (X, izquierda (T)) de lo contrario, si X> valor (T) entonces derecha (T): = insertar (X, derecha (T)) end if Tenga en cuenta que el caso de X == valor (T) no está especificado. Como se indica, un inserto no tendrá ningún efecto. El implementador puede desear un comportamiento diferente. Realice un sesgo y luego divida. Los condicionales que determinan si se producirá o no una rotación están dentro de los procedimientos, como se indicó anteriormente. T: = sesgo (T) T: = dividir (T) función de retorno T fin
Supresión
Como en la mayoría de los árboles binarios equilibrados, 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 a la derecha una vez y a la izquierda hasta que se encuentre un puntero nulo. Debido a la propiedad AA de todos los nodos de nivel superior a 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 algunos 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 los nodos cuyos hijos estén dos niveles por debajo de ellos o que no tengan hijos. Luego, todo el nivel debe estar sesgado y dividido. Se favoreció este enfoque, porque cuando se establece conceptualmente, tiene tres pasos separados fácilmente comprensibles:
- Disminuya el nivel, si corresponde.
- Inclina el nivel.
- Divide el nivel.
Sin embargo, tenemos que sesgar y dividir todo el nivel esta vez en lugar de solo un nodo, lo que complica nuestro código.
la función eliminar es la 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 es nulo (T) entonces volver T de lo contrario, si X> valor (T) entonces derecha (T): = eliminar (X, derecha (T)) de lo contrario, si Xentonces izquierda (T): = eliminar (X, izquierda (T)) de lo contrario Si somos una hoja, fácil, de lo contrario, reduzca a 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): = borrar (valor (L), derecha (T)) valor (T): = valor (L) demás L: = predecesor (T) izquierda (T): = eliminar (valor (L), izquierda (T)) valor (T): = valor (L) terminar si terminar si Reequilibra el árbol. Disminuya el nivel de todos los nodos en este nivel si es necesario, y luego sesgue y divida todos los nodos en el nuevo nivel. T: = disminución_nivel (T) T: = sesgo (T) derecha (T): = sesgar (derecha (T)) si no es nulo (derecha (T)) derecha (derecha (T)): = sesgar (derecha (derecha (T))) terminara si T: = dividir (T) derecha (T): = dividir (derecha (T)) volver Tfunción final
La función disminución_level es la entrada: T, un árbol para el que queremos eliminar los enlaces que saltan niveles. salida: T con su nivel disminuido. should_be = min (nivel (izquierda (T)), nivel (derecha (T))) + 1 si should_beentonces nivel (T): = should_be if should_be then nivel (derecha (T)): = should_be terminar si terminar si volver Tfunción final
Un buen ejemplo de eliminación por este algoritmo está presente en el artículo de Andersson .
Actuación
El desempeño de un árbol AA es equivalente al desempeño de un árbol rojo-negro. Mientras que un árbol AA hace 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 es más consistente en su desempeño que un árbol AA, pero un árbol AA tiende a ser más plano, lo que resulta en tiempos de búsqueda ligeramente más rápidos. [1]
Ver también
Referencias
- ^ "Una discusión sobre el comportamiento de rendimiento de las estructuras de datos del árbol de búsqueda binaria (páginas 67-75)" (PDF) . Archivado desde el original (PDF) el 27 de marzo de 2014 . Consultado el 17 de octubre de 2010 .
enlaces externos
- A. Andersson. Árboles de búsqueda equilibrados simplificados
- A. Andersson. Una nota sobre la búsqueda en un árbol de búsqueda binaria
- BSTlib Archivado el 7 de agosto de 2011 en Wayback Machine - Biblioteca de árbol AA de código abierto para C por trijezdci
- AA Visual 2007 1.5 - Programa Delphi de código abierto para educar las estructuras de árboles de AA
- Tutorial completo de Julienne Walker con mucho código, incluida una implementación práctica
- Implementación orientada a objetos con pruebas
- Una discusión sobre el comportamiento de desempeño de las estructuras de datos de árboles de búsqueda binaria (páginas 67 a 75) - Comparación de árboles AA, árboles rojo-negro, treaps, listas de omisión y árboles de base
- Una implementación de Objective-C
- Implementación de Python