Scapegoat strom

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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.

Odkazy[editovat | editovat zdroj]