C++ AVL树

我们学习了二叉搜索树，但它存在一个致命缺陷 —— 极端情况下会退化为单支树，导致增删查效率从 O(logN) 退化到 O(N)。今天我们就来学习解决这个问题的方案 ——AVL 树，它是最早的自平衡二叉搜索树，通过自动调整结构保持平衡，确保高效操作。

一、AVL 树的概念

AVL 树是一种自平衡二叉搜索树，得名于发明者 G. M. Adelson-Velsky 和 E. M. Landis（1962 年提出）。它的核心定义的是：

• 要么是一棵空树；
• 要么左右子树都是 AVL 树，且左右子树的高度差的绝对值不超过 1。

关键概念：平衡因子（Balance Factor, BF）

为了方便判断树的平衡状态，我们给每个节点引入平衡因子：

• 平衡因子 = 右子树高度 - 左子树高度；（一般情况下是这个，也可以左-右）
• 合法的 AVL 树节点，平衡因子只能是-1、0、1（对应左子树高、左右等长、右子树高）。

AVL 树的核心价值

AVL 树的高度能稳定控制在 logN 级别（与完全二叉树类似），因此增删查改的时间复杂度始终保持 O(logN)，从根本上解决了普通二叉搜索树的退化问题。

二、AVL树的实现

AVL树的结构

template<class K, class V> struct AVLTreeNode { pair<K, V> _kv; AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent;// 需要parent指针，后续更新平衡因⼦可以看到 int _bf; // balance factor 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: //... private: Node* _root=nullptr; };

AVL树的插⼊

AVL树插⼊⼀个值的⼤概过程

1. 插⼊⼀个值按⼆叉搜索树规则进⾏插⼊。

2. 新增结点以后，只会影响祖先结点的⾼度，也就是可能会影响部分祖先结点的平衡因⼦，所以更新 从新增结点->根结点路径上的平衡因⼦，实际中最坏情况下要更新到根，有些情况更新到中间就可 以停⽌了，具体情况我们下⾯再详细分析。

3. 更新平衡因⼦过程中没有出现问题，则插⼊结束。

4. 更新平衡因⼦过程中出现不平衡，对不平衡⼦树旋转，旋转后本质调平衡的同时，本质降低了⼦树 的⾼度，不会再影响上⼀层，所以插⼊结束。

平衡因⼦更新

1.平衡因⼦=右⼦树⾼度-左⼦树⾼度

2.只有⼦树⾼度变化才会影响当前结点平衡因⼦。

3. 插⼊结点，会增加⾼度，所以新增结点在parent的右⼦树，parent的平衡因⼦++，新增结点在 parent的左⼦树，parent平衡因⼦--。

4. parent所在⼦树的⾼度是否变化决定了是否会继续往上更新。

更新停⽌条件：

1.更新后的parent的平衡因子为0，说明它的高度不变。

2.更新后的parent的平衡因子为1或-1，就要继续往上更新。

3.更新后的parent的平衡因子为-2或2，说明，破坏了平衡，parent所在的⼦树不符合平衡要求，需要旋转处理，旋转的⽬标有两个：1、把 parent⼦树旋转平衡。2、降低parent⼦树的⾼度，恢复到插⼊结点以前的⾼度。所以旋转后也不 需要继续往上更新，插⼊结束。

4.不断更新，更新到根，跟的平衡因⼦是1或-1也停⽌了。

示例：

1.更新到中间结点，3为根的⼦树⾼度不变，不会影响上⼀层，更新结束。

2.最坏情况：更新到根节点为止。

3.更新到10结点，平衡因⼦为2，10所在的⼦树已经不平衡，需要旋转处理。

插入及平衡因子更新的代码实现：

#include<iostream> #include<assert.h> using namespace std; template<class K,class V> struct AVLTreeNode { pair<K, V> _kv; AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; 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: 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->_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) { //旋转 break; } else { assert(false); } } return true; } private: Node* _root = nullptr; };

旋转：

1.保持搜索树的规则。

2.让旋转的树从不满⾜变平衡，其次降低旋转树的⾼度。

旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。

右单旋：

情况1：

情况2：

插入一个-2节点在左子树，并更新平衡因子；

以10为旋转点进行右旋，8成为10的左子树，10变成5的右子树，5成为这棵树新的根。

代码实现：

void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; //记录父亲的父亲节点 Node* Pparent = parent->_parent; subL->_right = parent; parent->_parent=subL; if (parent == _root) { _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; }

左单旋：

情况1：

插入一个10节点在右子树，并更新平衡因子；

以节点6为旋转节点，向左旋转，将3设为6的左子树。

情况2：

插入一个14节点在右子树，并更新平衡因子；

以6为旋转点进行左旋，8成为6的右子树，6变成10的右子树，10成为这棵树新的根。

代码实现：

void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; Node* Pparent = parent->_parent; subR->_left = parent; parent->_parent = subR; 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; }

左右双旋：

下面两个例子可以看到，左边⾼时，如果插⼊位置不是在a⼦树，⽽是插⼊在b⼦树，b⼦树⾼度从h变 成h+1，引发旋转，右单旋⽆法解决问题，右单旋后，我们的树依旧不平衡。右单旋解决的纯粹的左边 ⾼，但是插⼊在b⼦树中，10为跟的⼦树不再是单纯的左边⾼，对于10是左边⾼，但是对于5是右边 ⾼，需要⽤两次旋转才能解决，以5为旋转点进⾏⼀个左单旋，以10为旋转点进⾏⼀个右单旋，这棵树 这棵树就平衡了。

上面两张图分别为左右双旋中h==0和h==1具体场景分析，下⾯我们将a/b/c⼦树抽象为⾼度h的AVL ⼦树进⾏分析，另外我们需要把b⼦树的细节进⼀步展开为8和左⼦树⾼度为h-1的e和f⼦树，因为 我们要对b的⽗亲5为旋转点进⾏左单旋，左单旋需要动b树中的左⼦树。b⼦树中新增结点的位置 不同，平衡因⼦更新的细节也不同，通过观察8的平衡因⼦不同，这⾥我们要分三个场景讨论。

• 场景1：h>=1时，新增结点插⼊在e⼦树，e⼦树⾼度从h-1并为h并不断更新8->5->10平衡因⼦， 引发旋转，其中8的平衡因⼦为-1，旋转后8和5平衡因⼦为0，10平衡因⼦为1。

• 场景2：h>=1时，新增结点插⼊在f⼦树，f⼦树⾼度从h-1变为h并不断更新8->5->10平衡因⼦，引 发旋转，其中8的平衡因⼦为1，旋转后8和10平衡因⼦为0，5平衡因⼦为-1。

• 场景3：h==0时，a/b/c都是空树，b⾃⼰就是⼀个新增结点，不断更新5->10平衡因⼦，引发旋 转，其中8的平衡因⼦为0，旋转后8和10和5平衡因⼦均为0。

代码实现：

void RotateLR(Node* parent) { //提前记录平衡因子 Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(parent->_left); RotateR(parent); if (bf == -1) { subLR->_bf = 0; subL->_bf = 0; parent->_bf =1; } else if (bf == 1) { subLR->_bf = 0; subL->_bf = -1; parent->_bf = 0; } else if (bf == 0) { subLR->_bf = 0; subL->_bf = 0; parent->_bf = 0; } else { assert(false); } }

右左双旋：

右左双旋逻辑跟左右双旋一样，只不过方向不同，就不再演示。

代码实现：

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

三、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; }

四、AVL树的平衡检测

我们实现的AVL树是否合格，我们通过检查左右⼦树⾼度差的的程序进⾏反向验证，同时检查⼀下结点 的平衡因⼦更新是否出现了问题。

int _Height(Node* root) { 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) { if (root == nullptr) return true; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); int diff = rightHeight - leftHeight; if (abs(diff) >= 2) { cout << "高度差异常" << endl; return false; } if (root->_bf != diff) { cout << "平衡因子异常" << endl; return false; } return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right); }

五、AVL 树特点总结

• 严格平衡：任何节点左右高度差 ≤ 1
• 查询极快：O(log n)
• 插入删除代价稍高：需要频繁旋转
• 适合读多写少的场景（如数据库索引、内存缓存）