Ok, este es otro en el reino de la teoría para los tipos de CS.Equilibrio de un árbol binario (AVL)
En los años 90 hice bastante bien en la implementación de BST. Lo único que nunca entendí fue la complejidad del algoritmo para equilibrar un árbol binario (AVL).
¿Pueden ayudarme en esto?
Un árbol de chivo expiatorio posiblemente tiene el algoritmo de determinación del equilibrio más simple de entender. Si alguna inserción hace que el nuevo nodo sea demasiado profundo, encuentra un nodo alrededor del cual reequilibrar, observando el equilibrio de peso en lugar del equilibrio de altura. La regla de si reequilibrar o eliminar también es simple. No almacena ninguna información arcana en los nodos. Es más complicado probar que es correcto, pero no es necesario para entender el algoritmo ...
Sin embargo, a diferencia de una AVL, no tiene un equilibrio de altura en todo momento. Al igual que el rojo-negro, su desequilibrio está limitado, pero a diferencia del rojo-negro, se puede ajustar con un parámetro, por lo que para la mayoría de los propósitos prácticos se ve tan equilibrado como se necesita. Sospecho que si lo sintonizas demasiado fuerte, terminará igual o peor que AVL para las inserciones del peor caso.
Respuesta a la pregunta de edición
voy a ofrecer mi camino personal hacia la comprensión de árboles AVL.
Primero tienes que entender qué es la rotación de un árbol, así que ignora todo lo demás que hayas escuchado sobre los algoritmos AVL y entiéndelo. Póngase recto en su cabeza, que es una rotación a la derecha y que es una rotación a la izquierda, y lo que cada uno le hace al árbol, o las descripciones de los métodos precisos lo confundirán.
A continuación, comprenda que el truco para equilibrar árboles AVL es que cada nodo registra en él la diferencia entre la altura de sus subárboles izquierdo y derecho. La definición de 'altura equilibrada' es que está entre -1 y 1 inclusive para cada nodo en el árbol.
A continuación, tenga en cuenta que si ha agregado o eliminado un nodo, es posible que haya desequilibrado el árbol. Pero solo puede haber cambiado el equilibrio de nodos que son ancestros del nodo que agregó o eliminó. Entonces, lo que vas a hacer es volver a trabajar en el árbol, usando rotaciones para equilibrar los nodos desequilibrados que encuentres y actualizar su puntaje de equilibrio, hasta que el árbol vuelva a estar equilibrado.
La parte final de entender es buscar en una referencia decente las rotaciones específicas usadas para reequilibrar cada nodo que encuentre: esta es la "técnica" de la misma en comparación con el concepto alto. Solo debe recordar los detalles al modificar el código de árbol AVL o quizás durante los exámenes de estructuras de datos. Han pasado muchos años desde la última vez que tuve código de árbol AVL hasta abrirlo en el depurador: las implementaciones tienden a llegar a un punto en el que funcionan y luego siguen funcionando. Entonces realmente no recuerdo. Puedes resolverlo en una mesa usando algunas fichas de poker, pero es difícil estar seguro de que realmente tienes todos los casos (no hay muchos). Lo mejor es buscarlo.
Luego está el negocio de traducirlo todo en código.
No creo que mirar los listados de códigos ayude mucho con cualquier etapa excepto la última, así que ignórelas. Incluso en el mejor de los casos, donde el código está escrito claramente, se verá como una descripción de libro de texto del proceso, pero sin los diagramas. En un caso más típico, es un desastre de manipulación de C struct. Así que solo adhiérase a los libros.
Estoy aceptando su respuesta porque era lo que quería de la pregunta: una buena descripción de lo que se debe hacer. –
Me alegro de que te guste, los enlaces de Konrad a Wikipedia también son útiles, ya que proporcionan los detalles que he omitido. –
No creo que sea bueno publicar aquí los códigos completos para los algoritmos de balanceo de nodos ya que son bastante grandes. Sin embargo, el artículo de Wikipedia en red-black trees contiene una implementación C completa del algoritmo y el artículo en AVL trees tiene varios enlaces a implementaciones de alta calidad también.
Estas dos implementaciones son suficientes para la mayoría de los escenarios de uso general.
No te olvides de los árboles de separación. –
No acepté su respuesta porque no explica, solo enlaces. Mi intención era obtener una respuesta descriptiva que ayudaría. ¡Gracias de cualquier manera! –
Su código de pregunta, no explicaciones. De todos modos, no tenía la intención de que mi respuesta fuera aceptada de todos modos (porque no es realmente una respuesta) ... ¡Tu nueva pregunta es mucho mejor! –
Estoy de acuerdo, un programa completo no sería apropiado.
Mientras que el árbol AVL y RB clásico utiliza un enfoque determinista, sugiero echar un vistazo a "Randomized binary search trees" que son menos costosos para mantener el equilibrio y garantizar un buen equilibrio independientemente de la distribución estadística de las claves.
El árbol AVL es ineficiente porque tiene que hacer potencialmente muchas rotaciones por inserción/eliminación.
El árbol Rojo-Negro es probablemente una mejor alternativa porque las inserciones/eliminaciones son mucho más eficientes. Esta estructura garantiza que el camino más largo a una hoja no es más que el doble del camino más corto. Por lo tanto, aunque menos equilibrado que un árbol AVL, se evitan los peores casos desequilibrados.
Si su árbol será leído muchas veces, y no será alterado después de haber sido creado, puede valer la pena la sobrecarga adicional para un árbol AVL totalmente equilibrado. Además, el árbol Rojo-Negro requiere un poco más de almacenamiento para cada nodo, lo que da el "color" del nodo.
Personalmente hablando, nunca he encontrado una * explicación * real de los árboles RB, simplemente una lista de las reglas. Nadie parece entender el * por qué * de RB. OTOH, AVL fue para mí intuitivo y directo de comprender; y solo debes escribir el código que comprendes. –
El "por qué": los árboles RB son un mapeo de 2-3-4 árboles en árboles binarios, donde los bordes rojos conectan las porciones de un nodo de árbol 2-3-4 dividido y los bordes negros corresponden a los bordes en el original 2-3-4 árbol. –
Una cosa, acerca de "potencialmente muchas rotaciones por inserción/eliminación". Las inserciones AVL solo necesitan una sola rotación o doble rotación para restablecer el equilibrio. Pero sí, Delete podría tener hasta O (log N) rotaciones. – otherchirps
He estado haciendo un poco de trabajo con los árboles AVL últimamente.
La mejor ayuda que pude encontrar sobre cómo equilibrarlos fue a través de la búsqueda en google.
Acabo de codificar este pseudo código (si entiendes cómo hacer rotaciones es bastante fácil de implementar).
IF tree is right heavy
{
IF tree's right subtree is left heavy
{
Perform Double Left rotation
}
ELSE
{
Perform Single Left rotation
}
}
ELSE IF tree is left heavy
{
IF tree's left subtree is right heavy
{
Perform Double Right rotation
}
ELSE
{
Perform Single Right rotation
}
}
Esta parte de AVL es bastante sencilla: lo que se torna un poco más complicado es actualizar los factores de equilibrio después de las rotaciones. –
Para equilibrar un árbol AVL Acabo de escribir un conjunto de funciones que pensé compartir con todos los que estaban aquí. Supongo que esta implementación es perfecta. Consultas/preguntas/crítica, por supuesto, bienvenidos:
http://uploading.com/files/5883f1c7/AVL_Balance.cpp/
ser un novato a Stackoverflow, He intentado publicar mi código aquí, pero se quedó con problemas de formato malas. Entonces, cargué el archivo en el enlace de arriba.
Saludos.
hay una implementación completa de un árbol avl de auto-equilibrio @http://code.google.com/p/self-balancing-avl-tree/. también implementa operaciones de concatenación y división de tiempo logarítmico, así como colecciones de mapas/multimapas
¿Desea que el árbol * perfectamente * esté equilibrado? Los algoritmos más comunes garantizan que un árbol esté algo equilibrado. Por ejemplo, los árboles rojo-negros garantizan que la profundidad del nodo de hoja más profundo no sea más del doble de la profundidad del nodo de hoja más superficial –
Además, ¿está buscando un algoritmo toma un árbol y lo equilibra, o uno que equilibra como parte de las operaciones del árbol, como insertar, eliminar, etc. –
deben definirse "perfectamente". Sin embargo, en el contexto de los árboles binarios, la única definición significativa es la de un árbol binario con altura logarítmica, ¿no es así? –