AVL strom

O(log n)

AVL strom je samovyvažovací binární vyhledávací strom. V každém uzlu si drží výšku a po vložení vyjde zpět ke kořeni a kontroluje vyvažovací faktor každého uzlu — výšku levého podstromu mínus pravého. Když ten kdy přesáhne 1, je uzel příliš nakloněný a napraví ho rotace: jedna rotace u případů LL nebo RR, dvojitá (nejdřív rotace potomka) u LR nebo RL. Tyhle lokální přestavby drží výšku celého stromu do ~1,44·log₂(n), takže hledání, vkládání i mazání jsou zaručeně O(log n) — na rozdíl od prostého BST, který na seřazeném vstupu zdegeneruje na řetěz O(n). Sleduj, jak strom zapadne zpět do rovnováhy s každou vloženou hodnotou.

Binární vyhledávací strom
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Vlož hodnotu jako u běžného BST a zapamatuj si cestu dolů.
  2. Vyjdi zpět nahoru a aktualizuj výšku každého předka.
  3. Kde se podstromy uzlu liší ve výšce o víc než jedna, vyvaž rotací.
  4. LL/RR potřebují jednu rotaci; LR/RL nejdřív otočí potomka, pak uzel.

Pseudokód

1avlInsert(v):                       # O(log n)2  insert v like a normal BST, remembering the path3  walk back up the path, updating heights:4    balance = height(left) − height(right)5    if balance > 1:  rotate right (LL), or left-then-right (LR)6    if balance < −1: rotate left (RR), or right-then-left (RL)7  → height stays O(log n), so search never degrades