[数据结构] AVL树 模拟实现AVL树

标题：[数据结构] AVL树 && 模拟实现AVL树

@水墨不写bug

正文开始：

目录

（一）普通二叉搜索树的痛点 

 （二）AVL树简介

（1）AVL树的概念 

（三）AVL树的实现

（1）AVL树节点的定义

（2）AVL树的插入

（3）AVL树的旋转

i，左单旋（新节点插入较高右子树的右侧---右右：左单旋）

ii，右单旋（新节点插入较高左子树的左侧---左左：右单旋）

iii，左右双旋（新节点插入较高左子树的右侧---左右：先左单旋再右单旋）

iv，右左双旋（新节点插入较高右子树的左侧---右左：先右单旋再左单旋）

（四）AVL树的验证

（五）适用场景与性能分析

（一）普通二叉搜索树的痛点 

        在学习map和set之前，我们先认识一下AVL树和红黑树，他们是平衡二叉树，不同的是控制平衡的方法不同。本文主要讲解AVL树的概念以及实现的原理，从源代码角度带你理解AVL树的控制平衡的方法。

        map/multimap/set/multiset这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的。
但是一般的二叉搜索树有一个致命的缺陷：往树中插入元素有序或者接近有序，二叉搜索树会退化为接近链表形状的单支树结构，时间复杂度会退化为O（N）。

        为了能够利用二叉树的结构优势，同时避免二叉树时间复杂度退化的缺陷，AVL树横空出世。

 （二）AVL树简介

        AVL树的概念由两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年提出，目的是为了解决在  数据有序或者接近有序的二叉搜索树  中查找元素时的  时间复杂度退化的问题。

        平衡的二叉搜索树结构查找的时间复杂度为O（logN），是一个高效的查找复杂度。但是一旦在构建二叉树时，数据有序或者接近有序，那么二叉搜索树会退化为单支树，这就相当于在链表中查找元素，复杂度为O（N），效率低下。

        两位数学家提出：当向二叉搜索树中插入新节点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
 

（1）AVL树的概念 

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

•         它的左右子树都是AVL树
•         左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1）

什么是平衡因子？ 

        平衡因子是人为引入的快速判断二叉树是不是AVL树的一个标准。

        平衡因子是一个变量，它存储在每一个二叉树节点中。

        根据习惯，平衡因子=右子树的高度-左子树的高度。

(图中为平衡因子的计算结果)

        一旦一个节点的平衡因子的绝对值超过1，这表示这个根节点的左右子树的高度差超过1，那么就需要特殊操作（旋转），使得这棵树的左右子树的高度差的不超过1。

        如果一棵树是高度平衡的，那么它就是AVL树。如果他有n个节点，那么他的高度可以保持在log(n),那么在搜索时，时间复杂度就降下来了，为O(logN)。 

（三）AVL树的实现

        AVL树的特点是仅仅使用旋转这一种特殊操作来维持搜索树的平衡，这与其他的维持搜索树平衡的方法相比，是一个特点。本文我们依靠在节点中加入parent指针来更新平衡因子，来实现AVL树，但是这并不代表实现AVL树的方法仅此一种。

（1）AVL树节点的定义

        对于节点内存储的值，可以是一个值key，也可以是一个键值对pair{key，val}，但是只存一个值key可以归为pair{key，key}，存的值与键值相等，于是，本文的AVL树采用内部存储pair{key，val}键值对。

什么是key，val？

        key是存取时判断的标准，val是key对应的值。key，val都可以是int；也可以key是int，val是string。（需要根据实际情况判断）

什么是pair？ 

        pair是一种STL中的类：

        该类将一对不同类型的值(T1和T2)耦合在一起。单个值可以通过它的公共成员first和second来访问。

AVL树节点的定义：

template<class K,class V>
struct AVLTreeNode
{AVLTreeNode(const pair<K,V>& pair_ = pair<K,V>()): _left(nullptr), _right(nullptr), _parent(nullptr)//根节点的_root是空, _pair(pair_), _bf(0){}AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K, V> _pair;int _bf;   // 节点的平衡因子
};

        唯一需要注意的是缺省参数要给  pair<K,V>()  表示一个匿名对象，这种写法的好处我们以前文章讨论过，这里不再赘述。
 

（2）AVL树的插入

        AVL树的插入过程分为两个步骤：

                （1）与普通二叉树相同的插入操作；

                （2）调整节点的平衡因子，根据平衡因子，判断是否要进行旋转操作。

         就插入操作而言，AVL树相对于普通的二叉搜索树，对二叉树的结构（或者形状）更加关切。

插入操作：（普通二叉树）

        处理特殊情况，根为空，直接插入即可。

        对于一般情况，先根据键值key找到插入节点的位置，接下来进行的就是节点间指针的连接了——为了在找到插入位置时能够找到插入位置的_parent的位置，创建一个parent指针在cur向下查找的时候记录parent，这样就可以成功得到_parent。但是，现在子节点可以找到父亲，但是父亲没有办法确定子节点是他的左孩子还是右孩子，想要成功连接，还需要确定当前节点是parent的左还是右，所以需要有一次单独的判断。

（具体实现如下：）

// 在AVL树中插入值为data的节点
bool insert(const pair<K,V>& pair)//1,插入  2,调整平衡因子
{//处理特殊情况if (_root == nullptr){_root = new Node(pair);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_pair.first > pair.first){parent = cur;cur = cur->_left;}else if (cur->_pair.first < pair.first){parent = cur;cur = cur->_right;}else//插入的节点等于data时退出{return false;}}//cur就是要插入的位置,parent记录父亲位置cur = new Node(pair);if (pair.first > parent->_pair.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;

插入操作：（AVL树）

两个步骤：

        （1）与普通二叉树相同的插入操作；（与上面完全一致）

        （2）调整节点的平衡因子，根据平衡因子，判断是否要进行旋转操作。（这是AVL树多做的部分）

---

如何调整平衡因子？

        平衡因子是每一个节点都有的，并且插入一个节点，只会对插入的子树的父祖节点的平衡因子产生影响。所以我们使用迭代法，从下向上依次更新平衡因子：

       

        每一次迭代后，cur和parent会向上移动，同时平衡因子也会更新。

更新平衡因子的方法是比较容易想的：

        只看当前新插入节点和parent节点——如果心插入节点是parent左，平衡因子_bf = 右子树高度 - 左子树高度；在左侧插入会导致平衡因子减小1；

        只看当前新插入节点和parent节点——如果心插入节点是parent右，平衡因子_bf = 右子树高度 - 左子树高度；在→侧插入会导致平衡因子增大1；

if (cur == parent->_left)parent->_bf--;
elseparent->_bf++;

(上述代码是在每次迭代后的更新平衡因子操作)

如何根据平衡因子来判断是否需要旋转？

        在更新平衡因子之后，需要根据平衡因子来判断是否需要旋转，更新平衡因子之后，父节点的平衡因子只有三种情况：

//parent的平衡因子为0    ——原来是1、-1，插入后为0，插入的是较矮的一边，高度不变化，不需要向上追踪父族
//parent平衡因子是-1、1  ——原来是0，插入后为1、-1，原来平衡，插入后不平衡，高度变化，需要向上
//parent平衡因子是2、-2  ——原来是1、-1，插入后加剧了不平衡，高度变化，需要旋转

 我们只需要将上述的三种情况转化为代码即可：

while (parent)//parent的平衡因子为0    ——原来是1、-1，插入后为0，插入的是较矮的一边，高度不变化，不需要向上追踪父族//parent平衡因子是-1、1  ——原来是0，插入后为1、-1，原来平衡，插入后不平衡，高度变化，需要向上//parent平衡因子是2、-2  ——原来是1、-1，插入后加剧了不平衡，高度变化，需要旋转
{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)//需要旋转{//....}else{assert(false);}
}

        在向上迭代的过程中，如果cur节点的parent节点的平衡因子为2或者-2，这就表明这棵树已经不平衡了，将parent和cur所在的子树单独拿出来，旋转处理。

（3）AVL树的旋转

        AVL树的旋转总结来说一共右四种情况，分别是：左单旋，右单旋，左右双旋，右左双旋。

这四种情况的区别仅仅是插入节点的位置不同。 

        以下四种情况是触发旋转后才考虑的，如果在插入后没有触发旋转，则对下面四种旋转的讨论是没有意义的 ；（画的图也是刚好可以触发旋转的抽象图，目的是便于理解和梳理思路，便于写代码）

i，左单旋（新节点插入较高右子树的右侧---右右：左单旋）

        通过观察，我们发现：

        1，旋转的过程需要将bf等于2或者-2的子树拿出来进行——新节点的插入导致15的bf==2，于是把15这课子树拿出来进行旋转处理。

        2，旋转后，整棵树变化为平衡二叉树（左子树和右子树高度之差小于2）。

        3，至于旋转的为什么这样旋，以及可行性问题等，可以参考当年提出AVL树的学术论文。

---

        这里我们先考虑具体实现：需要几个指针变量记录节点的地址，便于改变树的形状：

parent为树的根节点，subR，subRL不再赘述。

对于一种特殊情况：当高度H==0，这时subRL==nullptr，不能再对subRL解引用，所以在访问subRL的时候，需要特殊判空。

void RotateL(Node* parent)
{Node* subR = parent->_right, * subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;//....
}

        接下来，parent的父亲节点以及父亲节点和parent之间的关系没有确定，所以需要一个变量提前保存parent的父亲节点：

Node* Parentparent = parent->_parent;

        判断parent与他的父亲节点的关系：

        特殊的，如果parent的父亲是空，说明parent是整棵树的根，这种情况直接将旋转后的新根赋值给_root即可；

        一般情况，需要判断parent是他的父亲的左孩子还是右孩子：

if (Parentparent == nullptr)
{subR->_parent = nullptr;_root = subR;
}
else
{if (Parentparent->_left == parent){Parentparent->_left = subR;}else{Parentparent->_right = subR;}subR->_parent = Parentparent;
}

        最后，根据抽象图更新平衡因子即可：

			subR->_bf = parent->_bf = 0;

左单旋整体代码逻辑：

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

ii，右单旋（新节点插入较高左子树的左侧---左左：右单旋）

        右单旋与与左单旋，无论是插入位置，触发条件，还是旋转处理，都与左单旋类似（某一种对称）这里给出右单旋抽象图，不再赘述：

实现参考：

// 右单旋
void RotateR(Node* parent)
{Node* subL = parent->_left, * subLR = subL->_right;Node* Parentparent = parent->_parent;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;if (Parentparent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (Parentparent->_left == parent){Parentparent->_left = subL;}else{Parentparent->_right = subL;}subL->_parent = Parentparent;}//更新平衡因子，下方的树的平衡因子没有影响subL->_bf = parent->_bf = 0;
}

        通过总结，我们发现：插入在较高的子树的同侧（较高的左子树的左侧，较高的右子树的右侧），只需要进行一次旋转就可以树平衡化；但是对于插入位置在较高的子树的异侧时，就需要换一种处理方法——双旋。

iii，左右双旋（新节点插入较高左子树的右侧---左右：先左单旋再右单旋）

        对于这棵子树（一般来说是子树，也可能是一整颗树），90节点为根，30节点为左子树，它相对于90的右子树更高。

        插入位置在较高的左子树（30这棵子树）的右侧；这时需要先对30这棵子树左单旋，再对90这棵子树右单旋，最终90这棵子树成为平衡树。 

        

在具体实现中，我们可以复用已经实现的左单旋和右单旋的函数：

void RotateLR(Node* parent)
{Node* subL = parent->_left, * subLR = subL->_right;RotateL(subL);RotateR(parent);//.....
}

        但是需要注意，在旋转后，需要手动更新平衡因子，因为单旋中更新的平衡因子是只适合单旋的情况，对于双旋，自己设计更新平衡因子：

        通过观察抽象图，我们发现，左右双旋的插入位置无非只有两个：

这两种情况我们可以通过观察60的平衡因子来判断，于是，在旋转之前，提前保存60这个节点的平衡因子：

int bf = subLR->_bf;

        接下来，根据60节点的平衡因子的情况，更新90这棵子树中，插入位置的父祖节点的平衡因子即可。

        特殊处理：60这个节点的平衡因子可能为0，这表示60这个节点本身就是插入的新节点。依然根据抽象图分类假设，更新平衡因子即可。

左右双旋代码实现：

// 左右双旋
void RotateLR(Node* parent)
{Node* subL = parent->_left, * subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);RotateR(parent);if (bf == 0){parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else if (bf == 1){subLR->_bf = 0;parent->_bf = 0;subL->_bf = -1;}else if (bf == -1){subLR->_bf = 0;parent->_bf = 1;subL->_bf = 0;}elseassert(false);//一般逻辑不会进入，用于检验平衡因子的异常
}

iv，右左双旋（新节点插入较高右子树的左侧---右左：先右单旋再左单旋）

         基本思路与左右双旋一致，这两种满足某种对称性，这里仅仅给出抽象图和代码实现：

右左双旋参考代码：

// 右左双旋
void RotateRL(Node* parent)
{Node* subR = parent->_right, * subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);if (bf == 0){subRL->_bf = 0;subR->_bf = 0;parent->_bf = 0;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else if (bf == 1){subRL->_bf = 0;parent->_bf = -1;subR->_bf = 0;}elseassert(false);
}

（四）AVL树的验证

        到这里，AVL树的主要工作原理你已经十分清楚了，接下来可以通过一下这个程序来测试一下我们的AVL树的代码逻辑有没有问题：

bool IsAVLTree()
{return _IsBalanceTree(_root);
}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 || root->_bf != diff)return false;// pRoot的左和右如果都是AVL树，则该树一定是AVL树return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}size_t _Height(Node* root)
{if (root == nullptr)return 0;int Hl = _Height(root->_left), Hr = _Height(root->_right);return Hl > Hr ? Hl + 1 : Hr + 1;
}

 如果没有问题，那么在运行如下场景时，每一次插入后，检测都是满足AVL树的：

#include"AVLTree.h"
int main()
{ddsm::AVLTree<int,int> at;//int arr[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (const auto& e : arr){at.insert({e,e});}at.inorder();cout<<at.IsAVLTree();return 0;
}

 运行结果：

4->1
2->1
6->1
1->1
3->1
5->1
15->1
7->1
16->1
14->1

（五）适用场景与性能分析

        AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即logN。

        但是如果要对AVL树做一些结构修改的操作，性能非常低下；（比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。）

        因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合使用AVL树来做底层来实现。

回顾：

        二叉搜索树——模拟实现

完~

未经作者同意禁止转载