АВЛ-деревья

АВЛ-дерево - это структура данных, придуманная в 1962 году советскими учеными. Это модификация классического бинарного дерева поиска, благодаря которой структура лучше сбалансирована и практически не может выродиться. Вырождение - это ситуация, когда у каждого узла оказывается только по одному потомку, и структура становится линейной (не оптимальной). Благодаря сбалансированности и почти невозможности вырождения дерева, информация хранится более эффективно, поэтому доступ к данным оказывается быстрее, и найти становится легче.

Применение АВЛ-деревьев

АВЛ-деревья нужны разработчикам, аналитикам (обработка информации) и так далее. Данное дерево нужно для хранения данных. Это структура позволяет хранить информацию в узлах дерева и перемещаться с помощью путей, которые соединяют между собой узлы.

1. Поисковые алгоритмы: Используются при построении поисковых систем и интеллектуальных сервисов.
2. Сортировка: С помощью АВЛ-деревьев можно хранить и сортировать информацию в БД в особых участках памяти, ХЭШах и в других структурах.
3. Программные проверки: Может использоваться для решения стандартных задач (для быстрой проверки существования элемента в структуре).
4. Построение сложных структур: Дерево может быть составной частью более сложных структур данных или какого-либо алгоритма. Например, используется для поиска, хранения и принятия решений.

Особенности АВЛ-деревьев

АВЛ-дерево отличается от бинарного дерева поиска несколькими особенностями:

1. Сбалансированность по высоте: Поддеревья, образованные левыми и правыми потомками каждого из узлов, должны различаться длиной не более чем на 1 уровень.
2. Общая длина дерева и скорость операции: Зависят от числа узлов O(logn).
3. Вероятность получить сильно несбалансированное АВЛ-дерево крайне мала, а риск, что оно выродиться практически отсутствует. Сбалансированность такого дерева гарантирована, в отличии от рандомизированных деревьев, которые сбалансированы вероятностно.

Балансировка

Балансировка называют операцию, которая делает дерево более сбалансированным. В случае с АВЛ-деревьями ее применяют, когда нарушается главное правило структуры: Поддеревья потомки одного узла начинают различаться больше, чем на один уровень. Если разница в количестве уровней становится равна -2 и 2, то запускается балансировка. В связи между предками и потомками изменяются и перестраиваются так, чтобы сохранить структуру. Обычно для этого какую-либо из узлов поворачивается влево или вправо, то есть меняет свое расположение. Поворот может быть простым, когда расположение изменяет только один узел, или большим, при нем два узла разворачиваются в разные стороны.

Особенность АВЛ-деревьев при балансировке состоит в том, что после вставки надо проверить соотношение длин поддеревьев и если нужно, то провести балансировку. Высота АВЛ-дерева с n ключами лежит в диапазоне log2(n + 1) < h < 1.44log(n + 2) – 0.328.

Реализация АВЛ-дерева на C++

#include<iostream>
using namespace std;

struct Node {
int key;
Node *left;
Node *right;
int height;
};

Node* newNode(int key) {
Node* node = new Node();
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
return(node);
}

int height(Node *N) {
if (N == NULL)
return 0;
return N->height;
}

int max(int a, int b) {
return (a > b)? a : b;
}

Node* rightRotate(Node *y) {
Node *x = y->left;
Node *T2 = x->right;

// Perform rotation
x->right = y;
y->left = T2;

// Update heights
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;

// Return new root
return x;
}

Node* leftRotate(Node *x) {
Node *y = x->right;
Node *T2 = y->left;

// Perform rotation
y->left = x;
x->right = T2;

// Update heights
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;

// Return new root
return y;
}

int getBalance(Node *N) {
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}

Node* insert(Node* node, int key) {
// 1. Perform the normal BST insertion
if (node == NULL)
return(newNode(key));

if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else // Equal keys are not allowed in BST
return node;

// 2. Update height of this ancestor node
node->height = 1 + max(height(node->left), height(node->right));

// 3. Get the balance factor
int balance = getBalance(node);

// If this node becomes unbalanced, then there are 4 cases

// Left Left Case
if (balance > 1 && key < node->left->key)
return rightRotate(node);

// Right Right Case
if (balance < -1 && key > node->right->key)
return leftRotate(node);

// Left Right Case
if (balance > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}

// Right Left Case
if (balance < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}

// return the (unchanged) node pointer
return node;
}