【C++】AVL树的底层以及实现

AVL树的底层及其实现

AVL树是一种自平衡的二叉搜索树，以其发明者Georgy Adelson-Velsky和Evgenii Landis的名字命名。它的特点是对于每个节点，左子树和右子树的高度最多相差1，因此AVL树能保持较高的查询效率。AVL树的插入和删除操作需要额外的旋转操作来保持平衡，这导致其时间复杂度为O(log n)。

AVL树的结构

AVL树的每个节点结构通常包含三个部分：

1. 值: 节点存储的数据。
2. 左子树指针: 指向节点的左子节点。
3. 右子树指针: 指向节点的右子节点。
4. 高度: 节点的高度信息，用于平衡的计算。

以下是一个简单的AVL树节点的结构定义：

struct AVLNode {
    int key;                // 节点的值
    int height;            // 节点的高度
    AVLNode* left;         // 左子节点
    AVLNode* right;        // 右子节点

    AVLNode(int value) : key(value), height(1), left(nullptr), right(nullptr) {}
};

插入操作

在AVL树中插入新节点时，首先执行正常的二叉搜索树插入操作，然后检查每个祖先节点的高度，并进行必要的旋转，以保持AVL树的平衡。旋转分为四种情况：

• 右旋: 当某个节点的左子树比右子树高2，并且左子树的左子树较高时，进行右旋。
• 左旋: 当某个节点的右子树比左子树高2，并且右子树的右子树较高时，进行左旋。
• 左-右旋: 当某个节点的左子树比右子树高2，并且左子树的右子树较高时，先左旋左子树，再右旋。
• 右-左旋: 当某个节点的右子树比左子树高2，并且右子树的左子树较高时，先右旋右子树，再左旋。

下面是AVL树的插入实现：

class AVLTree {
private:
    AVLNode* root;

    int getHeight(AVLNode* node) {
        return node ? node->height : 0;
    }

    int getBalance(AVLNode* node) {
        return node ? getHeight(node->left) - getHeight(node->right) : 0;
    }

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

        // 进行旋转
        x->right = y;
        y->left = T2;

        // 更新高度
        y->height = std::max(getHeight(y->left), getHeight(y->right)) + 1;
        x->height = std::max(getHeight(x->left), getHeight(x->right)) + 1;

        return x;
    }

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

        // 进行旋转
        y->left = x;
        x->right = T2;

        // 更新高度
        x->height = std::max(getHeight(x->left), getHeight(x->right)) + 1;
        y->height = std::max(getHeight(y->left), getHeight(y->right)) + 1;

        return y;
    }

    AVLNode* insert(AVLNode* node, int key) {
        // 进行标准的BST插入
        if (!node) {
            return new AVLNode(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 = 1 + std::max(getHeight(node->left), getHeight(node->right)));

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

        // 左左情况
        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;
    }

public:
    AVLTree() : root(nullptr) {}

    void insert(int key) {
        root = insert(root, key);
    }
};

删除操作

AVL树的删除操作与插入类似，也需要注意平衡。在删除一个节点后，需检查节点的平衡因子，并进行适当的旋转以保持树的平衡。删除过程具体实现略有复杂，需结合插入时的结构进行调整，这里不再详细展开。

总结

AVL树通过高度平衡的机制，确保在最坏情况下也能提供O(log n)的时间复杂度进行查找、插入和删除操作。尽管AVL树在实现上相对复杂，特别是旋转的处理，但它的高效性和自平衡特性在需要频繁插入和删除的场景中，无疑具有非常重要的意义。AVL树广泛应用于数据库、内存管理以及各种需要动态数据结构的领域中。