(a,b)-strom

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

(a,b)-strom je stromová datová struktura.

Definice[editovat | editovat zdroj]

Nechť a, b jsou přirozená čísla, 2 ≤ a ≤ (b+1)/2. Strom je (a,b)-strom, když platí:

  • Kořen má nejméně dva potomky a nejvýše b potomků, není-li listem.
  • Všechny vnitřní vrcholy kromě kořene mají alespoň a a nejvýše b potomků.
  • Všechny listy jsou na stejné úrovni, tzn. všechny cesty z kořene do libovolného listu mají stejnou délku.

Význam[editovat | editovat zdroj]

Třída (a,b)-stromů má jen teoretický význam. V praxi se využívá podmnožina (a,b)-stromů, B-stromy.

Odkazy[editovat | editovat zdroj]

Související články[editovat | editovat zdroj]

Zdroje[editovat | editovat zdroj]

  • Paul E. Black: (a,b)-strom v encyklopedii algoritmů a datových struktur, U.S. National Institute of Standards and Technology, 6. 10. 2004