Arborest

Se poate observa usor ca atunci cand modificam tatal unui nod, este cel mai bine sa il modificam in radacina arborelului, 1. Putem cauta binar adancimea maxima a arborelui. Vrem ca pentru o anumita adancime maxima q sa aflam nr numarul de mutari necesar pentru a aduce arborele la adancimea maxima q. Daca nr > K atunci q este prea mic. Altfel q poate scadea in continuare. Pentru a afla nr vom proceda in felul urmator. Fie Di distanta de la radacina la nodul i. Sortam toate nodurile descrescator dupa Di. Parcurgem nodurile in ordinea sortarii. Sa zicem ca ne aflam la nodul x. Daca Dx > q atunci nodul x trebuie urcat. Dar pentru ca nodul x este cel mai de jos nod neurcat inca, vrem sa ducem nodul x la nivelul q schimband tatal celui de al q-1-lea tata al lui x. Facem acest lucru pentru a ridica cat mai multe noduri deasupra nivelului q. Fie T al q-1-lea tata al lui x. Pentru a urca intreg subarborele lui T parcurgem acest surarbore si marcam toate nodurile din subarbore ca fiind vizitate. Incrementam nr. Cand trecem la urmatorul nod ce trebuie ridicat, trebuie sa verificam in plus daca a fost vizitat (daca a fost in subarborele vreunui nod ridicat) ca sa stim ca nu trebuie ridicat. Trebuie de asemenea sa avem grija ca atunci cand parcurgem subarborele unui nod ce trebuie ridicat, sa nu revizitam nodurile ce au fost ridicate inainte pentru ca este inutil (sa nu parcurgem subarborii deja ridicati ai subarborelui ce vrem sa il ridicam in acest moment pentru ca nu este necesar; acest lucru ar duce la o complexitate mult mai mare).

Aceasta abordare duce la o complexitate N log N.