(a,b)-strom
Z Wikipedie, otevřené encyklopedie
(a,b)-strom je stromová datová struktura. Operace přidání, vyjmutí i vyhledávání probíhají amortizovaně v logaritmicky omezeném čase.
Obsah |
[editovat] Formální definice
Nechť a, b jsou přirozená čísla, a <= b. Strom je (a,b)-strom, když platí:
- Každý vnitřní vrchol kromě kořene má alespoň a a nejvýše b potomků.
- Kořen má nejvýše b potomků. Pokud a >= 2, pak má alespoň 2 syny, nebo je listem.
- Všechny cesty z kořene do listu jsou stejně dlouhé.
[editovat] Operace nad (a,b)-stromy
(a,b)-stromy podporují nejen operace přidání, vyjmutí a vyhledání, ale při správné implementaci i
- nalezení k-tého nejmenšího prvku, rozdělení na dva stromy podle určité hodnoty
- spojení dvou stromů, kdy jeden obsahuje prvky menší než druhý
a to opět v logaritmickém čase.
Pomocí (a,b)-stromů - nejlépe (2,3)-stromů lze i třídit, toto třídění probíhá v čase O(n) až O(nlogn), podle toho, jak moc utříděná je vstupní posloupnost. Vyžaduje ovšem více prostoru, proto se hodí pouze pro předtříděné posloupnosti, když je důraz kladen na rychlost.
