Pourquoi l'algorithme de rotation de l'arbre d'affichage prend-il en compte le nœud parent et grand-parent?

25

Je ne comprends pas très bien pourquoi la rotation dans la structure de données de l'arbre d'affichage prend en compte non seulement le parent du nœud de notation, mais aussi le grand-parent (opération zig-zag et zig-zig). Pourquoi les éléments suivants ne fonctionneraient-ils pas:

Lorsque nous insérons, par exemple, un nouveau nœud dans l'arbre, nous vérifions si nous insérons dans le sous-arbre gauche ou droit. Si nous insérons à gauche, nous faisons pivoter le résultat à DROITE, et vice versa pour le sous-arbre droit. Récursivement, ce serait comme ça

Tree insert(Tree root, Key k){
    if(k < root.key){
        root.setLeft(insert(root.getLeft(), key);
        return rotateRight(root);
    }
    //vice versa for right subtree
}

Cela devrait éviter toute la procédure de "splay", vous ne pensez pas?

Bober02
la source

Réponses:

30

L'algorithme d'équilibrage plus simple peut nécessiter temps amorti par rotation dans le pire des cas. Supposons que l'arbre n'est qu'un chemin totalement déséquilibré pour les bons enfants; aucun nœud n'a d'enfant à gauche. La seule feuille de cet arbre est l'arbre avec la clé maximale. Si vous faites pivoter cette étape étape par étape jusqu'à la racine, vous avez utilisé n - 1 rotations, et l'arbre résultant est toujours totalement déséquilibré.Ω(n)n-1

mauvais exemple pour simplement tourner

n2/2Ω(n)Ω(n)

mauvais exemple a continué

Ce mauvais exemple apparaît dans le papier d'origine de Sleator et Tarjan.

XXX

évitant le mauvais exemple

L'avantage de cet algorithme plus complexe est qu'il amène non seulement le nœud accédé à la racine, mais déplace également chaque ancêtre du nœud accédé à peu près à mi-chemin de la racine , mais ne déplace jamais aucun nœud à plus d'un nombre constant de niveaux de la racine.

O(bûchen)Ω(n)

Plus brièvement: le jeu déplace les nœuds vers le haut rapidement et vers le bas lentement.

JeffE
la source
Je pense que les algorithmes de rotation sont exactement les mêmes, le mien est tout simplement plus court et plus compréhensible. Plutôt que de regarder les grands-parents, je ne considère les parents qu'en une seule rotation. N'est-ce pas exactement le même résultat?
Bober02
Je suppose que vous faites peut-être référence à deux algues SPLAYING, l'une de haut en bas, l'autre de bas en haut, et pas la mienne, est-ce exact? Je faisais référence à mon jeu algo vs bottom up
Bober02