Algoritmy a dátové štruktúry prednáška 09

Zhrnutie prednášky

Prednáška nadväzuje na tému binárnych vyhľadávacích stromov a venuje sa ich vylepšovaniu pomocou pomocných údajov uložených vo vrcholoch - hĺbky a veľkosti podstromu, ktoré sa efektívne prepočítavajú pri vkladaní a mazaní. Ukazuje sa využitie veľkosti podstromu na indexovanie do stromu a nájdenie k-teho najmenšieho prvku v logaritmickom čase. Predstavuje sa formálna definícia vyváženosti (AVL stromy podľa Adelson-Velského a Landisa) a operácia rotácie ako spôsob lokálnej úpravy tvaru stromu pri zachovaní usporiadania kľúčov. Pomocou Fibonacciho čísel a zlatého rezu sa dokazuje, že vyvážený strom má hĺbku najviac dvojnásobok optima, teda logaritmickú vzhľadom na počet vrcholov. Na záver sa spomínajú praktické dátové štruktúry postavené na vyvážených stromoch - usporiadaná množina a asociatívne pole (mapa), ako aj iné druhy vyvažovaných stromov, napríklad červeno-čierne stromy, splay stromy a treapy.

• Prepočítavanie hĺbky a veľkosti podstromu vo vrcholoch
• Indexovanie do stromu a hľadanie k-teho najmenšieho prvku
• Definícia vyváženosti AVL stromu (Adelson-Velsky, Landis)
• Rotácia ako lokálna operácia na zmenu tvaru stromu
• Dôkaz logaritmickej hĺbky pomocou Fibonacciho čísel a zlatého rezu
• Červeno-čierne stromy, splay stromy a ďalšie varianty vyvažovania
• Usporiadaná množina (set) a asociatívne pole (mapa) postavené na vyvážených stromoch

Zhrnutie pripravené s pomocou AI z prepisu videa.