Бинарное дерево поиска (BST) называется практически сбалансированным (almost balanced), если длины всевозможных путей от корня к внешним вершинам отличаются не более, чем на единицу.
Высота такого дерева равна`h=|__ log_2(n)+1 __|`.
Идеально сбалансированным деревом будет только дерево, содержащее `2^h-1` вершин.
Обеспечение сбалансированности является сложной задачей, поэтому на практике используют более слабые критерии.
--
*АВЛ-дерево* — сбалансированное бинарное дерево поиска, в котором поддерживается следующее свойство: для каждой его
вершины высота её двух поддеревьев различается не более чем на 1.
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса,
которые впервые предложили использовать АВЛ-деревья в 1962 году.
Максимальная высота АВЛ-дерева
`h <= |__ 1.45*log_2(n+2) __|`
--
В каждом узле АВЛ-дерева мы храним высоту поддерева или разность в высоте (0,1,-1) и при нарушении разницы высот выполняем балансировку за `O(1)`.
Добавление: поиск места вставки нового узла `O(h)`, а при обратном проходе балансировка не более, чем `O(h)` раз.

--
Удаление: аналогично.

--
*Красно-чёрным* называется бинарное дерево поиска, у которого каждому узлу сопоставлен дополнительный атрибут — цвет и для
которого выполняются следующие свойства:
* Каждый узел промаркирован красным или чёрным цветом
* Корень и конечные узлы (листья) дерева — чёрные (листья, не содержащие данных — чёрные)
* У красного узла родительский узел — чёрный, у чёрного узла - любого цвета
* Все простые пути из любого узла `x` до листьев содержат одинаковое количество чёрных узлов (*чёрная высота*)
Максимальная высота красно-чёрного дерева
`h <= 2*log_2(n)+1`
--
Расширяющееся дерево (Splay-tree) — это двоичное дерево поиска, которое позволяет находить быстрее те данные, которые использовались недавно. Для этого узлы дерева переупорядочиваются таким образом, чтобы узел с искомым или добавляемым ключом стал корнем дерева.
Если к ключам в сплей-дереве выполняется `m` запросов поиска, из них к `i`-му ключу `k_i>0` запросов, то суммарное время работы не превышает `O(m*H(k_1/m,k_2/m,...,k_n/m))`, где `H` — шенноновская энтропия. Математическое ожидание количества действий для поиска `i`-го ключа равно `3*(log_2 m-log_2 k_i)`.