2.5-数据结构：AVL树

2.5-AVL树

🌲 定义与性质

AVL树（Adelson-Velsky and Landis Tree）是最早发明的自平衡二叉搜索树，通过维护平衡因子确保树的高度始终为 O(log N)。其核心特性为：

• 平衡因子：任意节点的左右子树高度差绝对值不超过 1
• 旋转操作：通过四种旋转操作（左旋、右旋、左右旋、右左旋）动态调整平衡

⚖️ 平衡因子

每个节点的平衡因子计算公式：

平衡因子 = 右子树高度 - 左子树高度

平衡因子范围：[-1, 0, 1]

🔄 旋转操作类型

🖥️ 核心代码实现（C++）

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;

// 定义AVL树节点结构
template<class K, class V>
struct AVLTreeNode {
    AVLTreeNode<K, V>* _left;  // 左子节点指针
    AVLTreeNode<K, V>* _right; // 右子节点指针
    AVLTreeNode<K, V>* _parent; // 父节点指针
    pair<K, V> _kv;  // 键值对
    int _bf; // balance factor 平衡因子

    // 构造函数，初始化节点
    AVLTreeNode(const pair<K, V>& kv)
    : _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0) {}
};

// 定义AVL树类
template<class K, class V>
class AVLTree {
    typedef AVLTreeNode<K, V> Node;
public:
    // 插入键值对
    bool Insert(const pair<K, V>& kv) {
        if(_root == nullptr) {
            _root = new Node(kv);
            return true;
        }
        Node* parent = nullptr;
        Node* cur = _root;
        // 查找插入位置
        while(cur) {
            if (cur->_kv.first > kv.first) {
                parent = cur;
                cur = cur->_left;
            } else if (cur->_kv.first < kv.first) {
                parent = cur;
                cur = cur->_right;
            } else {
                return false;
            }
        }
        cur = new Node(kv);
        // 插入新节点
        if (parent->_kv.first > kv.first) {
            parent->_left = cur;
        } else if (parent->_kv.first < kv.first) {
            parent->_right = cur;
        }
        cur->_parent = parent;

        // 更新平衡因子
        while (parent) {
            if (cur == parent->_right) {
                parent->_bf++;
            } else {
                parent->_bf--;
            }

            if (parent->_bf == 1 || parent->_bf == -1) {
                parent = parent->_parent;
                cur = cur->_parent;
            } else if (parent->_bf == 0) {
                break;
            } else if (parent->_bf == 2 || parent->_bf == -2) {
                // 旋转调整平衡
                if (parent->_bf == 2 && cur->_bf == 1) {
                    RotateL(parent); // 左单旋
                } else if (parent->_bf == -2 && cur->_bf == -1) {
                    RotateR(parent); // 右单旋
                } else if (parent->_bf == -2 && cur->_bf == 1) {
                    RotateLR(parent); // 左右双旋
                } else if (parent->_bf == 2 && cur->_bf == -1) {
                    RotateRL(parent); // 右左双旋
                }
                break;
            } else {
                assert(false);
            }
        }
        return true;
    }

    // 中序遍历AVL树
    void InOrder() {
        _InOrder(_root);
        cout << endl;
    }
    // 递归中序遍历辅助函数
    void _InOrder(Node* root) {
        if (root == nullptr) return;
        _InOrder(root->_left);
        cout << root->_kv.first << " ";
        _InOrder(root->_right);
    }

    // 判断AVL树是否平衡
    bool IsBalance() {
        return _IsBalance(_root);
    }

private:
    Node* _root = nullptr;

    // 左单旋
    void RotateL(Node* parent) {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        // 处理 subRL 与 parent 的连接
        parent->_right = subRL;
        if (subRL) {
            subRL->_parent = parent;
        }

        // 保存原父节点的父节点
        Node* pparent = parent->_parent;

        // 处理 subR 与 parent 的连接
        subR->_left = parent;
        parent->_parent = subR;

        // 处理 subR 与 pparent 的连接
        if (pparent == nullptr) {
            _root = subR;
            subR->_parent = nullptr;
        } else {
            if (pparent->_left == parent) {
                pparent->_left = subR;
            } else {
                pparent->_right = subR;
            }
            subR->_parent = pparent;
        }

        // 更新平衡因子
        parent->_bf = subR->_bf = 0;
    }

    // 右单旋
    void RotateR(Node* parent) {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        // 处理 subLR 与 parent 的连接
        parent->_left = subLR;
        if (subLR) {
            subLR->_parent = parent;
        }

        // 保存原父节点的父节点
        Node* pparent = parent->_parent;

        // 处理 subL 与 parent 的连接
        subL->_right = parent;
        parent->_parent = subL;

        // 处理 subL 与 pparent 的连接
        if (pparent == nullptr) {
            _root = subL;
            subL->_parent = nullptr;
        } else {
            if (pparent->_left == parent) {
                pparent->_left = subL;
            } else {
                pparent->_right = subL;
            }
            subL->_parent = pparent;
        }

        // 更新平衡因子
        parent->_bf = subL->_bf = 0;
    }

    // 左右双旋
    void RotateLR(Node* parent) {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        RotateL(parent->_left);
        RotateR(parent);
        int bf = subLR->_bf;

        // 根据subLR的平衡因子更新各节点平衡因子
        if (bf == 1) {
            parent->_bf = -1;
            subLR->_bf = 0;
            subL->_bf = -1;
        } else if (bf == -1) {
            parent->_bf = 1;
            subLR->_bf = 0;
            subL->_bf = -1;
        } else if (bf == 0) {
            parent->_bf = 0;
            subLR->_bf = 0;
            subL->_bf = 0;
        } else {
            assert(false);
        }
    }

    // 右左双旋
    void RotateRL(Node* parent) {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        RotateR(parent->_right);
        RotateL(parent);
        int bf = subRL->_bf;

        // 根据subRL的平衡因子更新各节点平衡因子
        if (bf == 1) {
            parent->_bf = -1;
            subRL->_bf = 0;
            subR->_bf = 0;
        } else if (bf == -1) {
            parent->_bf = 0;
            subRL->_bf = 0;
            subR->_bf = 1;
        } else if (bf == 0) {
            parent->_bf = 0;
            subRL->_bf = 0;
            subR->_bf = 0;
        } else {
            assert(false);
        }
    }

    // 计算树的高度
    int _Height(Node* root) {
        if(root == nullptr) { return 0; }
        int leftH = _Height(root->_left);
        int rightH = _Height(root->_right);

        return leftH > rightH ? leftH + 1 : rightH + 1;
    }

    // 判断以root为根的子树是否平衡
    bool _IsBalance(Node* root) {
        if (root == nullptr) { return true; }
        return abs(_Height(root->_left) - _Height(root->_right)) < 2
            && _IsBalance(root->_left) && _IsBalance(root->_right);
    }
};

// 测试AVL树的插入和平衡性
void test_AVLTree() {
    int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    AVLTree<int, int> t1;
    for (auto e : a) {
        t1.Insert(make_pair(e, e));
    }

    t1.InOrder();
    cout << t1.IsBalance() << endl;
}

（尝试拿deepseek丰富前面的文案。）