ADŠ prednáška 09: Rekurzívny výpis BST, iterátory, vylepšenia.

Zhrnutie prednášky

Prednáška nadväzuje na binárne vyhľadávacie stromy a dokazuje, prečo AVL stromy zaručujú logaritmickú hĺbku. Najprv sa načrtne, že rotáciami sa dá preusporiadať ľubovoľný strom na iný s rovnakou množinou prvkov, tak že sa požadovaný prvok rotáciami dostane do koreňa a postup sa rekurzívne zopakuje v podstromoch. Hlavná časť skúma opačnú otázku: aký najmenší počet vrcholov potrebuje vyvážený strom danej hĺbky. Minimálne počty vrcholov pre hĺbky 0 až 3 sú 1, 2, 4 a 7 a všeobecne spĺňajú rekurenciu P(h) = P(h-1) + P(h-2) + 1. Tá sa porovnáva s Fibonacciho číslami (P(h) = F(h+3) − 1), z čoho vyplýva exponenciálny rast počtu vrcholov, a teda logaritmická hĺbka.

• - AVL strom je vyvážený, ak sa v každom vrchole hĺbky podstromov líšia najviac o 1.
• - Rotáciami možno previesť ľubovoľný binárny vyhľadávací strom na iný s rovnakými prvkami: požadovaný prvok sa rotáciami dostane do koreňa a postup sa rekurzívne opakuje v podstromoch.
• - Hĺbku vyváženého stromu odhadujeme otočenou otázkou: koľko najmenej vrcholov treba na danú hĺbku.
• - Minimálny počet vrcholov pre hĺbky 0, 1, 2, 3 je 1, 2, 4, 7.
• - Minimálny strom hĺbky h má podstromy minimálnych hĺbok h-1 a h-2, preto P(h) = P(h-1) + P(h-2) + 1.
• - Rekurencia je podobná Fibonacciho číslam (P(h) je približne o 1 menšie než F(h+3)), takže počet vrcholov rastie exponenciálne a hĺbka je O(log n).

Zhrnutie pripravené s pomocou AI z prepisu videa.