BPC-ALD - Skripta_rev2019_2

Složitost operací 

B-stromy mají 
dobrou časovou 
složitost operací.

− 80 − 

Vezměme  operaci  vyhledávání.  Ta  jednak  zahrnuje  vyhledávání  v uzlu.  Pro  ně  je  použito 
binární  vyhledávání,  které  má  logaritmickou  složitost.  A  dále  operace  vyhledávání  znamená 
procházení uzlů od kořene k listu. Protože strom je vyvážený, výška stromu logaritmicky závisí 
na počtu prvků ve stromu. Celkově tedy vyhledávání má logaritmickou složitost. 

Základem  zbývajících  operací  (přidání  prvku,  odebrání  prvku)  je  vyhledávání  a  dále  průchod 
stromem směrem nahoru. Z čehož plyne, že i tyto operace mají logaritmickou složitost. 

Průvodce studiem  

B-stromy vznikly v roce 1969, tedy 7 let po vzniku AVL stromů, jež pocházejí z roku 

1962. O B-stromech určitě ještě uslyšíte v teorii databázových systémů, neboť se v nich se 
hodně využívají. 

1.  Jaké jsou vlastnosti B-stromu? 
2.  Jak probíhá v B-stromu vyhledávání? 
3.  Jaká je časová složitost operací v B-stromu? 
4.  Které jsou základní transformace obnovení vyvážení B-stromu? 

Cvičení  

1.  Do následujícího B-stromu (kapacita uzlů je r=4) přidejte prvek 55. 

2.  Stejný B-strom jako v předchozím cvičení, ale nemáme přidat prvek, nýbrž máme 

odebrat prvek  41. 

3.  Z následujícího B-stromu (kapacita uzlů je r=4) odeberte prvek 37. 

Úkoly k textu  

Zkuste spočítat, kolik pro danou výšku má B-strom uzlů v případě, kdy má nejmenší možné 
zaplnění uzlů, a kolik v případě, kdy má všechny uzly zcela zaplněny. 

− 81 − 

Řešení  

1.  Po přidání prvku 55 do listu se počet prvků v listu zvýší na 5, což znamená, že je nutné 

z listu vytvořit dva listy a střední prvek přesunout do kořenu. Ten ale už předtím byl 
také plný, čímž dojde i k jeho rozdělení a vytvoření nového kořenu. Výsledek ukazuje 
následující obrázek: