【C++】二叉搜索树+变身 = AVL树

二叉搜索树（Binary Search Tree，简称BST）是一种非常常见的数据结构，具有高效的查找、插入和删除操作。然而，普通的二叉搜索树在某些情况下会退化成一条链表，从而导致这些操作的时间复杂度变为O(n)。为了解决这个问题，我们引入了AVL树（Adelson-Velsky and Landis Tree），这是一种自平衡的二叉搜索树，能够在插入和删除节点后保持树的平衡性，从而保证查找、插入和删除操作均在O(log n)的时间复杂度内完成。

AVL树的基本特性

AVL树的定义是在每个节点中维护一个平衡因子（Balance Factor，BF），即节点的左子树高度减去右子树高度。对于AVL树中的任意节点，其平衡因子的值只能为-1、0或1：

• BF = 0 表示该节点的子树高度相等。
• BF = 1 表示左子树比右子树高1。
• BF = -1 表示右子树比左子树高1。

为了保持AVL树的性质，在插入或删除节点后，AVL树可能会失去平衡，此时需要进行旋转操作来恢复平衡。

AVL树的旋转操作

AVL树的旋转操作主要有四种：

1. 单右旋（LL旋转）：当节点的左子树插入导致不平衡。
2. 单左旋（RR旋转）：当节点的右子树插入导致不平衡。
3. 左右旋（LR旋转）：当节点的左子树右子树插入导致不平衡。
4. 右左旋（RL旋转）：当节点的右子树左子树插入导致不平衡。

AVL树的插入操作

下面是一个AVL树插入操作的C++示例代码：

#include <iostream>
using namespace std;

// AVL树节点
struct Node {
    int key;
    Node* left;
    Node* right;
    int height;

    Node(int k) : key(k), left(nullptr), right(nullptr), height(1) {}
};

// 获取节点高度
int height(Node* node) {
    return node ? node->height : 0;
}

// 获取平衡因子
int getBalance(Node* node) {
    return node ? height(node->left) - height(node->right) : 0;
}

// 右旋
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; // 返回新的根
}

// 左旋
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; // 返回新的根
}

// 插入节点
Node* insert(Node* node, int key) {
    if (!node)
        return new Node(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; // 不允许重复插入

    // 更新节点高度
    node->height = max(height(node->left), height(node->right)) + 1;

    // 检查平衡
    int balance = getBalance(node);

    // 如果不平衡进行旋转
    // LL情况
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);

    // RR情况
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);

    // LR情况
    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // RL情况
    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node; // 返回未更改的节点指针
}

// 中序遍历
void inOrder(Node* root) {
    if (root) {
        inOrder(root->left);
        cout << root->key << " ";
        inOrder(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 << "中序遍历AVL树: ";
    inOrder(root);
    cout << endl;

    return 0;
}

总结

AVL树通过自平衡的方式，在插入和删除操作后确保树的高度差保持在(-1, 0, 1)的范围内，从而保持了二叉搜索树的优势。在实际应用中，AVL树适合于对数据频繁变化的情况，如在线数据库、操作系统调度等场景。本文通过C++示例代码展现了AVL树的基本插入操作，希望能帮助读者深入理解AVL树的工作原理及实现方式。