Quelle est la manière la plus propre d'étendre cette conception pour la réécriture d'arbres?

Question

J'ai un arbre d'objets, où chaque objet a std::vector des pointeurs vers ses enfants. La classe de l'objet a une méthode rewrite() qui est récursive appliquée pour modifier l'objet et ses enfants, typiquement avec les transformations suivantes, où [N] est l'objet en cours de réécriture et (M) est l'élément qui rewrite() rendements:

 
       (A) 
[A]   /\    [A] 
/\  --> B X    | --> (B) 
B C    \    B 
         C 

Quelle est la manière la plus propre d'étendre cette configuration pour permettre des transformations comme celle-ci?

 
    A    X 
    |   /\ 
    [B] --> C A 
    |    | 
    C    (Y) 

C'est, ceux qui re-racine de l'arbre, déplacer un élément, insérer un nouvel élément, et le retour de l'élément inséré. J'ai du mal à trouver quelque chose de sympa qui implique aussi un refactoring minimal. Pensées?

Answer 1

On dirait que, pour la rapidité, vous aurez besoin d'un "back-pointeur" de chaque nœud enfant vers son nœud parent. De cette façon, vous pouvez suivre la chaîne de pointeurs parents avec un pointeur vers n'importe quel noeud jusqu'à la racine, si c'est ce dont vous avez besoin (je ne sais pas comment vous avez prévu de trouver la racine juste un pointeur vers un noeud interne , sans backpointers?). Bien sûr, vous aurez besoin d'ajuster le pointeur arrière, ainsi que les "enfants" std::vector, chaque fois que vous réorganiser l'arbre - une conséquence malheureuse de la légère duplication de l'information (pas plus que, disons, une liste doublement chaînée présente ;-), mais un petit prix à payer pour la facilité et la rapidité d'une telle navigation bidirectionnelle.