Equilibrio de un árbol binario (AVL)

Question

Ok, este es otro en el reino de la teoría para los chicos de CS que lo rodean.

En los años 90, hice bastante bien en la implementación de BST. Lo único que nunca pude entender fue la complejidad del algoritmo para equilibrar un árbol binario (AVL).

¿Pueden ayudarme en esto?

Answer 1

Un árbol chivo expiatorio posiblemente tiene el algoritmo más simple de determinación de equilibrio para entender. Si alguna inserción hace que el nuevo nodo sea demasiado profundo, encuentra un nodo alrededor del cual se puede reequilibrar, mirando el balance de peso en lugar del balance de altura. La regla de si se debe reequilibrar al eliminar también es simple. No almacena ninguna información arcana en los nodos. Es más difícil demostrar que es correcto, pero no necesita eso para entender el algoritmo ...

Sin embargo, a diferencia de un AVL, no está equilibrado en altura en todo momento. Al igual que el rojo-negro, su desequilibrio es 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 lo necesita. Sin embargo, sospecho que si lo ajusta demasiado, termina siendo tan malo o peor que AVL para las inserciones en el peor de los casos.

Respuesta a la edición de preguntas

Proporcionaré mi camino personal para comprender los árboles AVL.

Primero debes entender qué es la rotación de un árbol, así que ignora todo lo demás que has escuchado de los algoritmos AVL y comprende eso. Póngase derecho en su cabeza, que es una rotación hacia la derecha y hacia la izquierda, y lo que cada uno le hace al árbol, o de lo contrario las descripciones de los métodos precisos lo confundirán.

A continuación, comprenda que el truco para equilibrar los á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, comprenda que si ha agregado o eliminado un nodo, puede haber desequilibrado el árbol. Pero solo puede haber cambiado el equilibrio de los nodos que son ancestros del nodo que agregó o eliminó. Entonces, lo que vas a hacer es subir de nuevo el árbol, usando rotaciones para equilibrar los nodos desequilibrados que encuentres y actualizando su puntaje de equilibrio, hasta que el árbol vuelva a estar equilibrado.

La parte final de comprenderlo es buscar en una referencia decente las rotaciones específicas utilizadas para reequilibrar cada nodo que encuentre: esta es la técnica de "técnica". de ello frente al concepto alto. Solo tiene que recordar los detalles al modificar el código de árbol AVL o tal vez durante los exámenes de estructuras de datos. Han pasado años desde la última vez que tuve el código de árbol AVL abierto en el depurador: las implementaciones tienden a llegar a un punto en el que funcionan y luego permanecen funcionando. Así que realmente no recuerdo. Puedes resolverlo en una mesa usando algunas fichas de póker, pero es difícil estar seguro de que realmente tienes todos los casos (no hay muchos). Mejor solo para buscarlo.

Luego está el negocio de traducirlo todo en código.

No creo que mirar los listados de códigos ayude mucho en cualquier etapa, excepto en la última, así que ignóralos. Incluso en el mejor de los casos, donde el código está claramente escrito, se verá como una descripción de un libro de texto del proceso, pero sin los diagramas. En un caso más típico es un lío de manipulación de estructuras. Así que solo apégate a los libros.

Answer 2

No creo que sea bueno publicar códigos completos para algoritmos de equilibrio de nodos aquí, ya que se vuelven bastante grandes. Sin embargo, el artículo de Wikipedia sobre árboles rojo-negros contiene una implementación completa en C del algoritmo y el artículo sobre árboles AVL también tiene varios enlaces a implementaciones de alta calidad.

Estas dos implementaciones son suficientes para la mayoría de los escenarios de propósito general.

Answer 3

Últimamente he estado trabajando con los árboles AVL.

La mejor ayuda que pude encontrar sobre cómo equilibrarlos fue mediante la búsqueda en Google.

Acabo de codificar este pseudocó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
  }
}

Answer 4

Estoy de acuerdo, un programa completo no sería apropiado.

Si bien los árboles AVL y RB clásicos utilizan un enfoque determinista, sugeriría echar un vistazo a " Árboles de búsqueda binarios aleatorizados " que son menos costosos para mantenerlos equilibrados y garantizan un buen equilibrio independientemente de la distribución estadística de las claves.

Answer 5

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 del doble del camino más corto. Entonces, aunque es menos equilibrado que un árbol AVL, se evitan los casos más desequilibrados.

Si su árbol se leerá muchas veces y no se modificará después de su creación, puede valer la pena la sobrecarga adicional para un árbol AVL completamente equilibrado. Además, el árbol Rojo-Negro requiere un bit extra de almacenamiento para cada nodo, lo que le da el " color " ;.

Answer 6

Para equilibrar un árbol AVL, acabo de escribir un montón de funciones que pensé compartir con todos aquí. Supongo que esta implementación es impecable. Las consultas / preguntas / críticas son, por supuesto, bienvenidas:

http://uploading.com/files/5883f1c7/AVL_Balance.cpp/

Al ser un principiante en Stackoverflow, intenté publicar mi código aquí, pero tuve problemas con el formato. Por lo tanto, subí el archivo en el enlace anterior.

Saludos.

Answer 7

hay una implementación completa de un árbol avl autobalanceado @ 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 / mapas múltiples