BPC-ALD - Skripta_rev2019_2

)

1

(

2

+

× h

  operací  srovnání,  kde  h  je  výška 

stromu. Připomeňme, že v kapitole pojednávající o stromech jsme pro zcela vyvážený binární 
strom  odvodili  logaritmický  vztah  mezi  jeho  výškou  a  počtem  uzlů  v  něm.  Dá  se  ukázat,  že 

Vyhledávání v 
AVL stromu má 
stejnou míru 
složitosti jako v 
úplně vyváženém 
stromu.

− 71 − 

výška AVL stromu je maximálně 1,45 násobkem výšky úplně vyváženého binárního stromu se 
stejným počtem uzlů. Což znamená, že i v AVL stromu má vyhledávání logaritmickou složitost. 

Základem  zbývajících  operací  (přidání  prvku,  odebrání  prvku)  je  vyhledání  a  dále  průchod 
stromem  směrem  nahoru.  Z čehož  plyne,  že  složitost  těchto  operací  rovněž  závisí  na  výšce 
stromu, a to znamená, že i ony mají logaritmickou složitost. 

Kontrolní otázky  

1.  Jak probíhá hledání v binárním vyhledávácím stromu? 
2.  Jaká je nejhorší možná a nejlepší možná složitost vyhledávání v binárním vyhledávacím  

stromu? 

3.  Proč  v praxi  pro  binární  vyhledávácí  stromy  nepoužíváme  úplně  vyvážené  binární 

stromy, ale AVL stromy? 

4.  Jaká je časová složitost operací v AVL stromu? 
5.  Které jsou základní transformace obnovení vyvážení AVL stromu? 

Cvičení  

1.  Do následujícího AVL stromu přidejte prvek 23. 

2.  Do následujícího AVL stromu přidejte prvek 18. 

3.  Z následujícího AVL stromu odeberte prvek 15. Ukažte všechny možnosti, jak prázdný 

uzel zaplnit jiným prvkem. 

Úkoly k textu  

Zkuste si nakreslit AVL strom větší výšky s minimálním počtem uzlů pro danou výšku a k 
němu úplně vyvážený binární strom se stejným počtem uzlů a ověřte, zda skutečně pro ně platí, 
že poměr výšky AVL stromu a úplně vyváženého binárního stromu je nejvýše 1,45.