BPC-ALD - Skripta_rev2019_2

a)  Prvek x nebyl ve stromu nalezen – není co odebrat. 

b)  Prvek x byl nalezen v listovém uzlu. Prvek z uzlu odstraníme. Pokud list je po zrušení prvku 

aspoň z poloviny zaplněn, operace odebrání končí. Jinak přejdeme ke kroku 2. 

c)  Prvek x byl nalezen v uzlu u, který není listem. Prvek x z uzlu odstraníme a na volné místo 

v uzlu  u  přesuneme  buďto  největší  prvek  z jeho  levého  podstromu,  což  je  poslední  prvek 
v nejpravějším  listu  podstromu,  anebo  nejmenší  prvek  z jeho  pravého  podstromu,  což  je 
první prvek v nejlevějším listu podstromu. Pokud list, odkud jsme prvek přesunuli, je stále 
aspoň z poloviny zaplněn, operace odebrání prvku končí. Jinak přejdeme ke kroku 2. 

2.  Zmenšení počtu prvků v uzlu 

Sem se dostáváme v situaci, kdy po odstranění prvku ze stromu je nyní ve stromu list v, který 
má  jen  p-1  prvků.  Jak  se  tento  stav  řeší,  závisí  na  zaplnění  přímých  sousedů  listu.  Jsou  dvě 
možnosti: 

a)  List v má aspoň jednoho přímého souseda, který má více než p prvků. Přímým sousedem 

zde máme na mysli uzel, který nejen sousedí s uzlem v, ale má i stejného předchůdce. Pak 
do  listu  v přesuneme  prvek  z předchůdce  a  na  prázdné  místo  v předchůdci  přesuneme 
příslušný prvek ze souseda. Následující obrázek ukazuje tento přesun pro oba možné přímé 
sousedy,  nejdříve  pro  levého  souseda,  pak  pro  pravého  souseda  (prvku  v  uzlu  v jsou 
značeny písmenem c). 

Z B-stromu lze 
prvek snadno i 
odstranit.