BPC-ALD - Skripta_rev2019_2

− 78 − 

b)  List v má jen přímé sousedy, které mají právě p prvků. Pak vytvoříme nový list s r prvky 

tak, že sloučíme 

prvky z listu v   +   prvek z předchůdce   +   prvky ze souseda  . 

Následující  obrázek  ukazuje  toto  sloučení  opět  pro  oba  možné  sousedy  -  levého  i  pravého 
(prvku uzlu v jsou značeny písmenem c). 

Je zřejmé, že tímto ubyl jeden prvek v předchůdci. Pokud tento má nyní jen p-1 prvků, řeší se to 
analogicky v závislosti na tom, kolik prvků mají jeho přímí sousedé. Takto se můžeme případně 
dostat  až  k uzlu,  který  je  následníkem  kořene.  Pokud  je  vytvořen  nový  uzel  sloučením  s  jeho 
přímým  sousedem  a  pokud  kořen  v této  chvíli  má  jen  jeden  prvek,  dojde  přitom  k vytvoření 
nového kořene a zároveň ke snížení výšky stromu. Na následujícím obrázku je tato situace pro 
případ, kdy je pro sloučení vzat levý přímý soused. 

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

− 79 − 

odebereme prvek 17. Po odstranění prvku z daného listu zůstane jen prvek 15. Tento list má ale 
levého  přímého  souseda,  který  má  více  než  2  prvky.  Proto  provedeme  přesun  prvku  9  z  jeho 
levého souseda do předchůdce a prvku 12 z předchůdce do listu s prvkem 15. 

Odebereme dále prvek 15. V listu zůstane opět jen jeden prvek 12. Liste už ale nemá žádného 
přímého souseda, z kterého by se dal přesunout prvek, proto provedeme sloučení se sousedním 
listem. Vybereme si k tomu třeba pravého souseda. 

Při slučování byl odebrán prvek z předchůdce, ve kterém tímto zůstal jen jeden prvek 9. Tento 
uzel má ale pravého přímého souseda, který má více než dva prvky, čímž můžeme z něho prvek 
přesunout.  Celý  přesun  se  provede  tak,  že  do  uzlu  s prvkem  9  se  přesune  prvek  z jeho 
předchůdce (v tomto případě kořene) a na volné místo v předchůdci se přesune onen zmíněný 
prvek  ze  souseda.  Přitom  se  příslušně  přesune  i  ukazatel  na  jeho  následníka  –  list  s prvky 
52,53,58.