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 scapegoat stromu