Nouvelle mise en œuvre des arbres AVL

Question

Je suis en train d'écrire un algorithme de compression de fenêtre coulissante (LZ77) qui recherche des expressions dans un dictionnaire « mobile ».

Jusqu'à présent, je l'ai écrit un BST où chaque noeud est stocké dans un tableau et son index dans le tableau est également la valeur de la position de départ dans la fenêtre elle-même.

Je cherche maintenant à transformer le BST à un arbre AVL. Je suis un peu confus aux implémentations exemples que j'ai vu. Certains apparaissent seulement pour stocker les facteurs d'équilibre alors que d'autres enregistrent la hauteur de chaque arbre.

Y at-il un avantage de performance / inconvénients de stockage de la hauteur et / ou le facteur équilibre pour chaque noeud? Toutes mes excuses si cela est une question très simple, mais je ne suis toujours pas visualisant comment je veux restructurer mon BST pour mettre en œuvre l'équilibrage de la hauteur.

Merci.

Answer 1

L'équilibre est tout simplement la différence entre les deux hauteurs, donc il ne devrait pas y avoir de différences de performances significatives, sauf lorsque la soustraction entier est mis en œuvre très lentement. ;) Le stockage des hauteurs peut nécessiter plus de mémoire si vous les stocker simplement ints, sans compression à la fois en un seul int, que vous pouvez faire en toute sécurité comme l'équilibre garantit une limite pratique à la hauteur maximale. Mais l'optimisation prématurée, vous savez ... Avec les hauteurs vous avez plus d'informations disponibles que vous devez calculer avec une traversal sous-arbre supplémentaire lorsque vous avez seulement le solde disponible, mais cela dépend de vos besoins.

Je recommande une étude approfondie d'une excellente introduction Ben Pfaff à BSTS: http: //www.stanford.edu/~blp/avl/libavl.html/