SHPORA.net :: PDA

[ Back ]

B-puu



Kahendotsimise puud võib üldistada m>2 juhtumile, lubades ühes puu tipus hoida kuni m-1 kirjet (m on konstant).





m-rajaline otsimispuu on kas:



1. tühi või

2. koosneb juurest, milles hoitakse järjestatuna j võtit (0<=j<m) ning j+1 alampuust, mis kõik peavad olema kas mittetühjad m-rajalised otsimispuud või (kõik) tühjad puud. Juure võtmete k1 <= k2 <= ... <= kj ja alampuude T0, T1, ... , Tj jaoks kehtivad järgmised kitsendused:

1. kõik alampuus T0 esinevad võtmed k ei ületa juure esimest võtit k1: k <= k1

3. kõigi võtmete k jaoks alampuust Ti (0<i<j) kehtib ki <= k <= ki+1

4. kõik alampuus Tj esinevad võtmed k pole väiksemad kui juure viimane võti kj: k >= kj



m-järku B-puu (Bayer, McGreigh) on niisugune m-rajaline otsimispuu, milles



1. kõik lehed on samal tasemel;

2. lehed ei sisalda võtmeid (fiktiivsed, edaspidi jätame joonistel kujutamata);

3. juurel on 2 kuni m alluvat;

4. kõigil teistel vahetippudel on t=ceil[m/2] (t>=2) kuni m alluvat.



Seega on juures 1 kuni m-1 võtit, vahetippudes t-1 kuni m-1 võtit.





Tipp on täitunud, kui ta sisaldab m-1 võtit.



Kõrgus h <= log t ((n+1)/2)



Mahutavus n ~ O (2*(m/2)h)



3-järku B-puu = 2-3 puu (igal vahetipul 2 või 3 alluvat).



Otsimine: O(th)

Lõigu "poolitamise" asemel otsitakse õigest alamlõigust (igal sammul kuni m valikut, kuni h sammu).