54
правки
Изменения
Нет описания правки
<tex> size(left[x]) \leqslant \alpha \cdot size(x) </tex>;
<tex> size(right[x]) \leqslant \alpha \cdot size(x) </tex>, где <tex>size(left[x])</tex> и <tex>size(right[x])</tex> - размер левого и правого поддерева вершины <tex>x</tex>.
=== Плюсы и минусы ===
+ Данное дерево позволяет ускорить одни операции взамен на ускорение других, что отличает его от других (простое бинарное дерево, красно-черное дерево, splay-дерево). Результаты исследований показывают, что Scapegoat tree работает на случайных данных быстрее, чем красно-черное.
+ Требует меньше памяти, так как не надо хранить дополнительную информацию в вершине для балансировки.
+ Настройки скорости можно менять в процессе выполнения программы.
- Данное дерево сложно для написания.
- В случае неправильной настройки скорости работы дерево будет проигрывать по скорости работы другим.
Если условие нарушается, запускается операция перебалансировки дерева. Заметим, что при <tex>\alpha = 1</tex> деревом будет считаться даже линейная структура.
