1. AVL树特点

AVL树是一种自平衡二叉搜索树，其核心特点如下：

• 左右子树高度差不超过1
• 平衡因子：右子树高度 - 左子树高度
• 通过旋转操作维持平衡

2. 模拟实现

2.1 成员结构

代码语言：javascript

AI代码解释

template<class K, class V>
struct treenode
{
    std::pair<K, V> _kv;
    treenode* _left;
    treenode* _right;
    treenode* _father;  // 指向父节点的指针
    int _bf;            // 平衡因子
    
    treenode(const std::pair<K, V>& kv)
        : _kv(kv)
        , _left(nullptr)
        , _right(nullptr)
        , _father(nullptr)
        , _bf(0)
    { }
};

设计要点：

• 和搜索二叉树一样，有左右节点和一个pair键值对
• 由于需要从下到上处理高度差问题，因此需要指向父节点的指针
• _bf负责存储平衡因子

2.2 插入操作

插入操作 = 搜索二叉树插入 + 平衡高度调整

节点更新后平衡因子的三种情况：

1. 平衡因子 = 0（-1→0 或 1→0）：已经平衡，停止更新
2. 平衡因子为 ±1（0→±1）：会影响父节点，继续向上更新
3. 平衡因子为 ±2（-1→-2 或 1→2）：不符合AVL树，需要旋转，旋转完后停止更新

插入主逻辑：

代码语言：javascript

AI代码解释

bool insert(const std::pair<K, V>& kv)
{
    if (_root == nullptr)
    {
        _root = new node(kv);
        return 1;
    }
    
    node* par = nullptr;
    node* cur = _root;
    
    while (cur)
    {
        if (cur->_kv.first < kv.first)
        {
            par = cur;
            cur = cur->_right;
        }
        else if (cur->_kv.first > kv.first)
        {
            par = cur;
            cur = cur->_left;
        }
        else
        {
            return 0;  // 键值已存在
        }
    }
    
    cur = new node(kv);
    if (par->_kv.first < kv.first)
    {
        par->_right = cur;
    }
    else
    {
        par->_left = cur;
    }
    
    // 回溯更新平衡因子
    while (par)
    {
        if (cur == par->_left) par->_bf--;
        else par->_bf++;
        
        if (par->_bf == 0) break;
        else if (par->_bf == 1 || par->_bf == -1)
        {
            cur = par;
            par = par->_father;
        }
        else if (par->_bf == 2 || par->_bf == -2)
        {
            // 需要旋转
            if (par->_bf == -2 && cur->_bf == -1)
            {
                rotateR(par);  // 右单旋
            }
            else if (par->_bf == -2 && cur->_bf == 1)
            {
                rotateLR(par);  // 左右双旋
            }
            else if (par->_bf == 2 && cur->_bf == 1)
            {
                rotateL(par);  // 左单旋
            }
            else if (par->_bf == 2 && cur->_bf == -1)
            {
                rotateRL(par);  // 右左双旋
            }
            else
            {
                assert(0);
            }
            break;
        }
        else
        {
            assert(0);
        }
    }
    return 1;
}

3. 旋转操作

由于造成不平衡可能是左子树或右子树，因此先分为左旋和右旋。

3.1 右旋

右旋用于解决左子树过高的问题。造成左子树不平衡的可能是左左子树或左右子树，因此分为：

1. 右单旋
2. 左右双旋

（1）右单旋

想象有重力：提起左节点，让它变为根节点。

操作步骤：

1. 原来的根节点有三个分支
2. 将原来左节点的右枝砍断，接到原来的根节点上

右单旋的优点：

1. 保持搜索树规则
2. 使树变平衡
3. 降低树高度

结束后平衡因子变化：根节点变为0，右节点变为0