最新宝安区疫情公布_湖南网站建设策划_搜索app下载_郑州见效果付费优化公司

一、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/valueint _bf; //记录平衡因子，balance factorAVLTreeNode<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树插入的大致过程如下：

1. 按⼆叉搜索树规则插入一个值。
2. 新增结点以后，只会影响祖先结点的高度，也就是可能会影响部分祖先结点的平衡因子，所以更新从新增结点->根结点路径上结点的平衡因子，实际中最坏情况下要更新到根，有些情况更新到中间就可以停止了，具体情况我们下面再详细分析。
3. 更新平衡因子过程中没有出现问题，则插入结束。
4. 更新平衡因子过程中出现不平衡，需要对不平衡子树旋转，旋转后调整平衡的同时，本质降低了子树的高度，这个更新过程不会影响上⼀层，所以插入结束。

平衡因子的更新：

更新原则：

• 平衡因子 = 右子树高度 - 左子树高度(也可以是左子树高度 - 右子树高度，那么逻辑就需要改变)
• 只有子树高度变化才会影响当前结点平衡因子
• 插入结点，会增加高度，所以新增结点在parent的右子树，parent的平衡因子++，新增结点在
  parent的左子树，parent平衡因子--(右-左)
• parent所在子树的高度是否变化决定了是否会继续往上更新

更新停止条件(分为3种情况)：

1. 更新后parent的平衡因子等于0，更新中parent的平衡因子变化为-1->0或者1->0，说明更新前parent子树⼀边高⼀边低，新增的结点插入在低的那边，插入后parent所在的子树高度不变，不会影响parent的父结点的平衡因子，更新结束。
2. 更新后parent的平衡因子等于1或-1，更新中parent的平衡因子变化为0->1或者0->-1(不可能是2->1或者-2->-1，因为插入前这棵树必须是AVL树)，说明更新前parent子树两边⼀样高，新增的插入结点后，parent所在的子树⼀边高⼀边低，parent所在的子树符合平衡要求，但是高度增加了1，这会影响parent的父结点的平衡因子，所以要继续向上更新平衡因子，最坏情况下更新到根结点，更新结束。
3. 更新后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指针为nullptrreturn 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. 保持搜索树的规则不能被改变
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;elsepParent->_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;elsepParent->_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); //复用右单旋//场景1if (bf == -1){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}//场景2else if (bf == 1){subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}//场景3else 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);//场景1if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}//场景2else if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}//场景3else 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/valueint _bf; //记录平衡因子，balance factorAVLTreeNode<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;elsepParent->_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;elsepParent->_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); //复用右单旋//场景1if (bf == -1){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}//场景2else if (bf == 1){subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}//场景3else 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);//场景1if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}//场景2else if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}//场景3else 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指针为nullptrreturn 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树的定义与主要接口实现，希望对大家有帮助，祝生活愉快，我们下一篇再见！