Binary search tree

avg O(log n)

Binární vyhledávací strom (BST) ukládá hodnoty tak, že pro každý uzel je celý levý podstrom menší a celý pravý větší. Toto uspořádání umožňuje, aby insert, search i delete šly jednou cestou od kořene k listu — v průměru O(log n) u vyváženého stromu, ale O(n), když zdegeneruje do řetězu. Mazání uzlu se dvěma potomky nahradí uzel jeho in-order následníkem.

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

Jak to funguje

  1. Pro vložení i hledání začni v kořeni a jdi vlevo, když je hodnota menší, vpravo, když větší.
  2. Insert vloží hodnotu do prvního prázdného místa, na které narazí.
  3. Search skončí shodou s uzlem, nebo když spadne mimo strom.
  4. Delete vyřízne uzel; uzel se dvěma potomky nahradí in-order následníkem.

Pseudokód

1insert(v):                          # avg O(log n)2  walk from the root: go left if v < node, else right3  drop v into the first empty spot45search(v):6  walk the same way until v is found or you fall off78delete(v):9  0 / 1 child: splice the node out10  2 children: replace it with its in-order successor