Comment équilibrer l'arbre avec une seule branche?

Si nous avions, disons, des nœuds de valeur 10, 9 ... 1 disposés par ordre décroissant sur une seule branche gauche, comment pourrions-nous effectuer des rotations sur l'arbre pour en faire un arbre AVL équilibré? Je pensais répéter des rotations droites simples, mais quelqu'un pourrait-il montrer la séquence des étapes ici?Comment équilibrer l'arbre avec une seule branche?

Source

2017-10-02 Y. P

Vous pouvez inverser l'arborescence de branches unique de gauche pour créer une seule arborescence de branches droite (appelée vigne), puis convertir la vigne en arborescence. Lien vers [rebalance tree.pdf] (http://web.eecs.umich.edu/~qstout/pap/CACM86.pdf). – rcgldr

Faire les rotations à la racine jusqu'à ce que 5 soit en haut. L'arbre est maintenant à l'envers V. Maintenant, faites une opération similaire sur chacun des deux sous-arbres et ainsi de suite.

Source

2017-10-02 08:29:07 Henry

Comment équilibrer l'arbre avec une seule branche?

Répondre

Questions connexes