arbre Réarrangez utilisant des étiquettes

Question

Considérons un arbre (non ordonnée) dans lequel les noeuds sont étiquetés de 0 à n, avec le noeud racine toujours marqué 0.

Je souhaite construire un arbre séparé, dans lequel le parent de chaque non -noeud m est son ancêtre le plus proche avec un libellé inférieur à m.

Par exemple, étant donné cet arbre:

la puissance requise est:

Notez que le nœud 2 a une étiquette inférieure à celle de son parent 5, il se déplace l'arbre le noeud 4 est inférieure à son parent 7 et son grand-parent 5 de sorte qu'il se déplace dans l'arbre pour son grand-parent 0.

L'approche naïve consiste à traiter chaque noeud indépendamment, traversant vers le haut jusqu'à ce que l'on rencontre une étiquette inférieure. Cela devient très coûteux pour des situations telles que:

Il se sent comme il devrait y avoir un algorithme de sous-quadratique assez simple pour le traitement d'une telle réorganisation, mais je ne peux pas formuler le droit concoction ou même trouver un ordre traversal évident pour minimiser la quantité de traitement redondant. Est-ce un problème commun avec une solution bien définie?

Answer 1

L'algorithme sera le suivant:

1. REGLER 0 comme la racine d'un arbre
2. effectuer DFS sur l'arbre d'origine.
3. effectuer une injection récursive.

injection récursif (noeud, parent):

1. si le noeud parent supérieur, injecter comme enfant du parent.
2. injecter autrement récursif (nœud, parent.parent)