Dostal jsem AVL stromy, což je všeobecně známá věc, leč mně bylo už předem jasné, že správně nadefinovat rotace a vyvažování bude nad moje síly, a tedy mě čeká dříve či později odchod domů. Ukázalo se, že rotace a vyvažování nebyly zdaleka mým jediným problémem.
- Zvoral jsem už základní definici binárních vyhledávacích stromů. Jako základní podmínku jsem uvedl, že L(v) <= v <= P(v). Což je nerovnost, které se využívá při průchodu stromem, ale požadovaná vlastnost musí samozřejmě být silnější.
- Zvoral jsem základní operaci delete na vyhledávacích stromech. Moje verze v případě, že odebírám vrchol s dvěma syny, říkala, že vrchol nahradím jedním ze synů (což by porušilo binaritu). Naštěstí jsem si pak vzpomněl, že se vrchol nahrazuje maxem z levého podstromu.
- Zvoral jsem definici hloubky pro podstromy hl(L(v)) a hl(P(v)), z čehož se pak vyvozuje základní vlastnost AVL stormů. Je totiž potřeba myslet na případ, kdy v jednoho syna nemá a ručně dodefinovat hl := -1 pro tento případ. Je to v zásadě formální špek, ale Koubek mě v tom pokoupal.
- Zvoral jsem důkaz hloubky stromu. Důkaz jsem neuměl, jen jsem si pamatoval, že se dokazuje exponenciální počet vrcholů ve stromě s hloubkou k, že se to dělá indukcí, že tam figuruje 2^(k/2) a že to není těžké. Navrhl jsem důkaz, který všechno jmenované splňoval, leč na některé dost důležité věci jsem zapomněl a důkaz byl tedy odmítnut.
- Nenadefinoval jsem jedinou rotaci správně.
Takže abych to shrnul, v podstatě ve všem, co jsem napsal, jsem měl chybu. Ty lehčí věci mě nechal Koubek opravit, ty těžší vymyslel za mě. Což je dost v protikladu s tím, za co dost často vyhazuje. Evidentně stačí vědět, že AVL je binární strom a že se nějak rotuje a vyvažuje. Jak se to děje, to už je irelevantní
Budoucím generacím bych doporučil se obloukem vyhnout Koubkovým skriptům, snad jen jako pomocný materiál a haldy se mi z nich zdály docela pochopitelné (pokud si člověk namaluje, co se v nich děje). Naopak bych doporučoval se držet co to jde starých ADS sešitů, protože průnik datovek s ADS je dost velký, akorát v ADS jsou věci vysvětlovány jednodušeji a přímočařeji, i ty důkazy jsou snazší. A na projití to bohatě stačí.