(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)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.

[editovat] Podívejte se také

[editovat] Reference

V jiných jazycích