BPC-ALD - Skripta_rev2019_2

− 72 − 

Řešení  

1.  Přidání prvku a následné vyvážení ukazuje následující obrázek: 

2.  Přidání prvku a následné vyvážení ukazuje následující obrázek: 

3.  První obrázek ukazuje zaplnění prázdného kořene prvkem z levého podstromu: 

Druhý obrázek ukazuje druhou možnost – zaplnění prázdného kořene prvkem z pravého 
podstromu: 

− 73 − 

4.3.2  B-stromy 

Studijní cíle:  Tato  část  vysvětluje  princip  B-stromů,  popisuje  jejich  vlastnosti  a  konstrukci  a 
ukazuje, jak v B-stromu probíhá vyhledávání, jak do B-stromu přidat prvek nebo z něho prvek 
odebrat a zejména, jak pak provést transformace, jimiž se zajistí zachování vyváženosti stromu. 

Klíčová slova: Vložení, odebrání, B-strom. 

Potřebný čas: 2 hodiny 

B-stromy  jsou  velmi  významným  typem  vyhledávacích  stromů.  Na  rozdíl  od  doposud 
uváděných stromů, kdy v každém uzlu byl uložen jeden prvek, B-stromy mají v uzlech uloženo 
více prvků. Struktura B-stromů je definována následujícími vlastnostmi: 

Kapacita uzlu (počet prvků, který lze do uzlu uložit) je u všech uzlů stromu stejná, je to sudé 
číslo  a  volí  se  před  začátkem  vytváření  stromu,  označme  ho  r.  Protože  v B-stromech  má 

významnou úlohu polovina z tohoto počtu, zaveďme si pro ni samostatné označení 

2

r

p

= . 

Důležité  pro  efektivní  využití  uzlů  je  jejich  zaplnění.  Všechny  uzly  vyjma  kořene  musí  být 
aspoň z poloviny zaplněny prvky, tedy počet prvků v uzlech uložených musí být v rozmezí p až 
r prvků. Jedině u kořene stačí, aby obsahoval aspoň jeden prvek, tedy jeho zaplnění je v rozmezí 
1 až r prvků.