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ě a amortizovaná složitost vkládání a mazání je také . 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
![]() |
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. |
Zdroj dat | cs.wikipedia.org |
---|---|
Originál | cs.wikipedia.org/wiki/Scapegoat_strom |