Équilibrer un arbre binaire (AVL)

un arbre de bouc émissaire a peut-être l'algorithme le plus simple de détermination de l'équilibre à comprendre. Si une insertion provoque une trop grande profondeur du nouveau noeud, celui-ci trouve un noeud autour duquel se rééquilibrer, en regardant la balance de poids plutôt que la balance de hauteur. La règle pour savoir si rééquilibrer sur supprimer est aussi simple. Il ne stocke aucune information d'arcane dans les noeuds. C'est plus compliqué de prouver que c'est correct, mais on n'a pas besoin de ça pour comprendre l'algorithme...

Cependant, contrairement à une AVL il n'est pas à la hauteur équilibrée à tous les temps. Comme rouge-noir son déséquilibre est limité, mais contrairement rouge-noir il est accordable avec un paramètre, donc pour la plupart des fins pratiques il semble aussi équilibré que vous avez besoin qu'il soit. Je soupçonne que si vous l'accordez trop étroitement, cependant, il finit comme mauvais ou pire que AVL pour le pire des cas insertions.

réponse à la question Modifier

je fournirai mon chemin personnel pour comprendre les arbres AVL.

vous devez d'Abord comprendre ce qu'est une rotation d'arbre, alors ignorez tout ce que vous avez déjà entendu les algorithmes AVL et comprenez cela. Obtenez directement dans votre tête qui est une rotation droite et qui est une rotation gauche, et ce que chacun fait à l'arbre, ou bien les descriptions des méthodes précises ne fera que vous confondre.

ensuite, comprendre que l'astuce pour équilibrer les arbres AVL est que chaque noeud enregistre en elle la différence entre la hauteur de ses sous-arbres gauche et droite. La définition de 'height balanced' est que ceci est entre -1 et 1 inclus pour chaque noeud de l'arbre.

ensuite, comprenez que si vous avez ajouté ou enlevé un noeud, vous avez peut-être déséquilibré l'arbre. Mais vous ne pouvez avoir modifié l'équilibre des nœuds qui sont les ancêtres du nœud que vous avez ajouté ou supprimé. Donc, ce que vous allez faire est de travailler votre chemin de retour vers l'arbre, en utilisant des rotations pour équilibrer tous les noeuds déséquilibrés que vous trouvez, et en mettant à jour leur score d'équilibre, jusqu'à ce que l'arbre est équilibré encore.

la dernière partie de la compréhension c'est de chercher dans une référence décente les rotations spécifiques utilisées pour rééquilibrer chaque noeud que vous trouvez: c'est la "technique" de celui-ci par opposition au concept haut. Vous n'avez qu'à vous souvenir des détails lors de la modification du code de l'arbre AVL ou peut-être lors des examens de structure des données. Cela fait des années que je n'ai pas eu de code AVL aussi ouvert dans le débogueur - les implémentations ont tendance à aller jusqu'à un point où elles fonctionnent et restent ensuite opérationnelles. Donc je n'ai vraiment pas rappeler. 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 a pas beaucoup). Le meilleur de le regarder.

puis il y a le travail de traduire tout cela en code.

Je ne pense pas que regarder les listes de codes aide beaucoup avec n'importe quelle étape sauf la dernière, alors ignorez-les. Même dans le meilleur des cas, où le code est clairement écrit, il ressemblera à une description classique du processus, mais sans les diagrammes. Dans un cas plus typique, c'est un gâchis de manipulation de structures. Donc, il suffit de coller à ces livres.