54
правки
Изменения
→Идея
<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>, деревом будет считаться даже линейная структура. Примечание:Существует два подхода к балансу дерева, которые дают похожий результат. Первый - задавать <tex>\alpha</tex>. Второй - задать ограничение <tex>q</tex>, большее чем число элементов в дереве (чем больше ограничение, тем более несбалансированным может быть дерево), и следить, чтобы <tex>\log3/2(q)/tex> был больше максимальной глубины дерева. В противном случае, необходимо произвести перебалансировку дерева.
== Свойства ==
