2-3-træ

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 12. juni 2014; checks kræver 14 redigeringer .

2-3 træ - datastruktur , som er et B-træ , hvor hver node (side) har enten to børn og et felt, eller tre børn og to felter. Bladspidser er en undtagelse - de har ingen børn, men et eller to felter. 2-3 træer er afbalancerede, det vil sige, at alle bladspidser er i samme højde fra træroden.

2-top
3-top

Egenskaber

Alle knudepunkter uden blade indeholder et felt og 2 undertræer, eller 2 felter og 3 undertræer.
Alle bladspidser er på samme niveau (nederste niveau) og indeholder 1 eller 2 felter.
Alle data sorteres (efter princippet om et binært søgetræ ).
Et felt i et 2-vertex, som i et binært søgetræ, deler rummet af mulige værdier i to områder: og $(-\infty ,a)$ $[a,+\infty )$
Felterne i 3-vertexet opdeler rummet med mulige værdier i tre områder: , og $(-\infty ,a)$ $[a, b)$ $[b,+\infty )$

Ikke-blade hjørner

Noder uden blade indeholder et eller to felter, der angiver værdiintervallet i deres undertræer. Værdien af det første felt er strengt taget større end den største værdi i det venstre undertræ og mindre end eller lig med den mindste værdi i det højre undertræ (eller det centrale undertræ, hvis det er et 3-vertex); på samme måde er værdien af det andet felt (hvis nogen) strengt taget større end den største værdi i det centrale undertræ og mindre end eller lig med den mindste værdi i det højre undertræ. Disse ikke-bladspidser bruges til at dirigere søgefunktionen til det ønskede undertræ og til sidst til det ønskede blad.

For at illustrere ovenstående gælder for eksempel følgende uligheder:

for 2-vertex: $p<a\leq q$
for 3-vertex: $p<a\leq q<b\leq r$

Se også

B-træ
Liste over datastrukturer (træer)

Links

Træ (datastruktur)
Binært søgetræ Træ (grafteori) træstruktur
Binære træer	binært træ T-træ
Selvbalancerende binære træer	AA træ AVL træ Rød-sort træ Splay træ træ med bøder kartesisk træ Fibonacci træ B-træ T-træ
B-træer	2-3-træ B⁺-træ B*-træ B x -træ UB træ 2-3-4 træ (a,b)-træ dansende træ
præfiks træer	suffiks træ Komprimeret præfikstræ Ternært søgetræ
Binær opdeling af rummet	k-dimensionelt træ VP træ
Ikke-binære træer	Quadtree oktre Sparsom Voxel Octree eksponentielt træ PQ træ
At bryde rummet op	R-træ Hilbert R-træ R+-træ R*-træ X-træ M-træ Fenwick træ Segmenttræ
Andre træer	dynge hash træ fingertræ metrisk træ Belægning træ BK-træ Dobbeltkædet træ iDistance Linkskåret træ LSM træ
Algoritmer	Bredde først søgning Dybde første søgning DSW algoritme spanning tree protokol