Вот реализация AVL дерева на языке C с основными операциями: вставка, удаление, поиск и балансировка:
```c
#include <stdio.h>
#include <stdlib.h>
// Структура узла AVL дерева
typedef struct Node {
int key;
struct Node *left;
struct Node *right;
int height;
} Node;
// Функция для получения высоты узла
int height(Node *node) {
if (node == NULL)
return 0;
return node->height;
}
// Функция для вычисления максимума
int max(int a, int b) {
return (a > b) ? a : b;
}
// Создание нового узла
Node* newNode(int key) {
Node* node = (Node*)malloc(sizeof(Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // новый узел всегда добавляется как лист
return node;
}
// Правый поворот поддерева с корнем y
Node* rightRotate(Node *y) {
Node *x = y->left;
Node *T2 = x->right;
// Выполнение поворота
x->right = y;
y->left = T2;
// Обновление высот
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
return x; // Новый корень
}
// Левый поворот поддерева с корнем x
Node* leftRotate(Node *x) {
Node *y = x->right;
Node *T2 = y->left;
// Выполнение поворота
y->left = x;
x->right = T2;
// Обновление высот
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
return y; // Новый корень
}
// Получение фактора баланса узла
int getBalance(Node *node) {
if (node == NULL)
return 0;
return height(node->left) - height(node->right);
}
// Вставка ключа в дерево
Node* insert(Node *node, int key) {
// 1. Обычная вставка BST
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 // Дубликаты не разрешены
return node;
// 2. Обновление высоты узла
node->height = 1 + max(height(node->left), height(node->right));
// 3. Проверка баланса
int balance = getBalance(node);
// Если узел несбалансирован, возможны 4 случая:
// Left Left
if (balance > 1 && key < node->left->key)
return rightRotate(node);
// Right Right
if (balance < -1 && key > node->right->key)
return leftRotate(node);
// Left Right
if (balance > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Right Left
if (balance < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
// Поиск узла с минимальным ключом
Node* minValueNode(Node *node) {
Node *current = node;
while (current->left != NULL)
current = current->left;
return current;
}
// Удаление узла
Node* deleteNode(Node *root, int key) {
// 1. Стандартное удаление из BST
if (root == NULL)
return root;
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else {
// Узел с одним потомком или без
if ((root->left == NULL) || (root->right == NULL)) {
Node *temp = root->left ? root->left : root->right;
// Нет потомков
if (temp == NULL) {
temp = root;
root = NULL;
} else // Один потомок
*root = *temp; // Копируем содержимое
free(temp);
} else {
// Два потомка: берем преемника (наименьший в правом поддереве)
Node *temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
}
// Если дерево было из одного узла
if (root == NULL)
return root;
// 2. Обновление высоты
root->height = 1 + max(height(root->left), height(root->right));
// 3. Проверка баланса
int balance = getBalance(root);
// Балансировка:
// Left Left
if (balance > 1 && getBalance(root->left) >= 0)
return rightRotate(root);
// Left Right
if (balance > 1 && getBalance(root->left) < 0) {
root->left = leftRotate(root->left);
return rightRotate(root);
}
// Right Right
if (balance < -1 && getBalance(root->right) <= 0)
return leftRotate(root);
// Right Left
if (balance < -1 && getBalance(root->right) > 0) {
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
// Поиск значения в дереве
Node* search(Node *root, int key) {
if (root == NULL || root->key == key)
return root;
if (key < root->key)
return search(root->left, key);
else
return search(root->right, key);
}
// Инфиксный обход (для проверки)
void inOrder(Node *root) {
if (root != NULL) {
inOrder(root->left);
printf("%d ", root->key);
inOrder(root->right);
}
}
// Освобождение памяти
void freeTree(Node *root) {
if (root == NULL) return;
freeTree(root->left);
freeTree(root->right);
free(root);
}
int main() {
Node *root = NULL;
int keys[] = {10, 20, 30, 40, 50, 25};
int n = sizeof(keys)/sizeof(keys[0]);
// Вставка элементов
for (int i = 0; i < n; i++)
root = insert(root, keys[i]);
printf("Inorder traversal: ");
inOrder(root);
printf("\n");
// Удаление элемента
root = deleteNode(root, 30);
printf("After deletion of 30: ");
inOrder(root);
printf("\n");
// Поиск элемента
Node *found = search(root, 25);
if (found)
printf("Key 25 found in tree\n");
else
printf("Key 25 not found\n");
freeTree(root);
return 0;
}
```
Объяснение ключевых моментов:
1. **Структура узла**:
- `key` - хранимое значение
- `left`, `right` - указатели на потомков
- `height` - высота поддерева
2. **Балансировка**:
- Вычисляется через разницу высот поддеревьев
- 4 типа вращений: LL, RR, LR, RL
- Вращения поддерживают свойства BST
3. **Операции**:
- `insert()`: вставка с последующей балансировкой
- `deleteNode()`: удаление с балансировкой
- `search()`: поиск элемента
- `inOrder()`: симметричный обход (для проверки)
4. **Особенности**:
- Автоматическая балансировка при операциях
- Гарантированная высота O(log n)
- Рекурсивная реализация операций
Пример работы:
1. Создается дерево с элементами [10, 20, 30, 40, 50, 25]
2. После вставки дерево балансируется
3. Удаляется элемент 30 с последующей балансировкой
4. Выполняется поиск элемента 25
Этот код реализует самобалансирующееся AVL дерево, где все операции (вставка, удаление, поиск) работают за O(log n) времени в худшем случае.
Комментариев нет:
Отправить комментарий