Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

5.8. B-fák

5.8. B-fák

5.20. Definíció. A B-fa egy olyan gyökeres fa, amely rendelkezik a következő

tulajdonságokkal:

Minden csúcsnak a következő mezői vannak:

Az az csúcsban tárolt kulcsok darabszáma. Az darab kulcs (nemcsökkenő sorrendben) . A egy logikai változó, melynek az értéke , ha levél, és , ha egy belső csúcs.

Ha belső csúcs, akkor tartalmazza a mutatókat, melyek az gyerekeire mutatnak. A levél csúcsoknak nincsenek gyerekei és így e mezők definiálatlanok.

A értékek meghatározzák a kulcsértékek azon tartományait, amelyekbe a részfák kulcsai esnek. Ha ki egy olyan kulcs, amelyik a gyökerű részfában van, akkor .

Minden levélnek azonos a mélysége, ez az érték a fa magassága

A csúcsokban található kulcsok darabszámára adott egy alsó és egy felső korlát. Ezeket a korlátokat egy rögzített egész számmal () lehet kifejezni, és ezt a számot a B-fa minimális fokszámának nevezzük.A. Ezért minden nem gyökér csúcsnak legalább kulcsa van. Minden belső csúcsnak legalább gyereke van. Ha a fa nem üres, akkor a gyökércsúcsnak legalább egy kulcsának kell lennie. Minden csúcsnak legfeljebb kulcsa lehet. Tehát egy belső csúcsnak legfeljebb gyereke lehet. Azt mondjuk, hogy egy csúcs telített, ha pontosan kulcsa van.

Ha , akkor a B-fa neve 2-3-4 fa.

5.21. Tétel. Ha , és T egy olyan -kulcsos B-fa, amelynek magassága és minimális fokszáma , akkor