【数据结构】AVL树

目录

1. AVL的概念

2. AVL树的实现

2.1 AVL树的结构

2.2 AVL树的插入

2.2.1 AVL树插入一个值的大概过程

2.2.2 平衡因子更新

2.2.3 插入结点及更新平衡因子的代码实现

2.3 旋转

2.3.1 旋转的原则

2.3.2 右单旋

2.3.3 右单旋代码实现

2.3.4 左单旋

2.3.5 左单旋代码实现

2.3.6 左右双旋

2.3.7 左右双旋代码实现

2.3.8 右左双旋

2.3.9 右左双旋代码实现

2.4 AVL树的查找

2.5 AVL树平衡检测

2.6 AVL树的删除

1. AVL的概念

• AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis是两个前苏联的科学家，他们在1962年的论文《An algorithm for the organization of information》中发表了它。

• AVL树是最先发明的自平衡二叉查找树：AVL是一颗空树，或者具备下列性质的二叉搜索树：它的左右子树都是AVL树（左右子树也满足AVL一系列特性），且左右子树的高度差的绝对值不超过1。AVL树是一颗高度平衡搜索二叉树，通过控制高度差去控制平衡。

AVL本身是二叉搜索树，但是由于之前二叉搜索树部分，我们所讨论的可能出现的节点插入在一侧的情况，使得二叉搜索树的性能退化。这里AVL树通过上述自身控制高度差的方式，保持二叉搜索树节点分布均衡，保持平衡，避免最坏情况的发生。

• AVL控制高度差的方式有很多，这里我们采用的方法是引入一个平衡因子(balance factor)的概念，每个结点都有一个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1。

需要明确的是AVL树的实现并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡，就像一个风向标一样。

• 思考一下为什么AVL树是高度平衡搜索二叉树，要求高度差不超过1，而不是高度差是0呢？0不是更好的平衡吗？

画画图分析我们发现，不是不想这样设计，而是有些情况是做不到高度差是0的。比如一棵树是2个结点，4个结点等情况下，高度差最好就是1，无法做到高度差是0。

• 通过控制高度差，AVL树的节点分布较为均衡，整体结点数量和分布和完全二叉树类似，高度可以控制在 ，那么增删查改的效率也可以控制在 ，相比二叉搜索树有了本质的提升。

以上面两幅图为例，节点上面的数字就是它的平衡因子，等于2或-2说明这时候不满足AVL性质，我们要进行旋转，使得平衡因子重新为-1、1或0。

2. AVL树的实现

2.1 AVL树的结构

templatestruct AVLTreeNode{// 需要parent指针，后续更新平衡因子可以看到pair _kv;AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;int _bf; // balance factorAVLTreeNode(const pair& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}};templateclass AVLTree{typedef AVLTreeNode Node;public://...private:Node* _root = nullptr;};

AVL树的节点中，比起二叉搜索树，这里多增加一个指针，记录节点父节点的。，形成三叉链结构。（这里三叉链也只是其中一种实现方式。）

2.2 AVL树的插入

2.2.1 AVL树插入一个值的大概过程

1. 插入一个值按二叉搜索树规则进行插入。

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

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

4. 更新平衡因子过程中出现不平衡，需要对不平衡子树旋转，旋转后本质调平衡的同时，本质还降低了子树的高度，不会再影响上一层，所以插入结束。

2.2.2 平衡因子更新

更新原则：
• 平衡因子 = 右子树高度-左子树高度

• 只有子树高度变化才会影响当前结点平衡因子。

• 插入结点，会增加高度，所以新增结点在parent的右子树，parent的平衡因子++，新增结点在parent的左子树，parent平衡因子--

• parent所在子树的高度是否变化决定了是否会继续往上更新
更新停止条件：
• 更新后parent的平衡因子等于0，更新中parent的平衡因子变化为-1->0 或者 1->0，说明更新前parent子树一边高一边低，新增的结点插入在低的那边，插入后parent所在的子树高度不变，不会影响parent的父亲结点的平衡因子，更新结束。

• 更新后parent的平衡因子等于1 或 -1，更新前更新中parent的平衡因子变化为0->1 或者 0->-1，说明更新前parent子树两边一样高，新增的插入结点后，parent所在的子树一边高一边低，parent所在的子树符合平衡要求，但是高度增加了1，会影响parent的父亲结点的平衡因子，所以要继续向上更新。

插入cur节点，parent左子树高度加一，因此parent的平衡因子变为-1，更新到中间结点，3为根的左右子树高度相等，3的平衡因子变为0，不会影响上一层，更新结束。

需要注明的是这里不可能出现2或-2变为1或-1的情况，因为当平衡因子为2、-2时，说明这棵树本身已经不满足AVL树性质，不是AVL树了，我们这时候在讨论插入节点的平衡因子没有意义。

• 更新后parent的平衡因子等于2 或 -2，更新前更新中parent的平衡因子变化为1->2 或者 -1->-2，说明更新前parent子树一边高一边低，新增的插入结点在高的那边，parent所在的子树高的那边更高了，破坏了平衡，parent所在的子树不符合平衡要求，需要旋转处理，旋转的目标有两个：1、把parent子树旋转平衡。2、降低parent子树的高度，恢复到插入结点以前的高度。所以旋转后也不需要继续往上更新，插入结束。

插入cur节点，parent左子树高度加一，平衡因子变为-1，继续往上更新，更新到10结点，平衡因子为2，10所在的子树已经不平衡，需要旋转处理（下文详细讲解旋转具体规则）。

注：同上，这里也不可能出现3、-3变为2、-2的情形，这样没有意义。

• 如果不断更新，更新到根，根的平衡因子是1或-1也停止了。

最坏更新到根停止

2.2.3 插入结点及更新平衡因子的代码实现

bool Insert(const pair& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur)//先按二叉搜索树的规则插入{if (cur->_kv.first _right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first _right = cur;}else{parent->_left = cur;} //因为节点变为三叉链结构，这里我们需要链接父节点cur->_parent = parent;// 按照前文规则，更新平衡因子while (parent){// 更新平衡因子if (cur == parent->_left)parent->_bf--;elseparent->_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;}

2.3 旋转

2.3.1 旋转的原则

1. 保持搜索树的规则

2. 让旋转的树从不满足变平衡

3. 其次降低旋转树的高度（这样上一级的整棵树的高度不变，平衡因子不变）

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

说明：下面的图中，有些结点我们给的是具体值，如10和5等结点，这里是为了方便讲解，实际中是什么值都可以，只要大小关系符合搜索树的性质即可。

2.3.2 右单旋

• 本图1展示的是10为根的树，有a/b/c抽象为三棵高度为h的子树(h>=0)，a/b/c均符合AVL树的要求。10可能是整棵树的根，也可能是一个整棵树中局部的子树的根。这里a/b/c是高度为h的子树，是一种概括抽象表示，他代表了所有右单旋的场景，实际右单旋形态有很多种，具体图2/图3/图4/图5进行了详细描述。

• 在a子树中插入一个新结点，导致a子树的高度从h变成h+1，不断向上更新平衡因子，导致10的平衡因子从-1变成-2，10为根的树左右高度差超过1，违反平衡规则。10为根的树左边太高了，需要往右边旋转，控制两棵树的平衡。

• 旋转核心步骤，因为5 < b子树根节点的值 < 10，将b变成10的左子树，10变成5的右子树，5变成这棵树新的根，符合二叉搜索树的规则（左子树值<根节点<右子树），5的左右子树高度相等，控制了平衡，这棵的高度恢复到了插入之前的h+2，符合旋转原则。插入的是之前10整棵树的一个局部子树，旋转后不会再影响上一层，插入结束了。这时5和10的平衡因子都为0。

以上抽象出a\\b\\c三个子树来说明右单旋的规则，为了进一步验证规则的普适性，以下选择3中情况讨论下。

2.3.3 右单旋代码实现

void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;// 需要注意除了要修改孩子指针指向，还是修改父亲指针指向新父亲parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;//记录祖父节点subL->_right = parent;parent->_parent = subL;// parent有可能是整棵树的根，也可能是局部的子树// 如果是整棵树的根，要修改_root// 如果是局部的指针要跟上一层链接if (parentParent == nullptr){_root = subL;subL->_parent = nullptr;}else{//链接上一层前需要判断父亲节点在祖父节点的左子树还是右子树中if (parent == parentParent->_left){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}parent->_bf = subL->_bf = 0;//更新平衡因子}

2.3.4 左单旋

• 本图6展示的是10为根的树，有a/b/c抽象为三棵高度为h的子树(h>=0)，a/b/c均符合AVL树的要求。10可能是整棵树的根，也可能是一个整棵树中局部的子树的根。这里a/b/c是高度为h的子树，是一种概括抽象表示，他代表了所有左单旋的场景，实际左单旋形态有很多种，具体跟上面右旋类似。

• 在a子树中插入一个新结点，导致a子树的高度从h变成h+1，不断向上更新平衡因子，导致10的平衡因子从1变成2，10为根的树左右高度差超过1，违反平衡规则。10为根的树右边太高了，需要往左边旋转，控制两棵树的平衡。

• 旋转核心步骤，因为10 < b子树的值 < 15，将b变成10的右子树，10变成15的左子树，15变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵的高度恢复到了插入之前的h+2，符合旋转原则。如果插入之前10整棵树的一个局部子树，旋转后不会再影响上一层，插入结束了。对应10、15节点平衡因子更新为0。

2.3.5 左单旋代码实现

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; // parent有可能是整棵树的根，也可能是局部的子树// 如果是整棵树的根，要修改_root// 如果是局部的指针要跟上一层链接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 = subR->_bf = 0;//平衡因子更新为0}

2.3.6 左右双旋

单旋主要针对的是插入在树的一边，导致树一边高的情况。

通过图7和图8可以看到，左边高时，如果插入位置不是在a子树，而是插入在b子树，b子树高度从h变成h+1，引发旋转，右单旋无法解决问题，右单旋后，我们的树依旧不平衡。右单旋解决的纯粹的左边高，但是插入在b子树中，10为跟的子树不再是单纯的左边高，对于10是左边高，但是对于5是右边高，需要用两次旋转才能解决，以5为旋转点进行一个左单旋，使树变成纯粹的一边高，再以10为旋转点进行一个右单旋，这棵树这棵树就平衡了。

• 图7和图8分别为左右双旋中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。

2.3.7 左右双旋代码实现

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//代码可能由于bug,出现其他值，我们这里是防止意外的防御性代码{assert(false);}}

2.3.8 右左双旋

• 跟左右双旋类似，下面我们将a/b/c子树抽象为高度h的AVL子树进行分析，另外我们需要把b子树的细节进一步展开为12和左子树高度为h-1的e和f子树，因为我们要对b的父亲15为旋转点进行右单旋，右单旋需要动b树中的右子树。b子树中新增结点的位置不同，平衡因子更新的细节也不同，通过观察12的平衡因子不同，这里我们要分三个场景讨论。、

• 场景1：h >= 1时，新增结点插入在e子树，e子树高度从h-1变为h并不断更新12->15->10平衡因子，引发旋转，其中12的平衡因子为-1，旋转后10和12平衡因子为0，15平衡因子为1。

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

• 场景3：h == 0时，a/b/c都是空树，b自己就是一个新增结点，不断更新15->10平衡因子，引发旋转，其中12的平衡因子为0，旋转后10和12和15平衡因子均为0。

2.3.9 右左双旋代码实现

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);}}

2.4 AVL树的查找

那二叉搜索树逻辑实现即可（左子树<根节点<右子树），搜索效率为

Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first _right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}

2.5 AVL树平衡检测

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

注：我们这里不能简单的通过平衡因子来判断AVL是否平衡，平衡因子无误是AVL平衡的必要条件，不是充分条件，平衡因子本身可能由于bug出错。

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){// 空树也是AVL树if (nullptr == root)return true;// 计算pRoot结点的平衡因子：即pRoot左右子树的高度差int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者// pRoot平衡因子的绝对值超过1，则一定不是AVL树if (abs(diff) >= 2){cout <_kv.first << \"高度差异常\" <_bf != diff){cout <_kv.first << \"平衡因子异常\" <_left) && _IsBalanceTree(root->_right);}// 测试代码void TestAVLTree1(){AVLTree t;// 常规的测试用例//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试用例int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.Insert({ e, e });}t.InOrder();cout << t.IsBalanceTree() << endl;}// 插入一堆随机值，测试平衡，顺便测试一下高度和性能等void TestAVLTree2(){const int N = 100000;vector v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);}size_t begin2 = clock();AVLTree t;for (auto e : v){t.Insert(make_pair(e, e));}size_t end2 = clock();cout << \"Insert:\" << end2 - begin2 << endl;cout << t.IsBalanceTree() << endl;cout << \"Height:\" << t.Height() << endl;cout << \"Size:\" << t.Size() << endl;size_t begin1 = clock();// 确定在的值/*for (auto e : v){t.Find(e);}*/// 随机值for (size_t i = 0; i < N; i++){t.Find((rand() + i));}size_t end1 = clock();cout << \"Find:\" << end1 - begin1 << endl;}

2.6 AVL树的删除

AVL树的删除不做讲解，有兴趣的读者可参考：《殷人昆 数据结构：用面向对象方法与C++语言描述》中讲解。