Rotație (computer)
Rotația este, în informatică , o procedură implementată pe un arbore de căutare binar pentru a-l echilibra fără a afecta regulile de ordonare ale elementelor sau nodurilor arborelui .
Domeniul de aplicare
Rotația funcționează mișcând de fiecare dată un nod în sus și un nod în jos în structura arborelui. Se folosește pentru a schimba forma copacului și în special pentru a scădea înălțimea acestuia pentru a îmbunătăți echilibrul arborelui în sine. Acest lucru se face prin mutarea subarborilor mai mici în locații inferioare și subarburi mai mari în locații mai înalte. Beneficiile acestui proces sunt resimțite în multe operații obișnuite în arborii de căutare binară (de exemplu inserarea și eliminarea).
Reguli de sortare
Atribuită valoarea rădăcină și dat un nod care conține o valoare x pentru a fi inserat în arbore, dacă nodurile arborelui conțin numere, regulile de sortare ale unui arbore de căutare binară sunt următoarele: începeți de la rădăcină și mergeți la stânga dacă x este mai mic decât rădăcina și spre dreapta dacă x este mai mare decât rădăcina. După acest pas, procedăm în același mod până când întâlnim un nod care nu are ambii copii. În acel moment nodul care conține datele x este poziționat și procesul se încheie.