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ě ${\displaystyle O(\log n)}$ a amortizovaná složitost vkládání a mazání je také ${\displaystyle 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.

• Vizualizace scapegoat stromu

Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.