Stromy jsou jednou z esenciálních datových struktur pro ukládání dat. Mezi jejich hlavní výhody patří efektivní prohledávání.
DEFINICE: Strom nazveme binární, pokud je zakořeněný a každý vrchol má nejvýše dva syny, u nichž rozlišujeme, který je levý a který pravý.
Definice
Binární vyhledávací strom (BVS) je binární strom, v jehož každému vrcholu v je uložen unikátní klíč k(v). Přitom pro každý vrchol v musí platit:
pokud a ∈ L(v), pak k(a) < k(v),
pokud b ∈ R(v), pak k(b) > k(v).
Druhy stromu
Vyvážený strom
DEFINICE: pro každý jeho vrchol v platí ||L(v)| − |R(v)|| ≤ 1.
Dokonale vyvážený strom o velikosti n má hloubku ⌊log n⌋ a operace find, insert, min, delete mají časovou složitost O(log n).
Složitost
| Algorithm | Operation | Worst Case |
|---|---|---|
| Space | O(n) | O(n) |
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
Hledání prvku x
BvsFind, Vstup: Koření BVS v, hledáný klíč x
- Pokud v = {}, vrátíme {}.
- Pokud x = k(v), vrátíme v
- Pokud x < k(v), vrátíme BvsFind(l(v), x)
- Pokud x > k(v), vrátíme BvsFind(r(v), x)
Minimum ve stromu
BvsMin, Vstup: Koření BVS v
- Pokud l(v) = {}, vrátíme vrchol v.
- Jinak vrátíme BvsMin(l(v))
Implementace
Uspořádané pole: