Рандомизированные деревья

Большинство лучших операций (например, поиск, макс, мин, вставка, удаление и т. д.) использует время O (h), где h – высота оптимального дерева. Стоимость этих операций может стать O (n): если мы убедимся, что высота дерева остается O(log n) после каждой вставки и удаления, то мы можем гарантировать верхнюю границу O (log n) для всех этих операций. Высота дерева AVL всегда O (log n), где n – количество узлов в дереве.
Чтобы убедиться, что данное дерево остается AVL после каждой вставки, мы должны расширить стандартную операцию вставки BST для выполнения некоторой балансировки. Ниже приведены две основные операции, которые могут быть выполнены для восстановления баланса BST без нарушения свойства BST.
1) Левое Вращение
2) Правое Вращение
Шаги, которые необходимо выполнить для вставки:
Пусть вновь вставленный узел будет W
1) Выполните стандартную вставку BST для W.
2) начиная с W, идите вверх и найдите первый несбалансированный узел. Пусть Z будет первым неуравновешенный узел, Y ребенка от Z, что происходит на пути от w к Z и X быть внуком Z, что приходит на пути из W к Z.
3) повторно сбалансируйте дерево, выполнив соответствующие вращения на поддереве, коренящемся с Z. Может быть 4 возможных случая, которые необходимо обработать, поскольку X, Y и Z могут быть организованы в 4 формациях. Ниже приведены возможные кейсы:
а) Y является левым потомком Z и X является левым потомком Y;
б) Y является левым потомком Z и X правый ребенка Y;
c) Y правый ребенок Z, а X правый ребенок Y;
д) Y правый ребенок Z и X является левым потомком Y.
В рекурсивной вставке BST после вставки мы получаем указатели на всех предков снизу вверх. Поэтому нам не нужен родительский указатель для перемещения вверх. Рекурсивный код сам перемещается вверх и посещает все предки вновь вставленного узла.
1) Выполните нормальную вставку BST.
2) текущий узел должен быть одним из предков вновь вставленного узла. Обновите высоту текущего узла.
3) получить коэффициент баланса (высота левого поддерева – высота правого поддерева) текущего узла.
4) Если коэффициент баланса больше 1, то текущий узел несбалансирован, и мы находимся либо в левом левом случае, либо в левом правом случае. Чтобы проверить, является ли он левым левым поддеревом или нет, сравните недавно вставленный ключ с ключом в левой ветви поддерева.
5) если коэффициент баланса меньше -1, то текущий узел несбалансирован, и мы находимся либо в правом правом случае, либо в правом левом случае. Чтобы проверить, является ли это правильным правым случаем или нет, сравните недавно вставленный ключ с ключом в правой ветви поддерева.
Операции поворота (поворот влево и вправо) занимают константное время, поскольку там изменяется только несколько указателей. Обновление высоты и получение коэффициента баланса также занимает постоянное время. Таким образом, временная сложность вставки AVL остается такой же, как и вставка BST, которая равна O(h), где h – высота дерева. Поскольку Авл-дерево является сбалансированным, его высота составляет O(logn). Таким образом, временная сложность вставки AVL равна O(logn).