Введем обозначения:
Квадратные скобки в обозначениях означают, что хранится это значение явно, а значит можно взять за время <tex>O(1)</tex>. Круглые скобки означают, что значение будет вычисляться по ходу дела то есть память не расходуется, но зато нужно время на вычисление.
<tex>T</tex> — обозначение дерева, <tex>root[T]</tex> — корень дерева <tex>T</tex>, <tex>left[x]</tex> — левый сын вершины <tex>x</tex>, <tex>right[x]</tex> — правый сын вершины <tex>x</tex>, <tex>\mathtt{brother(x)}</tex> — брат вершины <tex>x</tex> (вершина, которая имеет с <tex>x</tex> общего родителя), <tex>depth(x)</tex> — глубина вершины <tex>x</tex>. Это расстояние от неё до корня (количество ребер), <tex>height(T)</tex> — глубина дерева <tex>T</tex>. Это глубина самой глубокой вершины дерева <tex>T</tex>, <tex>weight(x)</tex> — вес вершины <tex>x</tex>. Это количество всех её дочерних вершин + 1 (она сама), <tex>weight[T]</tex> — размер дерева <tex>T</tex>. Это количество вершин в нём (вес корня), <tex>\mathtt{maxweight[T]}</tex> — максимальный размер дерева. Это максимальное значение, которое параметр <tex>weight[T]</tex> принимал с момента последней перебалансировки.<br> Если перебалансировка произошла только что, то <tex>\mathtt{maxweight[T]} = weight[T]</tex>
[[Файл:0ce162a62b624da8ba02233b4b254f23.png]]
Если оно выполняется — дерево могло потерять <tex>\alpha</tex> - балансировку по весу, а значит нужно выполнить полную перебалансировку дерева (начиная с корня) и присвоить:
:<tex>\mathtt {maxweight[T]} = weight[T]</tex>;
==Сравнение с другими деревьями==
