Équilibrage d'un arbre binaire (AVL)

StackOverflow https://stackoverflow.com/questions/133610

Question

Ok, c’est un autre exemple dans le domaine de la théorie pour les gars de CS autour.

Dans les années 90, j'ai assez bien réussi à mettre en œuvre la BST. La seule chose que je n'ai jamais pu comprendre, c'est la complexité de l'algorithme pour équilibrer un arbre binaire (AVL).

Pouvez-vous m'aider à ce sujet?

Était-ce utile?

La solution

Un arbre à boucs émissaires possède peut-être l'algorithme de détermination de la balance le plus simple à comprendre. Si une insertion rend le nouveau nœud trop profond, il trouve un nœud autour duquel rééquilibrer, en examinant la balance de poids plutôt que la balance de hauteur. La règle de rééquilibrage après suppression est également simple. Il ne stocke aucune information mystérieuse dans les nœuds. C'est plus délicat de prouver que c'est correct, mais vous n'avez pas besoin de ça pour comprendre l'algorithme ...

Cependant, contrairement à un AVL, il n’est pas toujours équilibré en hauteur. Comme le rouge-noir, son déséquilibre est limité, mais contrairement au rouge-noir, il est ajustable avec un paramètre. Par conséquent, pour des raisons pratiques, il est aussi équilibré que nécessaire. Je soupçonne cependant que si vous l’accordez trop, le résultat sera aussi mauvais ou pire que AVL pour les insertions dans le pire des cas.

Réponse à la question

Je fournirai mon chemin personnel pour comprendre les arbres AVL.

Tout d’abord, vous devez comprendre ce qu’est une rotation d’arbre. Ignorez tout ce que vous avez déjà entendu dans les algorithmes AVL et comprenez-le. Rentrez droit dans votre tête, ce qui correspond à une rotation à droite et à une rotation à gauche, et ce que chacun fait à l’arbre, sinon la description des méthodes précises ne fera que vous embrouiller.

Ensuite, comprenez que le truc pour équilibrer les arbres AVL est que chaque nœud enregistre la différence entre la hauteur de ses sous-arbres gauche et droit. La définition de "hauteur équilibrée" est qu’elle se situe entre -1 et 1 inclus pour chaque noeud de l’arbre.

Ensuite, comprenez que si vous avez ajouté ou supprimé un nœud, vous avez peut-être déséquilibré l’arbre. Mais vous ne pouvez modifier que l'équilibre des noeuds qui sont les ancêtres du noeud que vous avez ajouté ou supprimé. Vous allez donc remonter dans l’arbre, en effectuant des rotations pour équilibrer les nœuds non équilibrés que vous trouvez et en mettant à jour leur score d’équilibre, jusqu’à ce que l’arbre soit à nouveau équilibré.

La dernière partie de la compréhension consiste à rechercher dans une référence décente les rotations spécifiques utilisées pour rééquilibrer chaque nœud que vous trouvez: il s'agit de la "technique". de celui-ci par opposition au concept élevé. Vous devez seulement vous souvenir des détails lors de la modification du code de l'arborescence AVL ou peut-être lors des examens de structures de données. Il y a des années que je n'avais plus le code de l'arborescence AVL, mais ouvert dans le débogueur - les implémentations ont tendance à atteindre un point où elles fonctionnent, puis à rester actives. Donc je ne me souviens vraiment pas. Vous pouvez en quelque sorte travailler sur une table en utilisant quelques jetons de poker, mais il est difficile d’être sûr que vous avez vraiment tous les cas (il n’y en a pas beaucoup). Le mieux est de le regarder.

Ensuite, il y a la tâche de traduire tout cela en code.

Je ne pense pas que consulter des listes de codes soit d'une grande aide, quelle que soit l'étape, à l'exception de la dernière, ignorez-les. Même dans le meilleur des cas, où le code est clairement écrit, cela ressemblera à une description manuelle du processus, mais sans les diagrammes. Dans un cas plus typique, c'est un fouillis de manipulation de la structure C. Alors, tenez-vous-en aux livres.

Autres conseils

Je ne pense pas que ce soit bien de poster des codes complets pour les algorithmes d'équilibrage de nœud ici, car ils deviennent assez gros. Cependant, l'article de Wikipedia sur Arbres rouge-noir contient une implémentation complète en C de l'algorithme et l'article sur les Arborescence AVL contient également plusieurs liens vers des implémentations de haute qualité.

Ces deux implémentations sont suffisantes pour la plupart des scénarios généraux.

Je travaille depuis quelques temps avec les arbres AVL.

La meilleure aide que j'ai pu trouver sur la façon de les équilibrer était de chercher sur Google.

Je viens de coder ce pseudo-code (si vous comprenez comment effectuer des rotations, il est assez facile à implémenter). 

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
  }
}

Je suis d'accord, un programme complet ne serait pas approprié.

Tandis que les fichiers classiques AVL et RB utilisent une approche déterministe, je suggérerais de jeter un coup d'oeil à Arbres de recherche binaires randomisés " moins coûteux à maintenir équilibrés et garantissent un bon équilibrage quelle que soit la distribution statistique des clés.

L'arbre AVL est inefficace car vous devez potentiellement effectuer plusieurs rotations par insertion / suppression.

L’arbre rouge-noir est probablement une meilleure alternative car les insertions / suppressions sont beaucoup plus efficaces. Cette structure garantit que le plus long chemin menant à une feuille n’est pas plus de deux fois le plus court. Ainsi, tout en étant moins équilibrés qu’un arbre AVL, les cas les plus déséquilibrés sont évités.

Si votre arborescence doit être lue de nombreuses fois et ne sera pas modifiée après sa création, il peut être intéressant de prendre du temps supplémentaire pour une arborescence AVL totalement équilibrée. De plus, l’arbre rouge-noir nécessite un bit de stockage supplémentaire pour chaque nœud, ce qui donne la "couleur" du nœud.

Pour équilibrer un arbre AVL, je viens d’écrire un ensemble de fonctions que je pensais partager avec tout le monde ici. Je suppose que cette implémentation est sans faille. Les questions / questions / critiques sont bien sûr les bienvenues:

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

Etant novice chez Stackoverflow, j’ai essayé de poster mon code ici, mais j’étais bloqué par des problèmes de formatage. Donc, téléchargé le fichier sur le lien ci-dessus.

A bientôt.

l'implémentation complète de l'arborescence avl à auto-équilibrage @ http: // code.google.com/p/self-balancing-avl-tree/ . il implémente également des opérations de concaténation et de scission temporelles logarithmiques, ainsi que des collections de cartes / cartes multiples

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top