Y at-il une mise en œuvre d'un arbre de recherche binaire annotée avec la taille sous-arbre

Question

J'ai fait des recherches sur la structure de données d'arbre décrit à ce lien (vers le bas):

http://sigpipe.macromates.com/2009/08 / 13 / maintien-a-layout /

Il est mentionné que cette structure de données pourrait être un arbre de doigt. Cependant, après plus de recherche autour des arbres des doigts, j'ai trouvé que ce manque les « doigts » qui fait des arbres arbres doigts des doigts. Il semble plutôt cela est juste un arbre binaire annoté (annoté avec la taille de sous-arbre).

Connaissez-vous une implémentation existante (dans toutes les langues) de cette structure de données que je pourrais utiliser comme référence pour ma propre mise en œuvre (bien que, de préférence pas une mise en œuvre dans un langage de programmation fonctionnelle )?

Ou, quelle serait la façon la plus optimale des annotations de modernisation taille de sous-arbre dans un arbre existant structure de données?

Merci!

Answer 1

Simon B-Comptées Les arbres de Tatham sont similaires. si le comptage de noeud est remplacée par une largeur de mémoire tampon comme dans tweak , ceux-ci fournissent des opérations comme cordes .

, en fait, à la lecture que la page vous référencez je vois qu'il a été utilisé comme une table de pièce ou d'une table de ligne pour un éditeur

dans le document, positionnel Delta arbres pour concilier les mises à jour avec le stockage de données en lecture optimisée , les auteurs présentent un arbre dont le comportement en ce qui concerne les invariants qu'il détient entre les nœuds de l'arbre met à nu une ressemblance frappante avec enfilades de Xanadu auquel le B-tree compté est également similaire.

Answer 2

J'ai un projet sur github appelé qui vise à fournir un soutien générique pour les annotations comme nombre de sous-arbre dans Boost.Intrusive. comte était sous-arbre mon cas original usage.

Actuellement, il faut 11 modèles variadique C et de ne supporte que le rbtree, mais cela fonctionne, et j'espère retirer ces deux restrictions dans le temps Mise à jour : construit maintenant avec C ++ 03. soutient encore que rbtree.

Lorsqu'il est utilisé avec une annotation nombre est sous-arbre il semblable à ce que décrit jordan dans la réponse ci-dessus - il calcule (gauche + droite + 1) à chaque noeud. La mise en œuvre est tout à fait différent - il fonctionne avec un nœud et / ou traits valeur; les mises à jour d'annotation sont intégrées dans les algorithmes de rbtree au lieu, ce qui maintient le nombre de recalculs fait un minimum.

Answer 3

Je l'ai mis en œuvre quelque chose de similaire basé sur une question que je posais l'autre jour. Je annotations ajouté au boost :: :: intrusive rbtree / noeuds avltree pour calculer la taille de chaque sous-arbre (comptage de noeud foreach = node-> gauche> count + node-> droite> count + 1). J'effectuer cette mise à jour lors de l'insertion / deletetion / rééquilibrage de l'arbre à l'aide d'un crochet de l'impulsion pour set_parent, set_left et set_right. Quasiment, comme indiqué dans le site que vous avez mentionné, après chaque mise à jour de nœud, mettez à jour la taille du noeud courant, puis parcourir l'arbre jusqu'à ce que vous frappez la racine, la mise à jour de la taille de chaque nœud que vous allez.

Le problème vient quand vous voulez insérer dans l'arbre à une position spécifique. À peu près au moment où vous faites cela, vous invalidez l'invariant clé commande pour la structure de l'arbre. Cela signifie que vous ne sera pas en mesure d'effectuer des recherches efficaces O (log n) par clé. Mais, si vous voulez, vous ne serais probablement pas besoin de la taille des annotations de toute façon.