Что такое сбалансированное дерево

1️⃣ Как кратко ответить

Сбалансированное дерево — это структура данных, в которой высота дерева поддерживается минимально возможной для заданного количества узлов, чтобы обеспечить эффективные операции поиска, вставки и удаления. Примеры включают AVL-деревья и красно-черные деревья.

2️⃣ Подробное объяснение темы

Сбалансированное дерево — это тип структуры данных, который используется для хранения данных в виде иерархии, где каждый узел имеет не более двух потомков. Основная цель сбалансированного дерева — поддерживать высоту дерева минимально возможной, что позволяет выполнять операции поиска, вставки и удаления за логарифмическое время.

Зачем это нужно

В несбалансированном дереве, например, в обычном бинарном дереве поиска, в худшем случае высота дерева может стать линейной, что приводит к ухудшению производительности операций до O(n). Сбалансированные деревья решают эту проблему, поддерживая высоту дерева порядка O(log n), где n — количество узлов в дереве. Это обеспечивает более эффективное выполнение операций.

Примеры сбалансированных деревьев

1. AVL-дерево: Это бинарное дерево поиска, в котором для каждого узла разница высот его левого и правого поддеревьев не превышает 1. При каждой операции вставки или удаления дерево автоматически балансируется.

2. Красно-черное дерево: Это бинарное дерево поиска, в котором каждый узел имеет дополнительный атрибут — цвет (красный или черный). Дерево поддерживает балансировку с помощью набора правил, которые ограничивают количество последовательных красных узлов и обеспечивают, что путь от корня до любого листа содержит одинаковое количество черных узлов.

Как это работает

Рассмотрим пример AVL-дерева:

#include <iostream>
using namespace std;
​
// Структура для представления узла дерева
struct Node {
    int key;
    Node* left;
    Node* right;
    int height;
};
​
// Функция для получения высоты узла
int height(Node* N) {
    return (N == nullptr) ? 0 : N->height;
}
​
// Функция для создания нового узла
Node* newNode(int key) {
    Node* node = new Node();
    node->key = key;
    node->left = nullptr;
    node->right = nullptr;
    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* N) {
    return (N == nullptr) ? 0 : height(N->left) - height(N->right);
}
​
// Вставка нового ключа в поддерево с корнем node
Node* insert(Node* node, int key) {
    // 1. Выполнение стандартной вставки в бинарное дерево поиска
    if (node == nullptr)
        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 вращений
​
    // Левый левый случай
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);
​
    // Правый правый случай
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);
​
    // Левый правый случай
    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
​
    // Правый левый случай
    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
​
    // Возврат неизмененного узла указателя
    return node;
}
​
// Функция для вывода дерева в порядке возрастания
void preOrder(Node* root) {
    if (root != nullptr) {
        cout << root->key << " ";
        preOrder(root->left);
        preOrder(root->right);
    }
}
​
int main() {
    Node* root = nullptr;
​
    // Вставка узлов
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);
​
    // Вывод дерева
    cout << "Preorder traversal of the constructed AVL tree is \n";
    preOrder(root);
​
    return 0;
}

Объяснение кода

• Структура Node: Определяет узел дерева, содержащий ключ, указатели на левого и правого потомков, а также высоту узла.
• Функция height: Возвращает высоту узла или 0, если узел равен nullptr.
• Функция newNode: Создает новый узел с заданным ключом и инициализирует его как лист.
• Функции rightRotate и leftRotate: Выполняют правое и левое вращения соответственно, чтобы сбалансировать дерево.
• Функция getBalance: Возвращает разницу высот левого и правого поддеревьев узла.
• Функция insert: Вставляет новый ключ в дерево, обновляет высоты узлов и выполняет вращения для поддержания баланса.
• Функция preOrder: Выводит дерево в порядке возрастания ключей.
• Функция main: Демонстрирует вставку узлов в AVL-дерево и выводит его в порядке возрастания.

Сбалансированные деревья, такие как AVL и красно-черные деревья, широко используются в системах, где важна производительность операций поиска, например, в базах данных и файловых системах.