(a,b)-träd

Inom datavetenskap är ett (a,b)-träd ett slags balanserat sökträd .

Ett (a,b)-träd har alla sina löv på samma djup, och alla interna noder utom roten har mellan a och b barn , där a och b är heltal så att 2 ≤ a ≤ ( b +1) /2 . Roten har, om det inte är ett löv, mellan 2 och b barn.

Definition

Låt a , b vara positiva heltal så att 2 ≤ a ≤ ( b +1)/2 . Då är ett rotat träd T ett (a,b)-träd när:

• Varje inre nod utom roten har minst a och högst b barn.
• Roten har högst b barn.
• Alla vägar från roten till bladen är lika långa.

Intern nodrepresentation

Varje intern nod v i ett (a,b)-träd T har följande representation:

• Låt $\rho _{v}$ vara antalet underordnade noder för nod v .
• Låt $S_{v}[1\dots \rho _{v}]$ vara pekare till underordnade noder.
• Låt $H_{v}[1\dots \rho _{v}-1]$ vara en array av nycklar så att $H_{v [i]$ är lika med den största nyckeln i underträdet som ${\displaystyle S_{v}[i]} pekar på$ .

Se även

• B-träd
• 2-3 träd
• 2-4 träd

• Den här artikeln innehåller material som är allmän egendom från Paul E. Black. "(a,b)-träd" . Ordbok över algoritmer och datastrukturer . NIST .