algorithm - ordenado - arboles avl aplicaciones

Equilibrio de un árbol binario(AVL)

Question

Bien, este es otro en el reino de la teoría para los tipos de CS alrededor.

En los años 90 lo hice bastante bien al implementar BST. Lo único que nunca entendí fue la complejidad del algoritmo para equilibrar un árbol binario (AVL).

¿Pueden ayudarme en esto?

Answer 1

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 le da al "color" del nodo.

Answer 2

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

Mientras que el clásico árbol AVL y RB utiliza un enfoque determinista, sugiero echar un vistazo a " Árboles de búsqueda binarios aleatorizados " que son menos costosos para mantener el equilibrio y garantizar un buen equilibrio independientemente de la distribución estadística de las claves.

Answer 3

He estado trabajando un poco 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
  }
}

Answer 4

No creo que sea bueno publicar códigos completos para los algoritmos de equilibrio de nodos aquí ya que son bastante grandes. Sin embargo, el artículo de Wikipedia sobre árboles rojo-negro contiene una implementación C completa 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 5

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

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

Al ser un principiante de , traté de publicar mi código aquí, pero me quedé con problemas de formato. Entonces, cargué el archivo en el enlace de arriba.

Aclamaciones.

Answer 6

Un árbol de chivo expiatorio posiblemente tenga el algoritmo de determinación de 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 edición de pregunta

Proporcionaré mi camino personal para comprender los á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.

Luego, 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.

Luego, comprenda 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 equilibrarse.

La parte final de entenderlo 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 las listas de códigos ayude mucho con cualquier etapa excepto la última, así que ignóralas. 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.

Answer 7

hay una implementación completa de un árbol avl autoequilibrado @ 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 una colección de mapa / multimapa