Comment va-t-on équilibrer un arbre de recherche ternaire? La plupart des implémentations de tst n'abordent pas l'équilibrage, mais suggèrent d'insérer dans un ordre optimal (que je ne peux pas contrôler.)Equilibrer un arbre de recherche ternaire
L'article dans Dr. Dobbs à propos de Ternary Search Trees dit: D.D. Sleator et R.E. Tarjan décrit des algorithmes d'équilibrage théoriques pour les arbres de recherche ternaires dans "Arbres de recherche binaire à auto-ajustement" (Journal of the ACM, juillet 1985). Vous pouvez trouver des versions en ligne de ce document avec votre moteur de recherche préféré.
Une généralisation de l'arbre de recherche binaire est le B-Tree, qui fonctionne pour les ventilations à partir de 2 et plus. Ce n'est pas la seule façon de le faire, mais c'est une chose courante.
En gros, si une insertion ou une suppression déséquilibre l'arborescence, elle vole un élément ou un espace d'un nœud voisin. Si même cela ne suffit pas à maintenir l'équilibre de l'arbre, sa hauteur sera modifiée pour faire de la place.
Le PO parle d'arbres de recherche ** ternary **. – hmuelner
Je ne suis pas du tout clair sur la façon dont un B-Tree 1-2 diffère d'un arbre ternaire. Pouvez-vous m'expliquer? – SingleNegationElimination
Un arbre B (généralement) contient les clés complètes dans les nœuds. Dans un arbre de recherche ternaire, la clé est définie par le chemin du noeud. – hmuelner
lire cet article:
"autoréglable de ternaires Recherche L'utilisation conditionnelle Rotations essais et Randomized Heuristique" par "Ghada Hany Badr * et B. John Oommen †"
il vous aidera comprendre les TST auto-ajustés et équilibrés.
Quelle est la taille d'un arbre de recherche? –
Un couple de milliers de mots allant de 4 à 20 caractères. Je ne sais pas si c'est grand ou petit, mais c'est grand pour moi. – uroc
Semble jeter l'arbre quand il arrive à un certain point et le remplacer par un arbre construit avec «l'ordre optimal» est votre meilleur pari - devrait prendre des millisecondes, si vous pouvez économiser le temps. –