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指向结点的k
	if (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的仅用于修改父亲和爷爷结点的bf
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;

	RotateL(subL);
	RotateR(parent);

    subLR->_bf = 0;//旋转完后subLR指向的结点的bf为0

	if (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为0

	if (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指向结点的k
		if (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的仅用于修改父亲和爷爷结点的bf
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
		int bf = subLR->_bf;

   	RotateL(subL);
   	RotateR(parent);

   	subLR->_bf = 0;//旋转完后subLR指向的结点的bf为0

   	if (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为0

		if (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~

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

抖音小店新规重磅来袭！事关店铺流量！商家的福音来了？

抖音小店新规重磅来袭！事关店铺流量！商家的福音来了？

大家好&#xff0c;我是喷火龙。 就在前两天&#xff0c;抖店发布了新规&#xff0c;我给大家总结了一下&#xff0c;无非就是两点。 第一点&#xff1a;保证金下调&#xff0c;一证开多店。 第二点&#xff1a;新品上架破10单&#xff0c;有流量扶持。 咱来细细的解读&…
阅读更多...
无人机助力光伏项目测绘建模

无人机助力光伏项目测绘建模

随着全球对可再生能源需求的不断增长&#xff0c;光伏项目作为其中的重要一环&#xff0c;其建设规模和速度都在不断提高。在这一背景下&#xff0c;如何高效、准确地完成光伏项目的测绘与建模工作&#xff0c;成为了行业发展的重要课题。近年来&#xff0c;无人机技术的快速发…
阅读更多...
【产品经理】如何培养对市场的洞察力

【产品经理】如何培养对市场的洞察力

引言&#xff1a;        在最近频繁的产品管理职位面试中&#xff0c;我深刻体会到了作为产品经理需要的不仅仅是对市场和技术的敏锐洞察&#xff0c;更多的是在复杂多变的环境中&#xff0c;如何运用沟通、领导力和决策能力来引导产品从概念走向市场。这一系列博客将分享…
阅读更多...
技术驱动未来，全面揭秘 Sui 的生态发展和布局

技术驱动未来，全面揭秘 Sui 的生态发展和布局

在不到一年的时间里&#xff0c;由 Mysten Labs 团队创立的 Layer1 区块链 Sui 迅速崛起&#xff0c;成功跃升至去中心化金融&#xff08;DeFi&#xff09;的前十名。根据 DeFi Llama 的数据&#xff0c;Sui的总锁定价值&#xff08;TVL&#xff09;在短短四个月内增长超过 100…
阅读更多...
堆的实现

堆的实现

前言&#xff1a;本文讲述堆实现的几个难点&#xff0c;注意本文主要是以实现为主&#xff0c;建议有些基本概念认识的人阅读。 目录 1.堆 2.堆的实现 堆结构的定义&#xff1a; 要实现的接口&#xff1a; 接口的实现&#xff1a; 堆的初始化和销毁&#xff1a; 向堆中插…
阅读更多...
【简单介绍下链表基础知识】

【简单介绍下链表基础知识】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…
阅读更多...
第八届能源、环境与材料科学国际学术会议(EEMS 2024）

第八届能源、环境与材料科学国际学术会议(EEMS 2024）

文章目录 一、重要信息二、大会简介三、委员会四、征稿主题五、论文出版六、会议议程七、出版信息八、征稿编辑 一、重要信息 会议官网&#xff1a;http://ic-eems.com主办方&#xff1a;常州大学大会时间&#xff1a;2024年06月7-9日大会地点&#xff1a;新加坡 Holiday Inn …
阅读更多...
OA界面这么香吗？总有老铁私信，让我多发点，他好参考。

OA界面这么香吗？总有老铁私信，让我多发点，他好参考。

OA的确是B端系统应用最为广泛的一种&#xff0c;这次再给大家分享十来个页面&#xff0c;希望对他们的界面提升有所帮助。 举报 评论 3
阅读更多...
计算机考研｜408开始的晚，怎么入手复习？六个月保姆级规划

计算机考研｜408开始的晚，怎么入手复习？六个月保姆级规划

万事开头难&#xff0c;特别是408 大家在第一遍复习408的时候&#xff0c;基本上都有这个问题&#xff0c;就是复习速度慢&#xff0c;理解成本高&#xff0c;因为数据结构&#xff0c;计算机组成原理这些都是大一大二开始学的内容&#xff0c;等到自己准备考研的时候&#xf…
阅读更多...
洗地机哪个牌子最好用？2024洗地机排行榜

洗地机哪个牌子最好用？2024洗地机排行榜

随着人们生活水平的提升&#xff0c;智能清洁家电已经成为日常生活中的必需品。如今的清洁家电市场上&#xff0c;洗地机、吸尘器和扫地机器人等设备各有其独特的功能和优势。洗地机结合了扫、拖、吸和自清洁等多种功能&#xff0c;不仅可以处理干湿垃圾&#xff0c;还能高效清…
阅读更多...
打破传统相亲模式，这几款靠谱的相亲软件助你脱单

打破传统相亲模式，这几款靠谱的相亲软件助你脱单

相亲软件在当今社会已经变得越来越普遍&#xff0c;市面上有众多相亲软件可供选择&#xff0c;但哪些相亲软件好用呢&#xff1f;下面介绍几款备受好评的相亲软件&#xff0c;帮助你在茫茫人海中找到那个对的人&#xff01; 1、一伴婚恋 这个APP它最大的优点就是信息真实靠谱…
阅读更多...
mac上简单实现一个java调用C接口的JNI

mac上简单实现一个java调用C接口的JNI

目录 安装JDK及配置环境变量写Java代码生成头文件实现本地方法编译本地代码运行 Java 程序总结步骤 安装JDK及配置环境变量 参考&#xff1a;MAC系统安装JDK1.8及环境变量配置 写Java代码 // 文件名&#xff1a;Calculator.java public class Calculator {// 声明本地方法pu…
阅读更多...
Vue 3指令与事件处理

Vue 3指令与事件处理

title: Vue 3指令与事件处理 date: 2024/5/25 18:53:37 updated: 2024/5/25 18:53:37 categories: 前端开发 tags: Vue3基础指令详解事件处理高级事件实战案例最佳实践性能优化 第1章 Vue 3基础 1.1 Vue 3简介 Vue 3 是一个由尤雨溪&#xff08;尤大&#xff09;领导的开源…
阅读更多...
5.22-wjn

5.22-wjn

使用select实现的TCP并发服务器端 #define SER_PORT 8888 #define SER_IP "192.168.125.158" int main(int argc, const char *argv[]) {//1、为通信创建一个端点int sfd socket(AF_INET, SOCK_STREAM, 0);//参数1&#xff1a;说明使用的是ipv4通信域//参数2&#…
阅读更多...
SpringBoot Bean

SpringBoot Bean

配置优先级 Bean的管理 从IOC容器中获取Bean对象&#xff1a;注入IOC容器对象 bean的作用域 Bean对象默认在容器启动时实例化 Lazy在第一次使用时初始化 Bean的管理&#xff1a;第三方Bean 引入依赖&#xff0c;每次解析创建新对象&#xff0c;浪费资源 将第三方对象交给…
阅读更多...
vr商品全景展示场景编辑软件的优点

vr商品全景展示场景编辑软件的优点

3D模型展示网站搭建编辑器以强大的3D编辑引擎和逼真的渲染效果&#xff0c;让您轻松实现模型展示的优化。让用户通过简单的操作&#xff0c;就能满足个人/设计师/商户多样化展示的需求&#xff0c;让您的模型成为独一无二的杰作。 3D模型展示网站搭建编辑器采用国内领先的实时互…
阅读更多...
软件设计师中级

软件设计师中级

计算机系统 运算器和控制器 算术逻辑单元 累加寄存器器 状态寄存器 数据缓冲寄存器 指令寄存器 程序计数器 地址寄存器 指令译码器 内存按字节编址 内存存储单元16位 1 浮点数 浮点数范围&#xff1a;-2的(2的阶码次)-1到-2的(2的阶码次)-1 乘 1-2负尾数次 海明码 海明码&…
阅读更多...
力扣HOT100 - 136. 只出现一次的数字

力扣HOT100 - 136. 只出现一次的数字

解题思路&#xff1a; class Solution {public int singleNumber(int[] nums) {int single 0;for (int num : nums) {single ^ num;}return single;} }
阅读更多...
Java基础的语法---StringBuilder

Java基础的语法---StringBuilder

StringBuilder 构造方法 StringBuilder()&#xff1a;创建一个空的StringBuilder实例。 StringBuilder(String str)&#xff1a;创建一个StringBuilder实例&#xff0c;并将其初始化为指定的字符串内容。 StringBuilder(int a): 创建一个StringBuilder实例…
阅读更多...
AWTK实现汽车仪表Cluster/DashBoard嵌入式GUI开发（七）：快启

AWTK实现汽车仪表Cluster/DashBoard嵌入式GUI开发（七）：快启

前言： 汽车仪表是人们了解汽车状况的窗口，而仪表中的大部分信息都是以指示灯形式显示给驾驶者。仪表指示灯图案都较为抽象，对驾驶不熟悉的人在理解仪表指示灯含义方面存在不同程度的困难，尤其对于驾驶新手，如果对指示灯的含义不求甚解，有可能影响驾驶的安全性。即使是对…
阅读更多...
最新文章

Copyright @ 2022~2023