BPC-ALD - Skripta_rev2019_2

hledaný prvek není ve stromu obsažen. 

c)  Prvek nebyl v aktuálním uzlu u nalezen a tento uzel je nelistový. V tom případě vyhledávání 

skončilo v místě, kde je odkaz na následníka, ve kterém vyhledávání má pokračovat (tj. na 
následníka,  kterým  začíná  podstrom,  jež  by  hledaný  prvek  měl  obsahovat).  Tohoto 
následníka učiníme novým aktuální uzlem a opět se provede krok 2. 

Postup přidání prvku 

Chceme-li  do  B-stromu  přidat  prvek,  znamená  to  najít  příslušný  uzel,  do  kterého  nový  prvek 
patří, a následně ověřit, zda přitom nedošlo k přeplnění, a pokud ano, provést rozdělení uzlu. 

1.  Přidání prvku 

Označme  přidávaný  prvek  x.  Provedeme  je  vyhledání  ve  stromu.  Použijeme  k tomu  běžný 
algoritmus pro vyhledání. Ten může skončit dvěma způsoby: 

a)  Prvek x byl ve stromu nalezen. Tím přidávání končí, neboť prvek x už je ve stromu obsažen 

(u vyhledávacích stromů se nepředpokládá vícenásobný výskyt stejného prvku). 

b)  Vyhledávání skončilo v listovém uzlu u v místě, kam nový prvek podle velikosti vzhledem 

k ostatním  prvků  patří.  Prvek  na  toto  místo  vložíme.  Pokud  uzel  u  předtím  nebyl  zcela 
zaplněn, operace přidání tím končí. Jinak provedeme rozdělení uzlu. 

2.  Rozdělení uzlu 

Jestliže uzel u má po přidání r+1 prvků, tedy došlo k jeho přeplnění uzlu, rozdělíme ho na tři 
části: 

p prvků na začátku uzlu   +   prvek uprostřed uzlu   +   p prvků na konci uzlu. 

Části  s  p  prvky  budou  tvořit  nové  listy.  Prvek,  jež  je  v uzlu  u  uprostřed,  se  přesune  do 
předchůdce  na  místo,  kde  byl  původní  odkaz  na  list.  Po  přesunu  nalevo  a  napravo  od  něho  
vytvoříme nové odkazy na nově vzniklé listy.