== Идея ==
вввПри работе необходимо поддерживать состояние сбалансированного дерева, иначе время работы операции поиска может превысить <tex>O(\log n)</tex>. В Scapegoat Tree используется следующая идея: введем коэффициент <tex>\alpha</tex>, который показывает, насколько дерево может быть несбалансированным. Математически это выглядит следующим образом: <tex> 1/2 \leqslant \alpha \leqslant 1 </tex>; <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>. Если условие нарушается, запускается операция перебалансировки дерева. Заметим, что при <tex>\alpha = 1</tex>, деревом будет считаться даже линейная структура.
== Свойства ==
ввв
== Операции ==
== Оценка времени работы ==
