C++进阶：（六）深入浅出分析AVL树：原理与实现

template<class K, class V>
struct AVLTreeNode {
    // 存储键值对（适用于字典场景，如key-value映射）
    pair<K, V> _kv;
    // 左右孩子指针
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    // 父节点指针（关键：用于插入后回溯更新平衡因子）
    AVLTreeNode<K, V>* _parent;
    // 平衡因子（初始为0，新节点无孩子）
    int _bf;

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

template<class K, class V>
class AVLTree {
    // 类型别名：简化节点指针的使用
    typedef AVLTreeNode<K, V> Node;
public:
    // 构造函数：默认初始化根节点为nullptr（空树）
    AVLTree() : _root(nullptr) {}

    // 后续实现：插入、查找、平衡检测等成员函数
    bool Insert(const pair<K, V>& kv);
    Node* Find(const K& key);
    bool IsBalanceTree();
    // 中序遍历（用于验证二叉搜索树性质）
    void InOrder() { _InOrder(_root); cout << endl; }

private:
    // 根节点（私有成员，通过公有接口访问）
    Node* _root;

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

    // 辅助函数：计算节点高度
    int _Height(Node* root);
    // 辅助函数：递归检测平衡
    bool _IsBalanceTree(Node* root);

    // 旋转操作（私有：仅内部平衡调整使用）
    void RotateR(Node* parent);  // 右单旋
    void RotateL(Node* parent);  // 左单旋
    void RotateLR(Node* parent); // 左右双旋
    void RotateRL(Node* parent); // 右左双旋
};

bool AVLTree<K, V>::Insert(const pair<K, V>& kv) {
    // 情况1：树为空，直接创建根节点
    if (_root == nullptr) {
        _root = new Node(kv);
        return true;
    }

    // 情况2：树非空，查找插入位置
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur) {
        if (cur->_kv.first < kv.first) {
            // 键值比当前节点大，去右子树查找
            parent = cur;
            cur = cur->_right;
        } else if (cur->_kv.first > kv.first) {
            // 键值比当前节点小，去左子树查找
            parent = cur;
            cur = cur->_left;
        } else {
            // 键值已存在，插入失败（AVL树不允许重复键）
            return false;
        }
    }

    // 找到插入位置，创建新节点并建立父子关系
    cur = new Node(kv);
    if (parent->_kv.first < kv.first) {
        // 新节点为父节点的右孩子
        parent->_right = cur;
    } else {
        // 新节点为父节点的左孩子
        parent->_left = cur;
    }
    // 建立父节点指针（关键：用于后续回溯）
    cur->_parent = parent;

    // 后续步骤：更新平衡因子并调整平衡（见3.3节）
    // ...
}

// 接3.2节代码，继续在Insert函数中实现
// 步骤2：回溯更新平衡因子
while (parent) {
    // 1. 更新当前父节点的平衡因子
    if (cur == parent->_left) {
        // 新节点是父节点的左孩子，父节点bf--
        parent->_bf--;
    } else {
        // 新节点是父节点的右孩子，父节点bf++
        parent->_bf++;
    }

    // 2. 判断是否需要继续更新或调整平衡
    if (parent->_bf == 0) {
        // 情况1：bf变为0，子树高度不变，停止更新
        break;
    } else if (parent->_bf == 1 || parent->_bf == -1) {
        // 情况2：bf变为±1，子树高度增加1，继续向上更新
        cur = parent;
        parent = parent->_parent;
    } else if (parent->_bf == 2 || parent->_bf == -2) {
        // 情况3：bf变为±2，子树失衡，需要旋转调整
        // 根据失衡类型选择对应的旋转操作
        if (parent->_bf == 2) {
            // 右子树过高，需左单旋或右左双旋
            if (cur->_bf == 1) {
                // 右子树的右子树过高（RR型），左单旋
                RotateL(parent);
            } else {
                // 右子树的左子树过高（RL型），右左双旋
                RotateRL(parent);
            }
        } else { // parent->_bf == -2
            // 左子树过高，需右单旋或左右双旋
            if (cur->_bf == -1) {
                // 左子树的左子树过高（LL型），右单旋
                RotateR(parent);
            } else {
                // 左子树的右子树过高（LR型），左右双旋
                RotateLR(parent);
            }
        }
        // 旋转后子树高度恢复，无需继续向上更新，插入结束
        break;
    } else {
        // 异常情况：bf绝对值超过2（代码逻辑错误）
        assert(false);
    }
}

return true;

        parent (bf=-2)
       /
    subL (bf=-1)
   /
 newNode

void AVLTree<K, V>::RotateR(Node* parent) {
    // 1. 保存关键节点
    Node* subL = parent->_left;    // parent的左孩子（即将成为新根）
    Node* subLR = subL->_right;    // subL的右子树（即将成为parent的左子树）
    Node* parentParent = parent->_parent; // parent的父节点（上层节点）

    // 2. 调整subLR与parent的关系
    parent->_left = subLR;
    if (subLR != nullptr) {
        subLR->_parent = parent;
    }

    // 3. 调整parent与subL的关系
    subL->_right = parent;
    parent->_parent = subL;

    // 4. 调整subL与上层节点的关系
    if (parentParent == nullptr) {
        // 情况1：parent是原根节点，subL成为新根
        _root = subL;
        subL->_parent = nullptr;
    } else {
        // 情况2：parent是上层节点的左/右孩子，subL替换其位置
        if (parentParent->_left == parent) {
            parentParent->_left = subL;
        } else {
            parentParent->_right = subL;
        }
        subL->_parent = parentParent;
    }

    // 5. 重置平衡因子（旋转后subL和parent均平衡）
    parent->_bf = 0;
    subL->_bf = 0;
}

parent (bf=2)
       \
    subR (bf=1)
       \
     newNode

void AVLTree<K, V>::RotateL(Node* parent) {
    // 1. 保存关键节点
    Node* subR = parent->_right;   // parent的右孩子（即将成为新根）
    Node* subRL = subR->_left;     // subR的左子树（即将成为parent的右子树）
    Node* parentParent = parent->_parent; // parent的父节点

    // 2. 调整subRL与parent的关系
    parent->_right = subRL;
    if (subRL != nullptr) {
        subRL->_parent = parent;
    }

    // 3. 调整parent与subR的关系
    subR->_left = parent;
    parent->_parent = subR;

    // 4. 调整subR与上层节点的关系
    if (parentParent == nullptr) {
        // 情况1：parent是原根节点，subR成为新根
        _root = subR;
        subR->_parent = nullptr;
    } else {
        // 情况2：parent是上层节点的左/右孩子，subR替换其位置
        if (parentParent->_left == parent) {
            parentParent->_left = subR;
        } else {
            parentParent->_right = subR;
        }
        subR->_parent = parentParent;
    }

    // 5. 重置平衡因子
    parent->_bf = 0;
    subR->_bf = 0;
}

        parent (bf=-2)
       /
    subL (bf=1)
       \
    subLR (newNode)

void AVLTree<K, V>::RotateLR(Node* parent) {
    // 1. 保存关键节点
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    // 记录subLR的平衡因子（用于后续重置）
    int bf = subLR->_bf;

    // 2. 第一步：以subL为旋转点进行左单旋（转为LL型）
    RotateL(subL);
    // 3. 第二步：以parent为旋转点进行右单旋（恢复平衡）
    RotateR(parent);

    // 4. 根据subLR的原始bf重置平衡因子
    if (bf == 0) {
        subL->_bf = 0;
        subLR->_bf = 0;
        parent->_bf = 0;
    } else if (bf == -1) {
        // subLR的左子树插入节点，parent的右子树高度增加
        subL->_bf = 0;
        subLR->_bf = 0;
        parent->_bf = 1;
    } else if (bf == 1) {
        // subLR的右子树插入节点，subL的左子树高度增加
        subL->_bf = -1;
        subLR->_bf = 0;
        parent->_bf = 0;
    } else {
        assert(false); // 异常情况
    }
}

parent (bf=2)
       \
    subR (bf=-1)
    /
subRL (newNode)

void AVLTree<K, V>::RotateRL(Node* parent) {
    // 1. 保存关键节点
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    // 记录subRL的平衡因子
    int bf = subRL->_bf;

    // 2. 第一步：以subR为旋转点进行右单旋（转为RR型）
    RotateR(subR);
    // 3. 第二步：以parent为旋转点进行左单旋（恢复平衡）
    RotateL(parent);

    // 4. 根据subRL的原始bf重置平衡因子
    if (bf == 0) {
        subR->_bf = 0;
        subRL->_bf = 0;
        parent->_bf = 0;
    } else if (bf == 1) {
        // subRL的右子树插入节点，parent的左子树高度增加
        subR->_bf = 0;
        subRL->_bf = 0;
        parent->_bf = -1;
    } else if (bf == -1) {
        // subRL的左子树插入节点，subR的右子树高度增加
        subR->_bf = 1;
        subRL->_bf = 0;
        parent->_bf = 0;
    } else {
        assert(false); // 异常情况
    }
}

template<class K, class V>
typename AVLTree<K, V>::Node* AVLTree<K, V>::Find(const K& key) {
    Node* cur = _root;
    while (cur) {
        if (cur->_kv.first < key) {
            // 键值比当前节点大，去右子树查找
            cur = cur->_right;
        } else if (cur->_kv.first > key) {
            // 键值比当前节点小，去左子树查找
            cur = cur->_left;
        } else {
            // 找到目标节点，返回指针
            return cur;
        }
    }
    // 遍历结束未找到，返回nullptr
    return nullptr;
}

template<class K, class V>
int AVLTree<K, V>::_Height(Node* root) {
    if (root == nullptr) {
        return 0;
    }
    // 递归计算左、右子树高度
    int leftHeight = _Height(root->_left);
    int rightHeight = _Height(root->_right);
    // 当前节点高度 = 左右子树最大高度 + 1
    return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

template<class K, class V>
bool AVLTree<K, V>::_IsBalanceTree(Node* root) {
    // 空树是AVL树
    if (root == nullptr) {
        return true;
    }

    // 1. 计算当前节点的实际平衡因子（右高 - 左高）
    int leftHeight = _Height(root->_left);
    int rightHeight = _Height(root->_right);
    int actualBf = rightHeight - leftHeight;

    // 2. 检测平衡因子是否异常
    // 情况1：实际平衡因子绝对值超过1（失衡）
    if (abs(actualBf) >= 2) {
        cout << "节点" << root->_kv.first << "高度差异常：实际bf=" << actualBf << endl;
        return false;
    }
    // 情况2：存储的bf与实际bf不相等（平衡因子更新错误）
    if (root->_bf != actualBf) {
        cout << "节点" << root->_kv.first << "平衡因子异常：存储bf=" << root->_bf 
             << "，实际bf=" << actualBf << endl;
        return false;
    }

    // 3. 递归检测左、右子树
    return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}

// 公有接口：对外提供平衡检测
template<class K, class V>
bool AVLTree<K, V>::IsBalanceTree() {
    return _IsBalanceTree(_root);
}

// 测试用例1：常规场景（包含双旋）
void TestAVLTree1() {
    AVLTree<int, int> t;
    // 插入序列：包含LR和RL双旋场景
    int a[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
    for (auto e : a) {
        t.Insert({e, e});
    }

    // 验证二叉搜索树性质：中序遍历应为升序
    cout << "中序遍历结果：";
    t.InOrder(); // 预期：1 2 3 4 5 6 7 14 15 16

    // 验证平衡性质
    if (t.IsBalanceTree()) {
        cout << "TestAVLTree1：AVL树平衡检测通过！" << endl;
    } else {
        cout << "TestAVLTree1：AVL树平衡检测失败！" << endl;
    }
}

// 测试用例2：大量随机值插入（验证性能与稳定性）
void TestAVLTree2() {
    const int N = 100000; // 插入10万个随机值
    vector<int> v;
    v.reserve(N); // 预分配空间，避免扩容开销

    // 生成10万个不重复的随机值
    srand(time(0));
    for (size_t i = 0; i < N; i++) {
        v.push_back(rand() + i); // 加i避免重复
    }

    // 插入性能测试
    size_t insertBegin = clock();
    AVLTree<int, int> t;
    for (auto e : v) {
        t.Insert({e, e});
    }
    size_t insertEnd = clock();
    cout << "TestAVLTree2：插入" << N << "个节点耗时：" << (insertEnd - insertBegin) << "ms" << endl;

    // 平衡检测
    if (t.IsBalanceTree()) {
        cout << "TestAVLTree2：AVL树平衡检测通过！" << endl;
    } else {
        cout << "TestAVLTree2：AVL树平衡检测失败！" << endl;
    }

    // 树高度检测（应接近log2(N) ≈ 17）
    int height = t._Height(t._root);
    cout << "TestAVLTree2：AVL树高度为：" << height << endl;

    // 查找性能测试（查找随机值）
    size_t findBegin = clock();
    for (size_t i = 0; i < N; i++) {
        int key = rand() + i;
        t.Find(key);
    }
    size_t findEnd = clock();
    cout << "TestAVLTree2：查找" << N << "个随机值耗时：" << (findEnd - findBegin) << "ms" << endl;
}

// 主函数：运行测试用例
int main() {
    TestAVLTree1();
    cout << "------------------------" << endl;
    TestAVLTree2();
    return 0;
}