Scapegoat strom

Scapegoat strom (z angl. slova scapegoat - obětní beránek) je jeden z binárních vyhledávacích stromů. Nezávisle na sobě ho vymysleli Arne Andersone a Igal Galperin. Je implementován tak, že používá standardní algoritmy pro vkládání záznamů do nevyváženého stromu a v případě, že je to třeba, je strom při poslední operaci znovu vyvážen. Složitost při vyhledávání je v nejhorším případě O(\log n) a amortizovaná složitost vkládání a mazání je také O(\log n). Jeho největší výhodou je paměťová nenáročnost, na rozdíl od většiny vyvažovaných vyhledávacích stromů nepotřebuje ve vrcholech informace navíc.

Externí odkazy

Vizualizace [url=https://people.ksp.sk/~kuko/gnarley-trees/Scapegoat.html]scapegoat stromu[/url]

Kategorie:Stromy (datové struktury)