54
правки
Изменения
→Плюсы и минусы
<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> деревом будет считаться даже линейная структура.
