Équilibrer un arbre de recherche ternaire

Question

Comment aborde-t- « équilibre » un arbre de recherche ternaire? La plupart des implémentations de tst faire l'équilibrage d'adresse non, mais propose d'insérer dans un ordre optimal (que je ne peux pas contrôler.)

Answer 1

L'article Dr Dobbs sur le ternaires Recherche arbres dit: D.D. Sleator et R.E. Tarjan décrire des algorithmes d'équilibrage théoriques pour les arbres de recherche ternaires dans « autoréglable arbres binaires de recherche » (Journal de l'ACM, Juillet 1985). Vous pouvez trouver des versions en ligne de cet article avec votre moteur de recherche préféré.

Answer 2

Une optimisation simple est de faire un arbre rouge-noir, ce qui permet d'éviter certains scénarios les plus défavorables. TST sont vraiment juste arbres binaires où la valeur d'un noeud donné est une autre TST. Ainsi, le « milieu » enfant d'un noeud n'est pas vraiment partie de l'arbre qui est équilibré à chaque niveau, car il ne peut pas passer à un autre parent de toute façon.

Cela garantit que chaque niveau de la structure arborescente est traversée dans le journal (R) du temps, bien que vous pourriez probablement faire encore mieux en prenant en compte la taille des subtries à chaque noeud. Cela semble être beaucoup plus compliqué si!

Answer 3

Une généralisation de l'arbre de recherche binaire est le B-Tree , qui travaille pour fanouts partout de 2 ans et plus. Ce n'est pas la seule façon de le faire, mais il est une commune.

À peu près la façon dont il fonctionne est si une insertion ou de suppression mettrait l'arbre hors de l'équilibre, il vole un élément ou un espace à partir d'un noeud voisin. Si même cela ne suffit pas de garder l'arbre en équilibre, sa hauteur par sera modifiée pour faire de la place.

Answer 4

lire cet article:

« autoréglable de ternaires Recherche L'utilisation conditionnelle Rotations essais et répartition aléatoire Heuristique » par "Ghada Hany Badr * et B. John Oommen †"

il vous aidera à comprendre l'auto-réglage et l'équilibrage TST.