Arbre de recherche binary parfaitement équilibré

J’ai une question théorique sur la Balanced BST .

Je voudrais construire un Perfect Balanced Tree qui a 2^k - 1 nœuds, à partir d’un unbalanced BST régulier. La solution la plus simple à laquelle je peux penser consiste à utiliser une Array/Linked list sortingée, à diviser de manière récursive le tableau en sous-tableaux et à en créer un Perfect Balanced BST .

Cependant, dans le cas de très grandes tailles d’arbre, il faudra créer un Array/List de la même taille pour que cette méthode consum beaucoup de mémoire.

Une autre option consiste à utiliser AVL fonctions de rotation AVL , à insérer élément par élément et à équilibrer l’arbre avec des rotations en fonction du facteur d’équilibre de l’arbre – trois hauteurs des sous-arbres gauche et droit.

Mes questions sont, ai-je raison sur mes hypothèses? Existe-t-il un autre moyen de créer une BST parfaite à partir d’une BST déséquilibrée?

Je n’ai pas encore trouvé de très bonne situation pour avoir besoin d’un arbre de recherche parfaitement équilibré. Si votre cas en a vraiment besoin, j’aimerais en entendre parler. Habituellement, il est préférable et rapide d’avoir un arbre presque équilibré.

Si vous avez un grand arbre de recherche, jeter toute la structure existante n’est généralement pas une bonne idée. L’utilisation de fonctions de rotation est un bon moyen d’obtenir un arbre plus équilibré tout en préservant la majeure partie de la structure existante. Mais normalement, vous utilisez une structure de données appropriée pour vous assurer de ne jamais avoir un arbre complètement déséquilibré. Soi-disant arbres auto-équilibrant.

Il existe par exemple un arbre AVL, un arbre rouge-noir ou un arbre splay, qui utilisent des variantes de rotation légèrement différentes pour maintenir l’arbre en équilibre.

Si vous avez vraiment un arbre totalement déséquilibré, vous pourriez avoir un problème différent. – Dans votre cas, le faire tourner en AVL est probablement la meilleure façon de le réparer.

AVL et les arbres similaires ne sont pas parfaitement équilibrés, je ne suis donc pas sûr de leur utilité dans ce contexte.

Vous pouvez créer une liste doublement chaînée à partir de nœuds d’arborescence, en utilisant des pointeurs left et right au lieu de pointeurs forward et backward . Triez cette liste et construisez l’arborescence de manière récursive de bas en haut, en parcourant la liste de gauche à droite.

Construire un arbre de taille 1 est sortingvial: il suffit de séparer le noeud le plus à gauche de la liste.

Maintenant, si vous pouvez construire un arbre de taille N , vous pouvez également construire un arbre de taille 2N+1 : créez un arbre de taille N , puis coupez un seul nœud, puis un autre arbre de taille N Le nœud unique sera la racine de votre plus grand arbre et les deux plus petits seront ses sous-arbres gauche et droit. Comme la liste est sortingée, l’arborescence est automatiquement une arborescence de recherche valide.

Ceci est facile à modifier pour les tailles autres que 2^k-1 .

Mise à jour: puisque vous démarrez à partir d’un arbre de recherche, vous pouvez construire une liste sortingée directement à partir de celui-ci dans un espace temporel O(log N) espace O(log N) (peut-être même dans l’espace O(1) avec un peu d’ingéniosité), et l’arbre de bas en haut également en temps O(N) et en espace O(log N) (ou O(1) ).

Si vous êtes limité en mémoire, vous pouvez utiliser les opérations de scission et de jointure qui peuvent être effectuées sur une arborescence AVL en un temps O (log n), et je crois un espace constant.

Si vous pouviez également gérer les statistiques des commandes, vous pouvez diviser la médiane, rendre les LHS et les RHS parfaits, puis rejoindre.

Le pseudo-code (pour une version récursive) sera

 void MakePerfect (AVLTree tree) { Tree left, right; Data median; SplitOnMedian(tree, &left, &median, &right); left = MakePerfect(left); right = MakePerfect(right); return Join(left, median, right); } 

Cela peut être implémenté en temps O (n) et en espace O (log n), je crois.