B-fa

A HupWiki-ből...

Egy kiegyensúlyozott fát B-fának nevezzünk, ha teljesülnek rá a lentebbi feltételek. Egy fa akkor kiegyensúlyozott, ha az összes levele azonos távolságra található a fa gyökerétől.

A fa minden csúcsánál eltároljuk a következő értékeket:

• a csúcshoz tartozó kulcsok számát és a kulcsokat
• az adott csúcs levél vagy belső csúcs
• ha a csúcs belső, akkor a gyerekeire mutató pointereket

A csúcsokban tárolható kulcsok darabszámának (a csúcs fokának) van egy felső és egy alsó korlátja. Bm-fának nevezzük, ha m a felső korlát, és (felsőegészrész)m/2 az alsó. A gyökércsúcsra nem vonatkozik az m/2 alsó korlát, de legalább 2-nek kell lennie a fokának, ha a fa több mint 2 szintes.

FIXME bővítés

• csúcsvágás
• csúcsösszevonás