C++的AVL树

目录

基本概念

插入的语言分析 

LL右旋 

RR左旋 

额外结论及问题1

LR左右旋

RL右左旋

额外结论及问题2

插入结点

更新bf与判断旋转方式

旋转代码实现

准备工作一

LL右旋的实现

RR左旋的实现

准备工作二

LR左右旋的实现

RL右左旋的实现

完整代码

基本概念

1、二叉搜索树虽然可以缩短查找效率，但如果数据有序或接近有序时二叉搜索树将退化为单支树，此时查找元素相当于在顺序表中搜索元素效率低下，因此两位俄罗斯数学家G.M.Adelson-Velskii和E.M.Landis发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能够保证每个结点的左右子树高度之差的绝对值不超过1（需要对树中的结点进行调整）即可降低树的高度，从而减少搜索长度和避免单支二叉搜索树的出现

2、AVL是满足以下性质的二叉搜索树：

  • 左右子树都是AVL树
  • 根节点的平衡因子的绝对值不超过1

3、一个有n个结点的AVL树，其高度为log_2 n，搜索时的时间复杂度为O（log_2 n）

4、AVL树的结点应该是这样的（采用三叉链结构）：

template<class K, class V>
struct  AVLTreeNode
{//三叉链结构便于向上寻找自己的父亲、爷爷等长辈结点并修改它们的平衡因子AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K, V> _kv;int _bf; //平衡因子AVLTreeNode(const pair<K,V>& kv)//默认构造:_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};

5、二叉搜索树变为AVL树需要经历以下两步：

  • 按照二叉搜索树的方式插入新节点
  • 通过旋转的方式调整结点的平衡因子

6、平衡因子 = 左子树深度 - 右子树深度（右减左的算法也行，只要最后的绝对值不超过1）

7、当二叉搜索树新插入的一个结点导致它的某个祖先结点的bf变为2或-2时，就需要以该祖先结点为基础进行旋转：

  • 平衡因子变为2是因为原本祖先结点的左子树就比右子树更深一层，新插入的结点会在该基础上继续向祖先结点的左结点（L）的左或右子树（L  / R）中进行插入且成功让该子树高度+1（说成功+1是因为也有可能只是补了一个空位）
  • 平衡因子变为-2是因为原本祖先结点的右子树就比左子树更深一层，新插入的结点会在该基础上继续向祖先结点的右结点（R）的左或右子树（L  / R）中进行插入且成功让该子树高度+1（说成功+1是因为也有可能只是补了一个空位）

插入的语言分析 

下面例子中在说向a、b和c等AVL子树中插入时需要注意以下三点内容：

  1. 不关心具体插的是AVL子树的哪个位置
  2. 每次插入时肯定使得某个AVL子树多了一层（如果不是这样就不会进入旋转函数）
  3. 是向哪个AVL子树中插入

进行旋转时需要考虑两点内容：

  1. 旋转后的树是否是AVL树
  2. 旋转后的树是否符合二叉搜索树的基本性质左< 根 < 右

更细致的bf变化图懒得画了，注意绿色字体即可，有规律

真正得出该规律需要举太多例子或者需要用数学方法去计算验证，很麻烦

所以我在这里直接举一个例子，就指明该规律了

LL右旋 

1、现在我们假设这里有一个左子树深度大于右子树的AVL树：

①向a插入，并成功使该AVL子树的高度变为h+1时，30的bf变为1，60的bf变为2

旋转方式：将b作为60结点的左孩子，将60结点作为30结点的右孩子，此时30结点的左子树高度为h+1（向a中插入了一个结点导致该AVL子树的高度+1）等于右子树的h+1（新增的一个60结点+h）我们称这种旋转方式为右旋

插入后bf的前后变化：30结点的bf：1 -> 0、60结点的bf：2->0

结论：在AVL树的某个结点的左结点（L）的左子树（L）上进行插入需要进行右旋 

RR左旋 

2、现在我们假设这里有一个右子树深度大于左子树的AVL树：

①向c插入，并成功使该AVL子树的高度变为h+1时，70的bf变为-1，60的bf变为-2

旋转方式：将b作为60结点的右孩子，将60结点作为70结点的左孩子，此时70结点的右子树高度为h+1（向c中插入了一个结点导致该AVL子树的高度+1）等于左子树的h+1（新增的一个60结点+h）我们称这种旋转方式为左旋

插入后bf的前后变化：70结点的bf：-1 -> 0、60结点的bf：-2->0

结论：在AVL树的某个结点的右结点（R）的右子树（R）上进行插入需要进行左旋

额外结论及问题1

额外结论1：因为LL和RR导致的左或右旋，旋转后除了原本bf==2或-2的结点的bf会变为0，该结点的左或右结点的bf也会变为0（发生左旋就是左节点的bf变为0，发生右旋就是右节点的bf变为0），即使h == 0，说它们在旋转后都变为0是为了后续的写代码做准备

问题1：为什么不提新插入结点的bf由什么变为什么？

解释：因为插入时该结点的bf肯定为0，但是该结点的插入可能会使它的祖先结点的bf产生变化，当某个祖先结点的bf变为2时就需要以该祖先结点为基础进行旋转，通过上述案例我们可以得知不论是RR左旋还是LL右旋，完成插入后和完成旋转后两个状态时，新插入结点的bf第一为0，所以在完成旋转后不需要对该值进行更新从宏观上来看它一直没变

LR左右旋

3、现在我们假设这里有一个左子树深度大于右子树的AVL树（将b分为d、e和40是因为如果向某个结点的左结点的右子树中插入，如果b还是一个整体那么无法进行分析并旋转不信你按照单纯的左或者右旋试一试这都是别人研究后的结果，而且这里的分开也只是将b中的第一个具体结点透露出来，之前操作b时也是操作该结点的，懒得想那么多就直接往下看就行）：

​​​​​​①向d插入，成功使该AVL子树的高度变为h时，40的bf变为1，30的bf变为-1，60的bf变为2

旋转方式：先将30作为旋转点，对其进行左旋（d成为30的右孩子，30成为40的左孩子，40成为60的左孩子）后将60作为旋转点，对其进行右旋（c成为60的左孩子，60成为40的右孩子）此时40的bf变为，我们称这种旋转方式为左右旋

插入后bf的前后变化：40结点的bf：1 -> 0、30结点的bf：-1 -> 0、60结点的bf：2 -> -1

②向e插入，成功使该AVL子树的高度变为h时，40的bf变为-1，30的bf变为-1，60的bf变为2

旋转方式：同上（区别在于30结点得到的右孩子d的高度仍为h-1，60结点得到的左孩子e的高度增加了1，这也是为什么会产生30和60结点的bf因为插入d还是e不同而不同的根本原因，如果嫌麻烦可以不看一句直接看下面的结论）

插入后bf的前后变化：40结点的bf：-1 -> 0、30结点的bf：-1 -> 1、60结点的bf：2 -> 0

结论：

1、在AVL树的某个结点的左结点（L）的右子树（R）上进行插入需要进行左右旋

2、如果40结点的bf在插入新结点后变为1，那么最后三个结点的bf分别是0（祖先结点）、-1（祖先结点的左结点）、0（祖先结点的左结点的右结点）

3、如果40结点的bf在插入新结点后变为-1，那么最后三个结点的bf分别是0（祖先结点）、1（祖先结点的左结点）、0（祖先结点的左结点的右结点）

4、产生上述差异的本质原因是：40的左孩子必然为30右孩子，右孩子必然为60的左孩子，左右孩子会因为插入的对象不同产生差异，进而导致接收它们的父结点的bf发生变化

RL右左旋

4、现在我们假设这里有一个右子树深度大于左子树的AVL树：

其余的懒得画了，直接上结论：

1、在AVL树的某个结点的右结点（R）的右子树（R）上进行插入需要进行右左旋

2、如果40结点的bf在插入新结点后变为1，那么最后三个结点的bf分别是0（祖先结点）、-1（祖先结点的右结点）、0（祖先结点的右结点的左结点）

3、如果40结点的bf在插入新结点后变为-1，那么最后三个结点的bf分别是1（祖先结点）、0（祖先结点的右结点）、0（祖先结点的右结点的左结点）

额外结论及问题2

额外结论2：

1、若h == 0，则会出现下图中的两种初始情况，即如果40结点的bf为0时（40结点本身就是新插入的结点），旋转后它的祖先结点和祖先结点的左或右结点的bf也会变为0，需要注意的是在中途旋转时父亲和爷爷结点的bf并不一定满足之前单纯LL右旋和RR左旋时所说都变为0的规律RR左旋后（因为我测试过不满足的情况，满足的情况可能有但我没试）

问题2：为什么只考虑三代结点？

解释：因为fd==2或-2的情况只会出现在三代内（其它情况的图就不画了），并且一个AVL树中只会存在一个由于新插入结点导致的非AVL子树，并且会在下次插入前理解将该AVL子树恢复正常，所以当该AVL子树恢复正常后就不需要继续考虑其他的结点了（这应该也算是一个规律，我们直接记住就行）

插入结点

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;//主要负责确定要插入结点的父结点位置，同时保证不会出现冗余//cur负责为parent探路，最后cur一定指向空（相当于没用后被置空），parent指向的结点就是插入结点的父结点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);//重新令cur指向新申请的结点//新结点的k小于parent指向结点的kif (kv.first < parent->_kv.first){parent->_left = cur;//将新结点插入到父结点的左子树上}else{parent->_right = cur;//将新结点插入父结点的右子树上}cur->_parent = parent;//新结点插入后，新结点有了父亲结点，它的父亲结点就是parent指向的结点，所以将cur的_parent更新为parent
}

更新bf与判断旋转方式

吐槽：能发现这种更新机制的人的大脑构造可能真的跟我们不一样🤡

基本概念：插入新结点必然会导致其父结点的bf产生变化，并可能会导致它的爷爷结点甚至更向上的某个祖先结点的bf发生变化，当某个祖先结点的bf == 2或-2时需要以该祖先结点为基础进行旋转

结论1：对父结点bf的修改可以通过判断插入结点是父结点的左还是右结点然后++或--即可

结论2：对爷爷结点和更向上的祖先结点的bf的修改需要利用循环判断的方式实现，当某个祖先结点的bf在修改后变为2或-2时就需要以该祖先结点为基础进行旋转

由语言分析的例子可得结论3：

1、bf == 2时它左结点的bf若为1则采取LL右旋，若为-1则采取LR左右旋

2、bf == -2时它右结点的bf若为-1要采取RR左旋，若为1则采取RL右左旋

（旋转时都以parent指向的结点为基础）

//更新平衡因子
while (parent)
{if (cur == parent->_left){parent->_bf++;//新结点插在父结点左侧则父结点的bf++
++}else{parent->_bf--;//新结点插在父结点右侧则父结点的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){if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);//2 + 1 == LL右旋}else if (parent->_bf == 2 && cur->_bf == -1){RotateLR(parent);//2 + -1 == LR左右旋}else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);//-2 + -1  == RR左旋}else if (parent->_bf == -2 && cur->_bf == 1){RotateRL(parent);//-2 + 1 == RL右左旋}break;}else{// 理论而言不可能出现这个情况assert(false);}
}

旋转代码实现

准备工作一

1、我们向旋转函数中传入的都是bf==2或-2的结点的指针，即parent

2、通过上述语言分析的例子，我们可以发现在旋转函数中需要三个指针：

①当bf==2时

  • 指向bf==2结点的指针parent（函数的唯一形参，后两个指针需要依据该形参在函数中定义）
  • 指向parent指向结点的左结点的指针subL
  • 指向subL指向结点的右结点的指针subLR

②当bf==-2时

  • 指向bf==-2结点的指针parent（函数的唯一形参，后两个指针需要依据该形参在函数中定义）
  • 指向parent指向结点的右结点的指针subR
  • 指向subL指向结点的左结点的指针subRL

注意事项：

1、因为h>=0，所以当处理完h不为0的情况还要考虑h为0时存在的使用空指针问题

2、因为每个结点中存放了它的三个“亲人”结点的信息（左孩子、右孩子、父亲），所以如果bf==2或-2的结点为根结点那么在旋转时就不需要考虑该结点的父结点信息（它的父结点一直为nullptr），只需要考虑另外两个指针指向的结点的父结点信息（三个结点的孩子信息肯定一直需要考虑），如果不是bf==2或-2的结点不是根结点，由于它是“大哥”所以为了避免旋转后找不到它的父结点，需要先保存它的父结点信息，然后再进行旋转

3、旋转过程中三个指针指向的结点不会发生改变

LL右旋的实现

//右旋基础版（60结点是根结点）
void RotateR(Node* parent)//传入的结点都是结点为bf==2或-2的结点
{Node* subL = parent->_left;//subL指向根结点的左结点Node* subLR = subL->_right;//subLR指向subL所指向结点的右结点（若h==0则subLR指向空）parent->_left = subLR;//根结点的左结点更新为subLR指向的结点//只有在subLR不为空的时候才用更新它的父亲信息，如果为空时仍去更新就会出现使用空指针的问题if (subLR){subLR->_parent = parent;//更新subLR的父结点信息（加上只是为了防止使用空指针实际影响不大）}subL->_right = parent;//subL的右结点变为根结点parent->_parent = subL;//后将根结点中存放的父结点信息由nullptr变为subL_root = subL;//右旋后是subL指向的结点作为根结点，令整棵树的_root也指向subL指向的结点_root->_parent = nullptr;//根结点没有父结点parent->_bf = subL->_bf = 0;//更新此时的平衡因子，在上面我们总结过了规律，LL右旋一定会导致新插入结点的父亲和爷爷结点的bf变为0
}

//右旋完全版（parent指向的结点可能不是初始根节点）
void RotateR(Node* parent)//传入的参数是平衡因子不为1、0、-1的结点
{Node* subL = parent->_left;//subL指向parent结点的左结点Node* subLR = subL->_right;//subLR指向subL指向的结点的右结点parent->_left = subLR;//parent的左结点更新为subLR指向的结点//subLR可能为空，只有它不为空的时候才去更新它的父亲信息if (subLR){subLR->_parent = parent;//更新subLR的父结点信息}subL->_right = parent;//subL的右结点变为了parent指向的结点Node* ppNode = parent->_parent;//先保存自己原先得父亲结点信息parent->_parent = subL;//后将parent指向的结点中存放的父结点信息由原来的某个结点变为subL//如果parent指向的结点的确是初始根结点if (parent == _root)//_root指向原始根节点,在建树的时候就已经确定{_root = subL;//右旋后应该是subL作为初始根节点，令_root也指向subL指向的结点_root->_parent = nullptr;//初始根节点没有父结点，将存放父结点信息的指针置空}else//如果parent指向的结点不是初始根结点{if (ppNode->_left == parent)//如果parent是原父结点的左结点{ppNode->_left = subL;//将原父结点中存放的左结点信息变为subL}else//如果parent是原父结点的右结点{ppNode->_right = subL;//将原父结点中存放的右结点信息变为subL}subL->_parent = ppNode;//同时将subL中存放的父结点的信息更新为parent之前的父结点}parent->_bf = subL->_bf = 0;//更新平衡因子
}

RR左旋的实现

道理与LL右旋基本一致，只需该改变一些变量，即可具体内容不再过多描述

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

准备工作二

1、双重旋只需要确定每次的旋转点即可（该点也是固定的），可以复用左或右旋的代码，它的关键点在于更新旋转后和parent指向结点的bf和parent指向结点的左或右结点的bf的值

2、旋转完后subLR和subRL指向的结点的bf均为0

3、通过语言分析部分的描述我们可以得出以下结论：

①LR左右旋时

  • subLR指向结点的bf为1时，旋转后praent和subL指向结点的bf分别为-1和0
  • subLR指向结点的bf为-1时，旋转后praent和subL指向结点的bf分别为0和1
  • subLR指向结点的bf为0时，旋转后praent和subL指向结点的bf均为0

②RL右左旋时

  • subRL指向结点的bf为1时，旋转后praent和subR指向结点的bf分别为0和-1
  • subRL指向结点的bf为-1时，旋转后praent和subR指向结点的bf分别为1和0
  • subRL指向结点的bf为0时，旋转后praent和subR指向结点的bf均为0 

LR左右旋的实现

void RotateLR(Node* parent)
{//这里的subL和subLR的仅用于修改父亲和爷爷结点的bfNode* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);RotateR(parent);subLR->_bf = 0;//旋转完后subLR指向的结点的bf为0if (bf == 1){parent->_bf = -1;subL->_bf = 0;	}else if (bf == -1){parent->_bf = 0;subL->_bf = 1;}else if (bf == 0){parent->_bf = 0;subL->_bf = 0;}
}

RL右左旋的实现

不解释了

void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);subRL->_bf = 0;//旋转完后subRL指向的结点的bf为0if (bf == 1){parent->_bf = 0;subR->_bf = -1;}else if (bf == -1){parent->_bf = 1;subR->_bf = 0;}else{parent->_bf = 0;subR->_bf = 0;}
}

完整代码

AVL树的删除相比于插入更加复杂，这里不再过多阐述，考研或者面试一般不会要求手写AVL树

一些基础功能的代码就放在整体代码中了

#pragma once#include <iostream>
#include <assert.h>
using namespace std;template<class K, class V>
struct  AVLTreeNode
{//三叉链结构便于向上寻找自己的父亲、爷爷等长辈结点并修改它们的平衡因子AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K, V> _kv;int _bf; //平衡因子AVLTreeNode(const pair<K,V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_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;//主要负责确定要插入结点的父结点位置，同时保证不会出现冗余//cur负责为parent探路，最后cur一定指向空（相当于没用后被置空），parent指向的结点就是插入结点的父结点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);//重新令cur指向新申请的结点//新结点的k小于parent指向结点的kif (kv.first < parent->_kv.first){parent->_left = cur;//将新结点插入到父结点的左子树上}else{parent->_right = cur;//将新结点插入父结点的右子树上}cur->_parent = parent;//新结点插入后，新结点有了父亲结点，它的父亲结点就是parent指向的结点，所以将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){if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);//2 + 1 == LL右旋}else if (parent->_bf == 2 && cur->_bf == -1){//RotateLR(parent);//2 + -1 == LR左右旋continue;}else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);//-2 + -1  == RR左旋}else if (parent->_bf == -2 && cur->_bf == 1){RotateRL(parent);//-2 + 1 == RL右左旋}break;}else{// 理论而言不可能出现这个情况std::cout << "bf != 0、-1、1、-2、2" << std::endl;assert(false);}}}//查找函数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;}//RR左旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_right == parent){ppNode->_right = subR;}else{ppNode->_left = subR;}subR->_parent = ppNode;}parent->_bf = subR->_bf = 0;}void RotateLR(Node* parent)
{//这里的subL和subLR的仅用于修改父亲和爷爷结点的bfNode* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);RotateR(parent);subLR->_bf = 0;//旋转完后subLR指向的结点的bf为0if (bf == 1){parent->_bf = -1;subL->_bf = 0;}else if (bf == -1){parent->_bf = 0;subL->_bf = 1;}{parent->_bf = 0;subL->_bf = 0;}}//LL右旋//右旋完全版（parent指向的结点可能不是初始根节点）void RotateR(Node* parent)//传入的参数是平衡因子不为1、0、-1的结点{Node* subL = parent->_left;//subL指向parent结点的左结点Node* subLR = subL->_right;//subLR指向subL指向的结点的右结点parent->_left = subLR;//parent的左结点更新为subLR指向的结点//subLR可能为空，只有它不为空的时候才去更新它的父亲信息if (subLR){subLR->_parent = parent;//更新subLR的父结点信息}subL->_right = parent;//subL的右结点变为了parent指向的结点Node* ppNode = parent->_parent;//先保存自己原先得父亲结点信息parent->_parent = subL;//后将parent指向的结点中存放的父结点信息由原来的某个结点变为subL//如果parent指向的结点的确是初始根结点if (parent == _root)//_root指向原始根节点,在建树的时候就已经确定{_root = subL;//右旋后应该是subL作为初始根节点，令_root也指向subL指向的结点_root->_parent = nullptr;//初始根节点没有父结点，将存放父结点信息的指针置空}else//如果parent指向的结点不是初始根结点{if (ppNode->_left == parent)//如果parent是原父结点的左结点{ppNode->_left = subL;//将原父结点中存放的左结点信息变为subL}else//如果parent是原父结点的右结点{ppNode->_right = subL;//将原父结点中存放的右结点信息变为subL}subL->_parent = ppNode;//同时将subL中存放的父结点的信息更新为parent之前的父结点}parent->_bf = subL->_bf = 0;//更新平衡因子}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);subRL->_bf = 0;//旋转完后subRL指向的结点的bf为0if (bf == 1){parent->_bf = 0;subR->_bf = -1;}else if (bf == -1){parent->_bf = 1;subR->_bf = 0;}else{parent->_bf = 0;subR->_bf = 0;}}//中序遍历函数void InOrder(){_InOrder(_root);cout << endl;}//判断是否平衡bool IsBalance(){return _IsBalance(_root);}//判断高度int Height(){return _Height(_root);}//判断结点个数int Size(){return _Size(_root);}//避免接口暴露，让处理函数的权限为private
private:int _Size(Node* root){return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;}int _Height(Node* root){if (root == nullptr)return 0;return max(_Height(root->_left), _Height(root->_right)) + 1;}bool _IsBalance(Node* root){if (root == nullptr)return true;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);// 不平衡if (abs(leftHeight - rightHeight) >= 2){cout << root->_kv.first << endl;return false;}// 顺便检查一下平衡因子是否正确if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << endl;return false;}return _IsBalance(root->_left)&& _IsBalance(root->_right);}//中序遍历void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}private:Node* _root = nullptr;
};//测试代码
void TestAVLTree1()
{int a[] = { 4, 2, 6, 1, 3, 5, 15, 7,16,14 };//插入14的时候出错了AVLTree<int, int> t1;for (auto e : a){t1.Insert({ e,e });}t1.InOrder();cout << t1.IsBalance() << endl;
}

~over~

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/334464.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Android Studio 所有历史版本下载

Android Studio 所有历史版本下载

一、官网链接 https://developer.android.google.cn/studio/archive 操作 二、AndroidDevTools地址 https://www.androiddevtools.cn/ 参考 https://blog.csdn.net/qq_27623455/article/details/103008937
阅读更多...
Golang | Leetcode Golang题解之第102题二叉树的层序遍历

Golang | Leetcode Golang题解之第102题二叉树的层序遍历

题目&#xff1a; 题解&#xff1a; func levelOrder(root *TreeNode) [][]int {ret : [][]int{}if root nil {return ret}q : []*TreeNode{root}for i : 0; len(q) > 0; i {ret append(ret, []int{})p : []*TreeNode{}for j : 0; j < len(q); j {node : q[j]ret[i] …
阅读更多...
【加密与解密（第四版）】第十五章笔记

【加密与解密（第四版）】第十五章笔记

第十五章 专用加密软件 15.1 认识壳 15.2 压缩壳 UPX、ASPack、PECompact 15.3 加密壳 ASProtect(压缩、加密、反跟踪代码、CRC校验、花指令)、Armadillo(穿山甲)、EXECryptor、Themida 15.4 虚拟机保护软件 虚拟机引擎&#xff08;编译器解释器虚拟CPU环境指令系统&#xff…
阅读更多...
Python代码：十七、生成列表

Python代码：十七、生成列表

1、题目 描述&#xff1a; 一串连续的数据用什么记录最合适&#xff0c;牛牛认为在Python中非列表&#xff08;list&#xff09;莫属了。现输入牛牛朋友们的名字&#xff0c;请使用list函数与split函数将它们封装成列表&#xff0c;再整个输出列表。 输入描述&#xff1a; …
阅读更多...
关于智慧校园安全用电监测系统的设计

关于智慧校园安全用电监测系统的设计

人生人身安全是大家关注的话题&#xff0c;2019年12月中国消防统计近五年发生在全国学生宿舍的火灾2314起&#xff08;中国消防2019.12.应急管理部消防救援局官方微博&#xff09;&#xff0c;违规电器是引发火灾的主因。如果在各寝室安装智能用电监测器实时监督线路参数&#…
阅读更多...
python-绘制五星红旗（非标准）

python-绘制五星红旗（非标准）

完整代码如下&#xff1a; #五星红旗&#xff08;非标准版&#xff09; from turtle import* import math from random import* tracer(0) penup() goto(-640,220) pendown() color(gold,gold) begin_fill() for i in range(5): fd(150) right(144) # 大五角星 penup(…
阅读更多...
[9] CUDA性能测量与错误处理

[9] CUDA性能测量与错误处理

CUDA性能测量与错误处理 讨论如何通过CUDA事件来测量它的性能如何通过CUDA代码进行调试 1.测量CUDA程序的性能 1.1 CUDA事件 CPU端的计时器可能无法给出正确的内核执行时间CUDA事件等于是在你的CUDA应用运行的特定时刻被记录的时间戳&#xff0c;通过使用CUDA事件API&#…
阅读更多...
JVM内存模型详解

JVM内存模型详解

Java虚拟机&#xff08;JVM&#xff09;是Java程序运行的基础环境&#xff0c;它负责将Java代码转换为机器码并执行。在JVM中&#xff0c;内存管理是一个核心部分&#xff0c;它决定了Java程序如何分配、使用和回收内存。了解JVM的内存模型对于编写高效、健壮的Java程序至关重要…
阅读更多...
生成式AI模型大PK——GPT-4、Claude 2.1和Claude 3.0 Opus

生成式AI模型大PK——GPT-4、Claude 2.1和Claude 3.0 Opus

RAG(检索增强生成)系统的新评估似乎每天都在发布&#xff0c;其中许多都集中在有关框架的检索阶段。然而&#xff0c;生成方面——模型如何合成和表达这些检索到的信息&#xff0c;在实践中可能具有同等甚至更大的意义。许多实际应用中的案例证明&#xff0c;系统不仅仅要求从上…
阅读更多...
centos下给es7.12.1设置密码

centos下给es7.12.1设置密码

安装可参考&#xff1a; centos7下安装elasticsearch7.8.1并配置远程连接_在一台服务器centos7上安装和配置elasticsearch。-CSDN博客 1、先停掉es进程 2、设置输入密码后访问配置 cd /home/soft/elasticsearch-7.12.1/config vim elasticsearch.yml 3、启动es服务 cd /home/…
阅读更多...
echarts全局设置饼图的颜色

echarts全局设置饼图的颜色

&#x1f337;第一步 在js文件中写入你需要的颜色 这里的颜色也可以写渐变的 &#x1f337;下一步 在main.is中引用全局挂载 &#x1f337;最后一步 在初始化的时候加一个macarons即可 &#x1f337;第一步 在js文件中写入你需要的颜色 这里的颜色也可以写渐变的 (functi…
阅读更多...
LeetCode199二叉树的右视图

LeetCode199二叉树的右视图

题目描述 给定一个二叉树的 根节点 root&#xff0c;想象自己站在它的右侧&#xff0c;按照从顶部到底部的顺序&#xff0c;返回从右侧所能看到的节点值。 解析 这一题的关键其实就是找到怎么去得到当前是哪一层级&#xff0c;可以利用队列对二叉树进行层次遍历&#xff0c;但…
阅读更多...
人才测评的应用：人才选拔，岗位晋升，面试招聘测评

人才测评的应用：人才选拔，岗位晋升，面试招聘测评

人才测评自诞生以来&#xff0c;就被广泛应用在各大方面&#xff0c;不仅是我们熟悉的招聘上&#xff0c;还有其他考核和晋升&#xff0c;都会需要用到人才测评。不知道怎么招聘&#xff1f;或者不懂得如何实现人才晋升&#xff1f;都可以参考人才测评&#xff0c;利用它帮我们…
阅读更多...
linux 定时执行shell、python脚本

linux 定时执行shell、python脚本

在linux里设置定时执行一般是用crontab&#xff0c;如果没有的话&#xff0c;可以先安装&#xff1a; 安装 查看是否安装 cron -v # 对于基于Debian的系统&#xff08;如Ubuntu&#xff09; sudo apt-get install cron# 对于基于RedHat的系统&#xff08;如CentOS&#xff…
阅读更多...
FL Studio v21.2.3.4004中文破解版百度网盘下载

FL Studio v21.2.3.4004中文破解版百度网盘下载

FL Studio v21.2.3.4004中文破解版是一款完整的软件音乐制作环境或数字音频工作站 (DAW)。代表了超过 18 年的创新发展&#xff0c;它在一个软件包中提供了您创作、编曲、录制、编辑、混音和掌握专业品质音乐所需的一切。FL Studio v21.2.3.4004中文破解版现在是世界上最受欢迎…
阅读更多...
解决LabVIEW通过OPC Server读取PLC地址时的错误180121602

解决LabVIEW通过OPC Server读取PLC地址时的错误180121602

在使用LabVIEW通过OPC Server读取PLC地址时&#xff0c;若遇到错误代码180121602&#xff0c;建议检查网络连接、OPC Server和PLC配置、用户权限及LabVIEW设置。确保网络畅通&#xff0c;正确配置OPC变量&#xff0c;取消缓冲设置以实时读取数据&#xff0c;并使用诊断工具验证…
阅读更多...
蓝桥杯—SysTick中断精准定时实现闪烁灯

蓝桥杯—SysTick中断精准定时实现闪烁灯

在嵌入式系统中&#xff0c;SysTick_Handler 是一个中断服务例程&#xff08;Interrupt Service Routine, ISR&#xff09;&#xff0c;用于处理 SysTick 定时器的中断。SysTick 定时器通常用于提供一个周期性的定时中断&#xff0c;可以用来实现延时或者周期性任务。 SysTick…
阅读更多...
UVa1466/LA4849 String Phone

UVa1466/LA4849 String Phone

UVa1466/LA4849 String Phone 题目链接题意分析AC 代码 题目链接 本题是2010年icpc亚洲区域赛大田赛区的G题 题意 平面网格上有n&#xff08;n≤3000&#xff09;个单元格&#xff0c;各代表一个重要的建筑物。为了保证建筑物的安全&#xff0c;警察署给每个建筑物派了一名警察…
阅读更多...
【OpenGL手册14】实例化

【OpenGL手册14】实例化

目录 一、说明 二、实例化 三、实例化数组 四、小行星带 五、完整代码 六、结论 一、说明 实例化渲染&#xff0c;是用少数数据做模板&#xff0c;实现海量物体渲染的手段方法。用实例化渲染&#xff0c;需要对每个实例产生一定描述数据。如何实现&#xff1f;请看本文下…
阅读更多...
微软Copilot+ PC：Phi-Silica

微软Copilot+ PC：Phi-Silica

大模型技术论文不断&#xff0c;每个月总会新增上千篇。本专栏精选论文重点解读&#xff0c;主题还是围绕着行业实践和工程量产。若在某个环节出现卡点&#xff0c;可以回到大模型必备腔调重新阅读。而最新科技&#xff08;Mamba&#xff0c;xLSTM,KAN&#xff09;则提供了大模…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023