![][1]Сегодня мы посмотрим на структуру данных, называемую Scapegoat-деревом. «Scapegoat», кто не в курсе, переводится как «козёл отпущения», что делает дословный перевод названия структуры каким-то странным, поэтому будем использовать оригинальное название. Деревьев поиска, как вы, возможно, [знаете][2] есть очень много разных видов, и в основе всех их лежит одна и та же идея: "**А хорошо бы при поиске элемента перебирать не весь набор данных подряд, а только какую-то часть, желательно размера порядка log(N)**". Для этого каждая вершина хранит ссылки на своих детей и какой-то критерий, по которому при поиске точно понятно, в какую из дочерних вершин надо перейти. За логарифмическое время это всё будет работать тогда, когда дерево является сбалансированным (ну или стремится к этому) — т.е. когда «высота» каждого из поддеревьев каждой вершины примерно одинакова. А вот способы балансировки дерева уже у каждого типа деревьев свои: в красно-чёрных деревьях в вершинах хранятся маркеры «цвета», подсказывающие когда и как нужно перебалансировать дерево, в АВЛ-деревьях в вершинах хранится разница высот детей, Splay-деревья ради балансировки вынуждены изменять дерево во время операций поиска и т.д. Scapegoat-дерево тоже имеет свой подход к решению проблемы балансировки дерева. Как и для всех остальных случаев он не идеален, но вполне применим в некоторых ситуациях. К достоинствам Scapegoat-дерева можно отнести:
* Отсутствие необходимости хранить какие-либо дополнительные данные в вершинах (а значит мы выигрываем по памяти у красно-черных, АВЛ и декартовых деревьев)
* Отсутствие необходимости перебалансировать дерево при операции поиска (а значит мы можем гарантировать максимальное время поиска O(log N), в отличии от Splay-деревьев, где гарантируется только амортизированное O(log N))
* Амортизированная сложность операций вставки и удаления O(log N) — это в общем-то аналогично остальным типам деревьев
* При построении дерева мы выбираем некоторый коэффициент «строгости» α, который позволяет «тюнинговать» дерево, делая операции поиска более быстрыми за счет замедления операций модификации или наоборот. Можно реализовать структуру данных, а дальше уже подбирать коэффициент по результатам тестов на реальных данных и специфики использования дерева.
К недостаткам можно отнести:
* В худшем случае операции модификации дерева могут занять O(n) времени (амортизированна сложность у них по-прежнему O(log N), но защиты от «плохих» случаев нет).
* Можно неправильно оценить частоту разных операций с деревом и ошибиться с выбором коэффициента α — в результате часто используемые операции будут работать долго, а редко используемые — быстро, что как-то не хорошо.
[Читать дальше →][3]
[1]: //habrastorage.org/files/6c6/cbb/e62/6c6cbbe624b140e9b12dc4e4466f2e99.png
[2]:
http://habrahabr.ru/post/66926/
[3]:
http://habrahabr.ru/post/246759/#habracut