BPC-ALD - Skripta_rev2019_2

Zřejmě po přidání uzlu do předchůdce v něm může dojít rovněž k jeho přeplnění, pokud předtím 
byl zcela zaplněn. To se řeší stejným způsobem – rozdělením tohoto uzlu na tři části s počtem 
prvků  p+1+p.  Dvě  jeho  části  s p  prvky  budou  tvořit  nové  uzly  a  zbývající  prostřední  prvek 
vložíme do jeho předchůdce. Takto postupujeme směrem nahoru, až buďto narazíme na uzel, u 
kterého  po  vložení  dalšího  prvku  nedojde  k přeplnění,  anebo  se  nakonec  dostaneme  až  ke 
kořenu. Pokud i u něho dojde k přeplnění, rozdělí se a střední prvek v tomto rozdělení bude nyní 
nový kořen. V této situaci dojde ke zvětšení výšky stromu. 

Nový prvek 
přidáme do 
listového uzlu B-
stromu. 

− 76 − 

Příklad. K následujícímu B-stromu (r=4) 

přidáme prvek 17. Následující obrázek ukazuje postup vyhledání příslušného místa, kam prvek 
patří, a vložení prvku. 

Protože list, do kterého byl prvek 17 vložen, nyní obsahuje 5 prvků, je zapotřebí ho popsaným 
způsobem rozdělit. 

Je  zřejmé,  že  nyní  je  přeplněn  předchozí  uzel,  do  něhož  byl  přesunut  střední  prvek 
z rozděleného listu. Je zapotřebí rozdělit i tento uzel. 

− 77 − 

Postup odebrání prvku 

Chceme-li  z B-stromu  odebrat  prvek,  znamená  to  vyhledat  uzel,  ve  kterém  se  prvek  nachází,  
prvek z něho odstranit a následně ověřit, zda odebráním prvku nepoklesl počet prvků v daném 
uzlu pod přípustnou mez, a pokud ano, je nutné to vyřešit. 

1.  Odebrání prvku 

Označme odstraňovaný prvek x. Provedeme jeho vyhledání ve stromu. Použijeme k tomu běžný 
algoritmus pro vyhledání. Ten může skončit třemi způsoby: