Малые повороты двоичного дерева
Поворот двоичного дерева поиска
Мы уже показали, что несбалансированное ДДП имеет плохие показатели при поиске и вставке новых элементов: сложность операций стремится к n, т.о. преимущества этой структуры данных теряются. Идеальным был бы вариант, когда расстояние от вершины дерева до каждого из его листьев одинаковое или не отличается более чем на единицу. Такое сбалансированное двоичное дерево поиска будет иметь сложность порядка log(n) для операции поиска элемента, и, как следствие, вставка и удаление станут быстрее.
Двоичное дерево поиска не является самобалансирующейся структурой данных, то есть, при вставке или при удалении узлов может происходить разбалансировка дерева и увеличение времени выполнения операций. Однако, можно произвести балансировку "вручную".
Введём новую операцию - малые левый и правый повороты. Поворот дерева - это операция, которая позволяет изменить структуру дерева не меняя порядка элементов. Особенность этих операций в том, что они могут уменьшить высоту дерева. Используя эти операции для соответствующих узлов можно минимизировать высоту дерева.
Очевидно, что используя обратную операцию, наоборот, можно удлинять одну из ветвей, вытягивая её в список.
Обратите внимание – если производить поворот относительно вершины, то узел, который мы передаём, перестанет быть корнем дерева и превратится в наследника. Нужно постоянно помнить об этом, иначе можно потерять указатель на вершину дерева.
Из рисунка видно, что левый и правый малый поворот не изменяют положения ветвей L и R (Left и Right) и изменяют положение ветви C. Нужно помнить, что каждая из ветвей может быть равна NULL.
void l2rRotation(Node **root) {
Node *parent = NULL,
*C = NULL,
*a = NULL,
*b = NULL;
a = (*root);
parent = a->parent;
b = a->right;
if (b == NULL) {
return;
}
C = b->left;
b->left = a;
a->right = C;
if (C) {
C->parent = a;
}
b->parent = parent;
if (parent) {
if (parent->left == a) {
parent->left = b;
} else {
parent->right = b;
}
}
a->parent = b;
if (!parent) {
*root = (*root)->parent;
}
}
void r2lRotation(Node **root) {
Node *parent = NULL,
*C = NULL,
*a = NULL,
*b = NULL;
b = (*root);
parent = b->parent;
a = b->left;
if (a == NULL) {
return;
}
C = a->right;
a->right = b;
b->left = C;
if (C) {
C->parent = b;
}
a->parent = parent;
if (parent) {
if (parent->left == b) {
parent->left = a;
} else {
parent->right = a;
}
}
b->parent = a;
*root = (*root)->parent;
}
Левый поворот позволяет укорачивать ветвь, "растянувшуюся" вправо, правый, наоборот, длинную левую ветвь. Алгоритм балансировка состоит из трёх фаз. Во-первых, мы "расплетаем" дерево, используя левый и правый поворот, превращаем его в левоассоциативную лозу (vine). У этой лозы будет m узлов. Во-вторых, мы сводим эту лозу, используя правый поворот, к дереву, у которого главная левая лоза состоит из n-1 узла, где n - это ближайшее целое число, меньше данного, равное степени двойки (целочисленный логарифм по основанию 2). В конце мы проводим следующую операцию: отмечаем, начиная с вершины, через один все узлы дерева, после чего производим относительно них поворот. Эту операцию повторяем log(n) раз. Получается сбалансированное двоичное дерево поиска.
