(a, b) -strom - (a,b)-tree

v počítačová věda, an (a, b) strom je druh vyváženého vyhledávací strom.

Strom (a, b) má všechny své listy ve stejné hloubce a všechny vnitřní uzly kromě kořene mají mezi A a b děti, kde A a b jsou celá čísla taková 2 ≤ A ≤ (b+1)/2. Kořen má, pokud to není list, mezi 2 a b děti.

Definice

Nechat A, b být kladná celá čísla taková 2 ≤ A ≤ (b+1)/2. Pak zakořeněný strom T je strom (a, b), když:

• Každý vnitřní uzel kromě kořene má alespoň A a nanejvýš b děti.
• Kořen má maximálně b děti.
• Všechny cesty od kořene po listy jsou stejně dlouhé.

Reprezentace interního uzlu

Každý interní uzel proti stromu (a, b) T má následující zastoupení:

• Nechat ${displaystyle ho _ {v}}$ být počet podřízených uzlů uzlu proti.
• Nechat ${displaystyle S_ {v} [1 dot ho _ {v}]}$ být ukazateli na podřízené uzly.
• Nechat ${displaystyle H_ {v} [1 dot ho _ {v} -1]}$ být soubor klíčů takový, že ${displaystyle H_ {v} [i]}$ se rovná největšímu klíči v podstromu, na který ukazuje ${displaystyle S_ {v} [i]}$.

Viz také

• B-strom
• 2-3 strom
• 2-4 strom

Reference

• Tento článek zahrnuje public domain materiál zNIST dokument:Černý, Paul E. „(a, b) -strom“. Slovník algoritmů a datových struktur.

Tento algoritmy nebo datové struktury související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.