В этом задании вам необходимо реализовать сбалансированное двоичное дерево поиска - иерархичную структуру данных в pointer machine model, узлы которой содержат значения, а также некоторые имеют левого и/или правого потомка, каждый из которых является корнем левого и правого поддеревьев соответственно. Узлы без потомков называются листями, остальные - внутренними. Узел, находящийся на самом верхнем уровне (не являющийся чьим либо потомком) называется корнем (в дереве всегда только один корень).
Все значения в левом поддереве узла меньше, чем значение в самом узле. Аналогично, все значения в правом поддереве - больше, чем значение в узле.
Введем понятие высоты узла:
- Высота листа равна нулю
- Высота внутреннего узла равна максимуму между высотами его потомков, увеличенному на один
Высота дерева определяется как высота его корня.
Дерево называется сбалансированным, если его высота не превышает значение C·log(n) для некоторого C, где n - это количество элементов в дереве.
Информацию про ваши модификации в найдете в директории /trees:
- Группа 81 - АВЛ-дерево (/trees/AVL_B81.md)
- Группа 82 - Splay-дерево (/trees/Splay_B82.md)
- Группа 83 - Декартово дерево (/trees/Treap_B83.md)