Definujte binární strom. Definujte AVL strom a formulujte větu o hloubce AVL stromu.

Definice binárního stromu

AVL Strom

BTS je AVL stromem, pokud pro každý jeho vrchol platí | h(L(v)) - h(P(v)) | ≤ 1

Věta o hloubce AVL stromu

AVL strom s n vrcholy má hloubku O(log n)

Důkaz hloubky AVL stromu

Ah = minimální počet vrcholů AVL stromu s hloubkou h

→ dokážeme, že Ah roste exponencionálně s h

• Nejmenší AVL stromy dané hloubky jsou maximálně “hloubkově rozvážené”