AVL 树是最早的自平衡二叉搜索树:空树算 AVL;非空时左右子树都是 AVL,且左右子树高度差的绝对值不超过 1。这个结构由 Adelson-Velsky 和 Landis 在 1962 年的论文《An algorithm for the organization of information》中提出,"AVL"就是两人姓氏的首字母。

高度差为什么定成 1 而不是 0?两个结点的树,不管孩子挂在哪边,高度差只能是 1;四个结点的某些形态也一样。规则要覆盖所有规模,就不能写成"必须差 0"。

平衡因子的符号是一个约定

要让"差多少"变成能随时检查的一个数,给每个结点加一个整数:

_bf = 右子树高度 - 左子树高度

按这个定义,合格结点的 _bf 只可能是 −1、0、1,出现 ±2 就说明这棵子树已经失衡。存子树高度也能判断,但要做减法;存差值把"是否失衡"和"往哪边偏"压进同一个数,看到 parent 是 ±2、再看孩子 cur 的符号,立刻能决定单旋还是双旋、往哪边转。

把每个结点的平衡因子写在结点上方:8 是 −1,3 是 1,其余都是 0,整棵树每个结点的绝对值都不超过 1

符号方向是约定,不同教材有写成"左减右"的。选哪一种都行,但三个地方必须一致:插入时按方向加减、判断 ±2 时按方向选旋转、校验时按同一方向算差值。任何一处反了,症状都是树转得动、转完更歪。

结点需要指向父亲的指针,因为更新平衡因子和旋转后重新挂接都要往上走:

#include <cassert>
#include <iostream>
#include <utility>
 
template<class K, class V>
struct AVLTreeNode
{
    std::pair<K, V> _kv;
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    AVLTreeNode<K, V>* _parent;
    int _bf;
 
    AVLTreeNode(const std::pair<K, V>& kv)
        : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0)
    {}
};

课件说"AVL 树并不是必须要平衡因子",这句是对的:差值只是实现手段,也可以用"存高度"或"每次现算"来维护平衡,只是慢。

下面各节给的是 template<class K, class V> class AVLTree 的成员函数,类里有 typedef AVLTreeNode<K, V> Node;、根指针 Node* _root = nullptr;,四个旋转函数和 _Height、_IsBalanceTree 是私有成员。

插入后只有一条祖先链会变

插入本身还是二叉搜索树的走位,新结点挂到某个空位上。变化只发生在新结点到根的这一条链上:链外的结点,左右子树一个结点都没多,高度没变,平衡因子也不该动。

更新规则一句话:新结点在 parent 的右子树,_bf 加 1;在左子树,减 1。三个刹车对应三个不同的问题:

更新后 parent->_bf怎么来的子树高度变了吗怎么办
0−1→0 或 1→0没变,矮的一侧被补齐停
±10→±1涨了 1继续往上
±2±1→±2旋转后回到原来的高度转完就停

第一行最容易背反:归零说明新结点补在了矮的那边,两边被拉平,子树高度还是原来那一侧的高度,上一层完全感觉不到变化。

也正因为如此,更新不需要每次重新求子树高度:高度有没有变、变高还是变矮,都由下层那一轮已经算好的结果传上来,parent 只做加减。

插入一个结点后沿 1、3 向上更新:1 从 0 变成 −1,3 从 1 变成 0,子树高度没变,更新在 3 这里停住

走最坏情况也可能一路更新到根:

    bool Insert(const std::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->_right;
            }
            else if (cur->_kv.first > kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }
 
        cur = new Node(kv);
        if (parent->_kv.first < kv.first)
        {
            parent->_right = cur;
        }
        else
        {
            parent->_left = cur;
        }
        cur->_parent = parent;
 
        while (parent)
        {
            if (cur == parent->_left)
            {
                --parent->_bf;
            }
            else
            {
                ++parent->_bf;
            }
 
            if (parent->_bf == 0)
            {
                break;
            }
            else if (parent->_bf == 1 || parent->_bf == -1)
            {
                cur = parent;
                parent = parent->_parent;
            }
            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)
                {
                    RotateRL(parent);
                }
                else
                {
                    RotateLR(parent);
                }
                break;
            }
            else
            {
                assert(false);
            }
        }
        return true;
    }

课件给的 Insert 在 ±2 分支里只有一句 break; 和注释"不平衡了,旋转处理",四个旋转函数要到后面几节才出现。两段要拼起来读,照抄前半段,插入永远不旋转,得到的只是一棵普通二叉搜索树。

±2 出现时,cur 一定是 parent 更高的那一侧的孩子。因为 parent 能从 ±1 爬到 ±2,上一轮 cur 刚被赋成这个孩子,它当时的 _bf 才从 0 变成 ±1。所以四种组合(2 配 1、−2 配 −1、2 配 −1、−2 配 1)已经穷举,没有第五种。

右单旋:把 b 子树过继给 10

旋转守两条原则:不破坏搜索树的中序;把子树高度降回插入之前。

右单旋的抽象形态:10 为根,左孩子 5,5 的左右子树是 a、b,10 的右边是 c,三棵子树高度都是 h。新结点插进 a,a 从 h 变成 h+1,10 的 _bf 从 −1 变成 −2。

b 为什么必须过继给 10?旋转前有 5 小于 b 里所有值,b 里所有值又小于 10。5 当新根、10 当 5 的右孩子之后,b 挂 5 的右边合法,挂 10 的左边也合法,正好平移过去,中序序列一个字都不变。转完子树高度回到 h+2,和插入之前一样,所以上层不用再改。

右单旋的三步:a 长高后 10 的 bf 变成 −2;把 5 的右子树 b 过继给 10 的左指针,把 10 挂到 5 的右指针上,5 顶上成为新根

一次右单旋动六条线,每一处漏掉都会断链:

    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
 
        parent->_left = subLR;              // 1. b 过继给 10 的左
        if (subLR)
        {
            subLR->_parent = parent;        // 2. b 的父亲改指 10
        }
 
        Node* parentParent = parent->_parent;   // 3. 先存上层,再改 parent
 
        subL->_right = parent;              // 4. 10 挂到 5 的右边
        parent->_parent = subL;             // 5. 10 的父亲改指 5
 
        if (parentParent == nullptr)
        {
            _root = subL;                   // 6a. 原来就是整棵树的根
            subL->_parent = nullptr;
        }
        else
        {
            if (parent == parentParent->_left)
            {
                parentParent->_left = subL; // 6b. 接回上层
            }
            else
            {
                parentParent->_right = subL;
            }
            subL->_parent = parentParent;
        }
 
        parent->_bf = 0;
        subL->_bf = 0;
    }

parentParent 必须在 parent->_parent = subL; 之前取。若先改父亲指针再读 parent->_parent,拿到的是 subL,上层直接断链——树还能查找、还能中序输出,只是某个结点的 _bf 差了 1。

左单旋与课件里残留的那句话

左单旋是镜像:10 右边太高,15 是右孩子,15 的左子树 b 夹在 10 和 15 之间,过继给 10 的右边,15 成为新根。

左单旋:10 的 bf 从 1 变成 2;把 15 的左子树 b 过继给 10 的右指针,再把 10 挂成 15 的左孩子,15 成为新根,bf 归零

    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
 
        parent->_right = subRL;
        if (subRL)
        {
            subRL->_parent = parent;
        }
 
        Node* parentParent = parent->_parent;
 
        subR->_left = parent;
        parent->_parent = subR;
 
        if (parentParent == nullptr)
        {
            _root = subR;
            subR->_parent = nullptr;
        }
        else
        {
            if (parent == parentParent->_left)
            {
                parentParent->_left = subR;
            }
            else
            {
                parentParent->_right = subR;
            }
            subR->_parent = parentParent;
        }
 
        parent->_bf = 0;
        subR->_bf = 0;
    }

课件"左单旋"那一节的正文第一句写的是"他代表了所有右单旋的场景",和标题、以及同段后半句"10 的平衡因子从 1 变成 2,右边太高,需要往左旋转"自相矛盾。这段是从右单旋整段复制过来的,改标题时漏改了中间这句;按"左单旋"读,其余描述(15 当新根、10 变左孩子)都是对的。

方向记法一句话:哪边高,就把哪边的孩子提上来。

双旋:枢纽的旧平衡因子决定三个新值

左右双旋(LR)的触发条件是折线:10 左边高,但高的部分长在 5 的右子树 b 里。对 10 来说左边更高,对 5 来说它自己右边更高,一条折线用右单旋扳不直。做法是先对内侧做一次反向单旋,把折线捋直,再对外侧做标准单旋:先 RotateL(parent->_left),再 RotateR(parent)。

难点不在转,在转完的平衡因子。两次单旋各自把两个端点的 _bf 置零,三个结点的旧值全被覆盖,所以必须先把枢纽 subLR 的 _bf 存下来:

    void RotateLR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        int bf = subLR->_bf;
 
        RotateL(parent->_left);
        RotateR(parent);
 
        if (bf == 0)
        {
            subL->_bf = 0;
            subLR->_bf = 0;
            parent->_bf = 0;
        }
        else if (bf == -1)
        {
            subL->_bf = 0;
            subLR->_bf = 0;
            parent->_bf = 1;
        }
        else if (bf == 1)
        {
            subL->_bf = -1;
            subLR->_bf = 0;
            parent->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }

左右双旋的抽象图:b 子树展开成结点 8 和两棵高 h−1 的 e、f;8 的 bf 为 −1 时新结点落在 e,为 1 时落在 f,为 0 时 8 自己就是新结点

三次转动之后三个结点的相对位置已经固定,各剩多少高度差,完全取决于新结点原来挂在枢纽左边、右边,还是枢纽本身。这件事恰好被枢纽旋转前的 _bf 记下来:

枢纽 subLR->_bfsubL(5)subLR(8)parent(10)
0(8 自己是新结点)000
−1(新结点在 e)001
1(新结点在 f)−100

右左双旋(RL)完全对称:subR 是 parent 的右孩子,subRL 是枢纽,先 RotateR(parent->_right) 再 RotateL(parent),按 subRL 的旧值重建三个 _bf。

右左双旋的抽象图:12 是枢纽,bf 为 −1 时新结点落在 e、为 1 时落在 f、为 0 时 12 自己就是新结点;转完 15、12、10 的值按这三种情况分别确定

    void RotateRL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        int bf = subRL->_bf;
 
        RotateR(parent->_right);
        RotateL(parent);
 
        if (bf == 0)
        {
            subR->_bf = 0;
            subRL->_bf = 0;
            parent->_bf = 0;
        }
        else if (bf == 1)
        {
            subR->_bf = 0;
            subRL->_bf = 0;
            parent->_bf = -1;
        }
        else if (bf == -1)
        {
            subR->_bf = 1;
            subRL->_bf = 0;
            parent->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }

一次插入最多做一次双旋(两次单旋),旋转后子树高度恢复,链在这里断开,不会连锁。

高度上界与校验

课件写"AVL 树整体结点数量和分布和完全二叉树类似,高度可以控制在 logN",这句不准确:log₂N 是完全二叉树的界,AVL 的界更松,要自己推。

反过来问:高度为 h 的 AVL 树最少几个结点?要让高度尽量大、结点尽量少,根的两棵子树就得尽量矮,但高度差最多 1,所以一棵高 h−1、一棵高 h−2:

N(h) = N(h-1) + N(h-2) + 1,  N(1) = 1,  N(2) = 2

和斐波那契同形,指数增长:1、2、4、7、12、20、33、54、88、143…反解递推得到 h ≤ 1.44 log₂(N + 2)。这是 AVL 树高度上界的标准结论。

查找和普通二叉搜索树一样,O(logN):

    Node* 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;
            }
        }
        return nullptr;
    }

自己实现的树是否合格,靠三件事验证:中序有序,说明旋转没破坏搜索树;每个结点真实高度差绝对值不超过 1,说明树确实平衡;每个结点存的 _bf 等于按定义算出的差值,说明账本没错。第三条最关键,前两条只能说明"现在看起来还行",第三条能指出是哪一次插入把账算错了。

    void InOrder() const
    {
        _InOrder(_root);
        std::cout << '\n';
    }
 
    int Height() const
    {
        return _Height(_root);
    }
 
    bool IsBalanceTree() const
    {
        return _IsBalanceTree(_root);
    }
 
private:
    void _InOrder(Node* root) const
    {
        if (root == nullptr)
        {
            return;
        }
        _InOrder(root->_left);
        std::cout << root->_kv.first << ' ';
        _InOrder(root->_right);
    }
 
    int _Height(Node* root) const
    {
        if (root == nullptr)
        {
            return 0;
        }
        int leftHeight = _Height(root->_left);
        int rightHeight = _Height(root->_right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }
 
    bool _IsBalanceTree(Node* root) const
    {
        if (root == nullptr)
        {
            return true;
        }
 
        int leftHeight = _Height(root->_left);
        int rightHeight = _Height(root->_right);
        int diff = rightHeight - leftHeight;
 
        if (diff < -1 || diff > 1)
        {
            std::cout << root->_kv.first << " 高度差异常\n";
            return false;
        }
        if (root->_bf != diff)
        {
            std::cout << root->_kv.first << " 平衡因子异常\n";
            return false;
        }
 
        return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
    }
int main()
{
    AVLTree<int, int> t;
    int a[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
    for (int e : a)
    {
        t.Insert({e, e});
    }
    t.InOrder();                              // 1 2 3 4 5 6 7 14 15 16
    std::cout << t.IsBalanceTree() << '\n';   // 1
    std::cout << t.Height() << '\n';          // 4
    return 0;
}

_IsBalanceTree 对每个结点现场用 _Height 求左右高度,代价是 O(N·h):树平衡时 O(N logN),树塌成链就退到 O(N²)。它只能放在测试和断言里,塞进插入路径会把 AVL 的优势全部吃掉。

课件那段随机测试直接用 vector、clock()、srand、rand,摘出来单独编译时要自己补 <vector>、<ctime>、<cstdlib> 三个头文件。

删除课件明确说不讲。方向和插入对称:先按二叉搜索树删(零到一个孩子直接接上,两个孩子用后继替换),再从"实际变矮的那个结点"的父亲开始往上改平衡因子;变矮会让祖先的 _bf 往反方向走,出现 ±2 就旋转。差别在传播方式:插入的链会因为一次旋转立刻断开,删除不会,可能一路连锁到根,所以删除最坏要做 O(logN) 次旋转。两者复杂度都是 O(logN),实现难度差一个量级。

AVL 与红黑树的取舍

AVL 把左右高度差锁在 1 以内,树更矮,查找路径更短,查询略快。代价是每次插入删除都要维护这个严格的整数账本,结构变动更频繁。

红黑树只要求最长路径不超过最短路径的两倍,平衡更松,查找比 AVL 略慢,但插入最多两次旋转、删除最多三次,改结构的成本更低。标准库的 std::map/std::set 选的是红黑树,Linux 内核管虚拟内存区域和高精度定时器也用红黑树,理由一致:读写混合的场景里,改结构的稳定性比查找再快一点更值钱。

两者都是 O(logN) 的增删查,差别在成本放在哪一侧。AVL 适合读远多于写的场合;红黑树适合插入删除频繁的场合。