== Определение =='''Scapegoat-дерево''' (англ. ''Scapegoat-Tree'') {{---}} сбалансированное бинарное дерево поиска, обеспечивающее наихудшее <tex>O(log N)</tex> время поиска, и <tex>O(log N)</tex> - амортизирующее время вставки и удаления элемента.В отличие от большинства других самобалансирующихся бинарных деревьев поиска , которые обеспечивают худшем случае <tex>O(log N)</tex> время поиска, Scapegoat деревья не требуют дополнительной памяти в узлах по сравнению с обычным двоичным деревом поиска : узел хранит только ключ и два указателя на своих потомков.
== Достоинства Scapegoat дерева ==
