Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

5.7. 2-3-fák

5.7. 2-3-fák

5.18. Definíció. 2-3-fa

A 2-3-fa egy gyökeres fa az alábbi tulajdonságokkal:

A rekordok a fa leveleiben helyezkednek el, a kulcs értéke szerint balról jobbra növekvő sorrendben. Egy levél egy rekordot tartalmaz.

Minden belső (nem levél) csúcsnak 2 vagy három gyereke van. A csúcs szerkezete: , vagy ahol (. Az mutató szerinti részfában minden kulcs kisebb, mint , az mutató szerinti részfa legkisebb kulcsa , és minden kulcs ott kisebb, mint (ha van a csúcsban), az mutató (ha van) szerinti részfában a legkisebbkulcs .

A fa levelei a gyökértől egyforma távolságra vannak.

5.19. Tétel.

Ha a 2-3-fának szintje van, akkor a levelek száma legalább .

Fordítva: ha a tárolt rekordok száma , akkor

Keresés 2-3-fában: A gyökértől elindulva a belső csúcsokban 1 vagy 2 összehasonlítás után tovább lehet menni egy szinttel lejjebb. A műveletigény .