【C++】AVL树
一、AVL树的定义
AVL树是最先发明的⾃平衡⼆叉搜索树，AVL是⼀颗空树，或者具备下列性质的⼆叉搜索树：它的
左右子树都是AVL树，且左右子树的高度差的绝对值不超过1。AVL树是⼀颗高度平衡搜索⼆叉树，通过控制高度差去控制平衡。
思考⼀下为什么AVL树是高度平衡搜索⼆叉树，要求高度差不超过1，而不是高度差是0呢？0不是更好的平衡吗？我们先看下面的图：
画画图分析我们发现，不是不想这样设计，而是有些情况是做不到高度差是0的。比如图中的⼀棵树是2个结点，4个结点等情况下，高度差最好就是1，达不到高度差为0。
AVL树得名于它的发明者G.M.Adelson-Velsky和E.M.Landis，他们是两个前苏联的科学家，他们在1962年的论文《An algorithm for the organization of information》中发表了它。
AVL树整体结点数量和分布和完全⼆叉树类似，高度可以控制在 ，那么增删查改的效率也可
以控制在 ，相比⼆叉搜索树有了本质的提升。
二、AVL树的实现
1、平衡因子
关于AVL树的实现，这里我们引入一个平衡因子(balance factor)的概念，每个结点都有⼀个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1，AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡，就像⼀个风向标⼀样。
注：平衡因子不是实现AVL树的必备条件，有些地方没有使用平衡因子也能实现AVL树。
下图是含有平衡因子的AVL树：
对于8这个结点来说，它的左子树高度为3，右子树高度为2，那么它的平衡因子就是-1(右子树的高度减左子树的高度)；对于1这个结点来说，它的左子树高度为0，右子树的高度也为0，所以它的平衡因子就是0。如果每个结点的平衡因子大于1或者小于-1，那么这棵树就不是AVL树了，它的平衡性遭到了破坏。 (AVL树相较于二叉搜索树最主要的特点就是平衡，若失去平衡增删查改的时间复杂度就无从谈起)
因为AVL是搜索二叉树，它的插入遵循搜索二叉树的规则，若插入13，如下图所示：
此时，10这个结点的平衡因子更新为2，那么就认为这个树不平衡它就不是AVL树了。针对插入前是AVL树，而插入后不是AVL树的情况，我们会对这棵树进行旋转使它继续保持平衡，旋转的概念下面会详细解释。
2、实现框架
template <class K,class V>
struct AVLTreeNode
{
pair<K, V> _kv; //结点的每个元素类型是pair，搜索场景是key/value
int _bf; //记录平衡因子，balance factor
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent; //需要父结点的指针，方便更新平衡因子
//结点的构造函数
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0) //新结点的平衡因子都是0(因为它的左右子树均为空树，高度都是0，相减也为0)
{}
};
template <class K,class V>
class AVLTree
{
typedef AVLNode<K, V> Node;
public:
//... 实现的主要功能写在这个部分
private:
Node* _root = nullptr; //只需记录树的根节点
};3、插入函数(insert)
AVL树的插入规则和二叉搜索树一模一样，只不过它要单独更新结点中的parent指针，以及平衡因子。AVL树插入的大致过程如下：
- 按⼆叉搜索树规则插入一个值。
- 新增结点以后，只会影响祖先结点的高度，也就是可能会影响部分祖先结点的平衡因子，所以更新从新增结点->根结点路径上结点的平衡因子，实际中最坏情况下要更新到根，有些情况更新到中间就可以停止了，具体情况我们下面再详细分析。
- 更新平衡因子过程中没有出现问题，则插入结束。
- 更新平衡因子过程中出现不平衡，需要对不平衡子树旋转，旋转后调整平衡的同时，本质降低了子树的高度，这个更新过程不会影响上⼀层，所以插入结束。
平衡因子的更新：
更新原则：
- 平衡因子 = 右子树高度 - 左子树高度(也可以是左子树高度 - 右子树高度，那么逻辑就需要改变)
- 只有子树高度变化才会影响当前结点平衡因子
- 插入结点，会增加高度，所以新增结点在parent的右子树，parent的平衡因子++，新增结点在
parent的左子树，parent平衡因子--(右-左) - parent所在子树的高度是否变化决定了是否会继续往上更新
更新停止条件(分为3种情况)：
- 更新后parent的平衡因子等于0，更新中parent的平衡因子变化为-1->0或者1->0，说明更新前parent子树⼀边高⼀边低，新增的结点插入在低的那边，插入后parent所在的子树高度不变，不会影响parent的父结点的平衡因子，更新结束。
- 更新后parent的平衡因子等于1或-1，更新中parent的平衡因子变化为0->1或者0->-1(不可能是2->1或者-2->-1，因为插入前这棵树必须是AVL树)，说明更新前parent子树两边⼀样高，新增的插入结点后，parent所在的子树⼀边高⼀边低，parent所在的子树符合平衡要求，但是高度增加了1，这会影响parent的父结点的平衡因子，所以要继续向上更新平衡因子，最坏情况下更新到根结点，更新结束。
- 更新后parent的平衡因子等于2或-2，更新中parent的平衡因子变化为1->2或者-1->-2，说
明更新前parent子树⼀边高⼀边低，新增的插入结点在高的那边，parent所在的子树高的那边更高了，破坏了平衡，parent所在的子树不符合平衡要求，需要旋转处理，旋转的目标有两个：1、把parent子树旋转平衡。2、降低parent子树的高度，恢复到插⼊结点以前的高度。所以旋转后也不需要继续往上更新(插入前后高度不变：插入前高度是h，插入后，经过旋转，高度还是h)，更新结束。
以上3种情况都是针对插入前是AVL树，插入后也是AVL树的情景，第三种情况插入后不是AVL树，那我们就需要单独处理，进行旋转。
图例说明：
插入结点13，结点14的平衡因子由0变为-1，需要向上更新，更新到10结点，它的平衡因子由1变为2，此时破坏了平衡，10所在的子树已经不平衡，需要旋转处理。
插入结点-1，结点1的平衡因子由0变为-1，需要向上更新，更新到中间结点3，它的平衡因子由1变为0，但以3为根的子树高度不变，不会影响上⼀层，更新结束。
插入结点7，结点6的平衡因子由0变为1，需要向上更新，更新到8这个根结点，这是最坏情况。
在左子树中插入结点，右子树所有结点的平衡因子都不需要改变；在右子树中插入结点，左子树所有结点的平衡因子都不需要改变。
了解完上面的知识，那么代码就很好理解了：
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv); //根结点的_parent指针为nullptr
return true;
}
Node* parent = nullptr; //注意这里的parent是结点的父结点，不是结点中指向父结点的指针
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) //比较的是key值，value值不参与比较
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
//链接父亲
cur->_parent = parent;
//插入结点结束后还要控制平衡
//更新平衡因子，沿着cur和parent向上更新
while (parent) //保证parent不为空，如果parent为空就更新结束了，此时cur就是根结点
{
if (cur == parent->_left) //parent的平衡因子需要--
parent->_bf--;
else//parent的平衡因子需要++
parent->_bf++;
//对应更新停止的第一种情况
if (parent->_bf == 0)
{
break;
}
//对应更新停止的第二种情况
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = parent->_parent;
}
//对应更新停止的第三种情况，这里写else if而不写else是为了防止插入前不是AVL树的情况
else if (parent->_bf == 2 || parent->_bf == -2)
{
//这里就需要写旋转的逻辑，旋转的部分我们单独讲解
//...
break;
}
else
{
assert(false);//如果插入前不是AVL树，就中断程序，说明平衡因子出现问题了，这时候就需要检查我们写的代码
}
}
return true; //控制平衡后，就插入成功了，放回true
}4、旋转
若某个结点的平衡因子达到-2或2，那么以此结点为根节点的子树就需要进行旋转使其高度差减小。
旋转的原则：
- 保持搜索树的规则不能被改变
- 让旋转的树由不满足平衡变为满足平衡，其次降低旋转树的高度
旋转总共分为四种：左单旋/右单旋/左右双旋/右左双旋。
(1)右单旋
先来看一张图：
本图展示的是以10为根的AVL树，有a/b/c三棵抽象的高度为h的子树(h>=0)，a/b/c均符合AVL树的要求。10可能是整棵树的根，也可能是⼀个整棵树中局部的子树的根。
在a子树中插入一个新结点，导致a子树的高度从h变成h+1，不断向上更新平衡因子，导致10的平
衡因子从-1变成-2，10为根的树左右高度差超过1，违反平衡规则。10为根的树左边太高了，需要
往右边旋转，即右单旋，来控制两棵树的平衡。
旋转核心步骤：因为5<b子树的值<10，将b变成10的左子树，10变成5的右子树，5变成这棵树新的根，这样就符合搜索树的规则，控制了平衡(结合上图理解)，同时这棵的高度恢复到了插入之前的h+2，符合旋转原则。如果插入之前，以10为根节点的树是整棵树的⼀个局部子树，旋转后不会再影响上⼀层(旋转后插入前后树的高度不变)，插入结束。
要想在10结点处发生右单旋，前提是插入前a和b的高度一致，且是在a树进行插入。
旋转过后，只有5和10结点的平衡因子改变，其余结点都不变。
旋转后必须要达到：1、保持搜索树规则 2、变平衡 3、降低树的高度，三者缺一不可。
如果将a、b、c具象化，可以分为下面几种情况(帮助大家理解抽象情况)：
情况1：a、b、c都是空树
情况2：a、b、c都只有一个结点
新增的结点也可以插在1的右边(比如新增一个结点2)，保证插入新结点后，从a开始平衡因子会更新到结点10，且在结点10的位置处引发旋转。
情况3：a、b、c均为高度为2的AVL树
a的场景只能是x，因为只有是x才能保证插入新结点后，从a开始平衡因子会更新到结点10，且在结点10的位置处引发旋转，在a中插入新结点的位置有4个。
情况4：a、b、c均为高度为3的AVL树
以上4中场景是帮助我们理解抽象图的，如果要考虑a、b、c的各个场景，那是不现实的，a、b、c高度可能是1、2、3...，如果只针对一种情况讲解那是不好的，不具有通性，所以我们要研究抽象图。
右单旋代码实现：
//右单旋(左子树高度高于右子树),结合抽象图分析代码逻辑
void RotateR(Node* parent) //parent就是旋转点
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* pParent = parent->_parent; //记录parent->_parent修改前的内容
parent->_left = subLR; //核心代码
subL->_right = parent; //核心代码
if(subLR) //subLR可能为空，需要判断
subLR->_parent = parent; //需要修改subLR的父结点指针
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;
}
//至此，旋转逻辑完毕，接下来需要更新平衡因子
subL->_bf = 0;
parent->_bf = 0;
}那么，在插入过程中，遇到旋转的情况就需要进行判断了：
if (parent->_bf == -2 && cur->_bf == -1) //parent和cur都满足左边高右边低，右单旋
{
RotateR(parent);
}(2)左单旋
左单旋的逻辑和右单旋一样，只是变为右边高度高于左边高度。
本图展示的是以10为根的AVL树，有a/b/c三棵抽象的高度为h的子树(h>=0)，a/b/c均符合AVL树的要求。10可能是整棵树的根，也可能是⼀个整棵树中局部的子树的根。
在a子树中插入一个新结点，导致a子树的高度从h变成h+1，不断向上更新平衡因子，导致10的平衡因子从1变成2，10为根的树左右高度差超过1，违反平衡规则。10为根的树右边太高了，需要往
左边旋转，即左单旋，来控制两棵树的平衡。
旋转核心步骤：因为10<b子树的值<15，将b变成10的右子树，10变成15的左子树，15变成这棵
树新的根，符合搜索树的规则，控制了平衡(结合上图理解)，同时这棵的高度恢复到了插入之前的h+2，符合旋转原则。如果插入之前，以10为根节点的树是整棵树的⼀个局部子树，旋转后不会再影响上⼀层(旋转后，插入前后树的高度不变)，插入结束。
要想在10结点处发生左单旋，前提是插入前a和b的高度一致，且是在a树进行插入。
旋转过后，只有10和15结点的平衡因子改变，其余结点都不变。
左单旋代码实现：
//左单旋(右子树高度高于左子树),结合抽象图分析代码逻辑
void RotateL(Node* parent) //parent就是旋转点
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* pParent = parent->_parent; //记录parent->_parent修改前的内容
parent->_right = subRL; //核心代码
subR->_left = parent; //核心代码
if (subRL) //subRL可能为空，需要判断
subRL->_parent = parent; //需要修改subRL的父结点指针
parent->_parent = subR;
//旋转点可能是整棵树的根结点，那么需要更新根
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
//旋转点也可能是局部子树的根结点，那么需要进行链接操作
else
{
if (pParent->_left == parent)
pParent->_left = subR;
else
pParent->_right = subR;
subR->_parent = pParent;
}
//至此，旋转逻辑完毕，接下来需要更新平衡因子
subR->_bf = 0;
parent->_bf = 0;
}那么，在插入过程中，遇到旋转的情况就需要进行判断了：
else if (parent->_bf == 2 && cur->_bf == 1)//parent和cur都满足右边高左边低，左单旋
{
RotateL(parent);
}(3)左右双旋
单旋场景是纯粹的一边高，双旋不是。
结合上面的图来看，右单旋中在a位置插入一个结点后，对于以5为结点的树，它的左边比右边高，对于以10为结点的树，也是左边比右边高，它是存粹的一边高。
左单旋中，在a位置插入一个结点后，对于以15为结点的树，它的右边比左边高，对于以10为结点的树，也是右边比左边高，它也是存粹的一边高。
单旋适用于存粹一边高的情况，如果不是存粹一边高，那就不能用单旋，比如：
在b位置上插入8后，对于5这个结点来说，它是右边高左边低；但对于10这个结点来说，它是左边高右边低。那这时如果进行右单旋，那就从左边高变为右边高了。所以这种不存粹的场景，不能用单旋来解决平衡和高度问题。我们再看一个场景：
在b位置上插入9后，对于5这个结点来说，它是右边高左边低；但对于10这个结点来说，它是左边高右边低。那这时如果进行右单旋，还是和上面一样，解决不了问题。
要想解决这种问题，就需要使用双旋，双旋的本质是将不存粹变为存粹。
对于第一种场景，双旋的过程是：
这种情况(a、b、c的高度都为0)，双旋后，5和10的平衡因子都是0。
对于第二种场景，也是如此，先对5结点进行左单旋，再对10结点进行右单旋。
对于第二种场景，这里不仅插入到8的右边会引发双旋，而且如果插入到8的左边照样也会引发双旋(这就导致了8这个结点的平衡因子会不同，进而导致在双旋后平衡因子更新会变得更加复杂)。
这两种情况的共同点是(只看首个形态和最终形态)：8结点的左子树给5结点的右子树，8结点的右子树给10结点的左子树，导致这两种情况不同的原因是8的左右子树不固定(既可以在8的右边插入9，又可以在8的左边插入6)。我们如果想要区分到底在8的左边插入还是右边插入，只需看8的平衡因子，如果8的平衡因子是1，就是右边插入，如果平衡因子是-1就是左边插入。
我们将这种先进行左旋，再进行右旋操作的过程称为左右双旋。
上边介绍的两种场景是左右双旋中h==0和h==1(h是指a、b、c的高度)具体场景分析，下面我们将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这3个结点的平衡因子，从而引发旋转，其中这种场景下8的平衡因子为-1，旋转后8和5平衡因子为0，10的平衡因子为1。
场景2：h>=1时，新增结点插入在f子树，f子树高度从h-1变为h并不断更新8->5->10这3个结点的平衡因子，从而引发旋转，其中这种场景下8的平衡因子为1，旋转后8和10平衡因子为0，5平衡因子为-1。
场景3：h==0时，a/b/c都是空树，b自己就是⼀个新增结点，不断更新5->10平衡因子，从而引发旋转，其中这种场景下8的平衡因子为0，旋转后8和10和5平衡因子均为0。
下图能直观地感受：
想要区分是哪种场景，就需要看插入新结点后，8的平衡因子是多少。
左右双旋代码实现：
//左右双旋,结合图例分析代码逻辑
void RotateLR(Node* parent)
{
//因为单旋会调整平衡因子，所以需要提前记录，防止丢失
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left); //复用左单旋
RotateR(parent); //复用右单旋
//场景1
if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
//场景2
else if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
//场景3
else if (bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);//中断程序，说明平衡因子出现问题了，这时候就需要检查我们写的代码
}
}那么，在插入过程中，遇到旋转的情况就需要进行判断了：
else if (parent->_bf == -2 && cur->_bf == 1) //左右双旋
{
RotateLR(parent);
}(4)右左双旋
跟左右双旋类似，下面我们将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这3个结点地平衡因子，从而引发旋转，其中12的平衡因子为1，旋转后15和12平衡因子为0，10平衡因子为-1。
场景3：h==0时，a/b/c都是空树，b自己就是⼀个新增结点，不断更新15->10平衡因子，引发旋
转，其中12的平衡因子为0，旋转后10和12和15平衡因子均为0。
下图能直观地感受：
想要区分是哪种场景，就需要看插入新结点后，12的平衡因子是多少。
右左双旋代码实现：
//右左双旋,结合图例分析代码逻辑
void RotateRL(Node* parent)
{
//因为单旋会调整平衡因子，所以需要提前记录，防止丢失
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
//场景1
if (bf == -1)
{
subR->_bf = 1;
subRL->_bf = 0;
parent->_bf = 0;
}
//场景2
else if (bf == 1)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = -1;
}
//场景3
else if (bf == 0)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);//中断程序，说明平衡因子出现问题了，这时候就需要检查我们写的代码
}
}那么，在插入过程中，遇到旋转的情况就需要进行判断了：
else if (parent->_bf == 2 && cur->_bf == -1) //右左双旋
{
RotateRL(parent);
}5、中序遍历
AVL树的中序遍历和二叉搜索树的实现逻辑一致。
代码实现：
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}6、高度和个数
因为它的底层是树，那我们就可以用递归来求树的高度和元素个数。
int Height()
{
return _Height(_root);
}
int Size()
{
return _Size(_root);
}
private:
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;
}
int _Size(Node* root)
{
if (root == nullptr)
return 0;
return _Size(root->_left) + _Size(root->_right) + 1;
}7、判断一棵树是否为AVL树
思路：算一个树左右子树的高度，然后求差值，若插值的绝对值大于等于2，那就不是AVL树，同时可以判断当前树的根节点的平衡因子是否正确，若不正确，也不是AVL树。
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 << root->_kv.first << "高度差异常" << endl;
return false;
}
if (root->_bf != diff)
{
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
// pRoot的左和右如果都是AVL树，则该树一定是AVL树
return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}8、查找
AVL树的查找逻辑和二叉搜索树一致。
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;
}9、删除
删除的逻辑这里就不详细介绍了，它的大致过程就是：首先找到要删除的结点，进行删除(删除时也分在什么位置，只有左子树，或者只有右子树，或者左右子树都有，或者左右子树都没有)，然后更新平衡因子，最后还需考虑旋转。
三、测试
AVL树的功能基本上已经结束了，接下来我们对所写的功能测试一下，看有没有问题：
void TestAVLTree1()
{
AVLTree<int, int> 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;
}
int main()
{
TestAVLTree1();
return 0;
}运行结果：
从结果上看没有问题。
我们再来写一个测试用例：
void TestAVLTree2()
{
const int N = 1000000;
vector<int> v;
v.reserve(N);
srand((unsigned int)time(0));
for (size_t i = 0; i < N; i++)
v.push_back(rand() + i); //插入100w个数
size_t begin1 = clock();
AVLTree<int, int> t;
for (auto e : v)
{
t.Insert(make_pair(e, e));
}
size_t end1 = clock();
cout << "Insert:" << end1 - begin1 << endl; //插入100w个数，看看花费了多少毫秒
cout << t.IsBalanceTree() << endl;
}
int main()
{
TestAVLTree2();
return 0;
}运行结果：
在debug环境下，插入100w个数花费757毫秒，速度还是非常快的。
它的速度之所以这么快，取决于它插入的过程，时间复杂度为：O(logN)。
因为它插入的时候，最多找高度次，高度是logN，所以插入需要找logN次，而平衡因子最多向上更新高度次，也是logN次，旋转的次数几乎可以忽略不记，所以2倍logN下的时间复杂度为:O(logN)
再来最后一个测试用例：
void TestAVLTree3()
{
const int N = 1000000;
vector<int> v;
v.reserve(N);
srand((unsigned int)time(0));
for (size_t i = 0; i < N; i++)
{
v.push_back(rand() + i);
}
AVLTree<int, int> t;
for (auto e : v)
{
t.Insert(make_pair(e, e));
}
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;
}
int main()
{
TestAVLTree3();
return 0;
}这段代码的功能就是插入100w个数，看看AVL数的高度是多少以及实际插入多少个有效的数据，还有看看Find的查找效率怎么样。
运行结果：
在debug环境下总共花费了411毫秒，查找效率也是挺快的，因为AVL树的高度为logN，它查找的次数最多为logN，所以查找的时间复杂度是：O(logN)
四、源码
1、AVLTree.h
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;
template <class K,class V>
struct AVLTreeNode
{
pair<K, V> _kv; //结点的每个元素类型是pair，搜索场景是key/value
int _bf; //记录平衡因子，balance factor
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent; //需要父结点的指针，方便更新平衡因子
//结点的构造函数
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0) //新结点的平衡因子都是0(因为它的左右子树均为空树，高度都是0，相减也为0)
{}
};
template <class K,class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
//右单旋(左子树高度高于右子树),结合抽象图分析代码逻辑
void RotateR(Node* parent) //parent就是旋转点
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* pParent = parent->_parent; //记录parent->_parent修改前的内容
parent->_left = subLR; //核心代码
subL->_right = parent; //核心代码
if(subLR) //subLR可能为空，需要判断
subLR->_parent = parent; //需要修改subLR的父结点指针
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;
}
//至此，旋转逻辑完毕，接下来需要更新平衡因子
subL->_bf = 0;
parent->_bf = 0;
}
//左单旋(右子树高度高于左子树),结合抽象图分析代码逻辑
void RotateL(Node* parent) //parent就是旋转点
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* pParent = parent->_parent; //记录parent->_parent修改前的内容
parent->_right = subRL; //核心代码
subR->_left = parent; //核心代码
if (subRL) //subRL可能为空，需要判断
subRL->_parent = parent; //需要修改subRL的父结点指针
parent->_parent = subR;
//旋转点可能是整棵树的根结点，那么需要更新根
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
//旋转点也可能是局部子树的根结点，那么需要进行链接操作
else
{
if (pParent->_left == parent)
pParent->_left = subR;
else
pParent->_right = subR;
subR->_parent = pParent;
}
//至此，旋转逻辑完毕，接下来需要更新平衡因子
subR->_bf = 0;
parent->_bf = 0;
}
//左右双旋,结合图例分析代码逻辑
void RotateLR(Node* parent)
{
//因为单旋会调整平衡因子，所以需要提前记录，防止丢失
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left); //复用左单旋
RotateR(parent); //复用右单旋
//场景1
if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
//场景2
else if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
//场景3
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);
//场景1
if (bf == -1)
{
subR->_bf = 1;
subRL->_bf = 0;
parent->_bf = 0;
}
//场景2
else if (bf == 1)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = -1;
}
//场景3
else if (bf == 0)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);//中断程序，说明平衡因子出现问题了，这时候就需要检查我们写的代码
}
}
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv); //根结点的_parent指针为nullptr
return true;
}
Node* parent = nullptr; //注意这里的parent是结点的父结点，不是结点中指向父结点的指针
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) //比较的是key值，value值不参与比较
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
//链接父亲
cur->_parent = parent;
//插入结点结束后还要控制平衡
//更新平衡因子，沿着cur和parent向上更新
while (parent) //保证parent不为空，如果parent为空就更新结束了，此时cur就是根结点
{
if (cur == parent->_left) //parent的平衡因子需要--
parent->_bf--;
else//parent的平衡因子需要++
parent->_bf++;
//对应更新停止的第一种情况
if (parent->_bf == 0)
{
break;
}
//对应更新停止的第二种情况
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = parent->_parent;
}
//对应更新停止的第三种情况，这里写else if而不写else是为了防止插入前不是AVL树的情况
else if (parent->_bf == 2 || parent->_bf == -2)
{
//这里就需要写旋转的逻辑，旋转的部分我们单独讲解
//...
if (parent->_bf == -2 && cur->_bf == -1) //parent和cur都满足左边高右边低，右单旋
{
RotateR(parent);
}
else if (parent->_bf == 2 && cur->_bf == 1)//parent和cur都满足右边高左边低，左单旋
{
RotateL(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1) //左右双旋
{
RotateLR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1) //右左双旋
{
RotateRL(parent);
}
else
{
assert(false);
}
break;
}
else
{
assert(false);//如果插入前不是AVL树，就中断程序，说明平衡因子出现问题了，这时候就需要检查我们写的代码
}
}
return true; //控制平衡后，就插入成功了，放回true
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
int Height()
{
return _Height(_root);
}
int Size()
{
return _Size(_root);
}
bool IsBalanceTree()
{
return _IsBalanceTree(_root);
}
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;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
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;
}
int _Size(Node* root)
{
if (root == nullptr)
return 0;
return _Size(root->_left) + _Size(root->_right) + 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 << root->_kv.first << "高度差异常" << endl;
return false;
}
if (root->_bf != diff)
{
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
// pRoot的左和右如果都是AVL树，则该树一定是AVL树
return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}
private:
Node* _root = nullptr; //只需记录树的根节点
};
2、Test.cpp
#include <vector>
#include "AVLTree.h"
void TestAVLTree1()
{
AVLTree<int, int> 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 = 1000000;
vector<int> v;
v.reserve(N);
srand((unsigned int)time(0));
for (size_t i = 0; i < N; i++)
v.push_back(rand() + i); //插入100w个数
size_t begin1 = clock();
AVLTree<int, int> t;
for (auto e : v)
{
t.Insert(make_pair(e, e));
}
size_t end1 = clock();
cout << "Insert:" << end1 - begin1 << endl; //插入100w个数，看看花费了多少毫秒
cout << t.IsBalanceTree() << endl;
}
void TestAVLTree3()
{
const int N = 1000000;
vector<int> v;
v.reserve(N);
srand((unsigned int)time(0));
for (size_t i = 0; i < N; i++)
{
v.push_back(rand() + i);
}
AVLTree<int, int> t;
for (auto e : v)
{
t.Insert(make_pair(e, e));
}
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;
}
int main()
{
//TestAVLTree1();
//TestAVLTree2();
TestAVLTree3();
return 0;
}五、结语
本篇内容到这里就结束了，主要讲了AVL树的定义与主要接口实现，希望对大家有帮助，祝生活愉快，我们下一篇再见！
原文地址：https://blog.csdn.net/weixin_74012727/article/details/142699182
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！