高级数据结构——平衡二叉树（AVL树）

目录

1. 底层结构

2. AVL数的概念 

3. AVL树节点的定义

4. 基本框架

5. AVL树的插入

6. AVL树的旋转

6.1 左单旋

6.2 右单旋

6.3 左右双旋 

6.4 右左双旋

7. AVL树的验证

8. AVL树的查找

9. AVL树的删除

10. AVL树的性能

11. 总代码

11.1 AVLTree

11.2 Test.cpp

1. 底层结构

前面对map、multimap、set、multiset进行了简单的介绍，这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。

2. AVL数的概念 

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

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

  1. 它的左右子树都是AVL树
  2. 任何一颗左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)。
  • 0代表左右高度相等；
  • 1代表右子树高1；
  • -1代表左子树高1。

如果一棵二叉搜索树是高度平衡的（相对平衡），它就是AVL树。如果它有n个结点，其高度可保持在O(logN)，搜索时间复杂度O(logN)。

3. AVL树节点的定义

这里我们实现的AVL树为KV模型，自然节点的模板参数有两个，并且节点定义为三叉连结构（左孩子，右孩子，父亲），在二叉链表的基础上加了一个指向父结点的指针域，使得即便于查找孩子结点，又便于查找父结点。接着还需要创建一个变量_bf作为平衡因子（右子树 - 左子树的高度差）。最后写一个构造函数初始化变量即可。

//节点类
template<class K, class V>
struct AVLTreeNode
{
	//存储的键值对
	pair<K, V> _kv;
	//三叉连结构
	AVLTreeNode<K, V>* _left;//左孩子
	AVLTreeNode<K, V>* _right;//右孩子
	AVLTreeNode<K, V>* _parent;//父亲
	//平衡因子_bf
	int _bf;//右子树 - 左子树的高度差
	//构造函数
	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _bf(0)
	{}
};

4. 基本框架

此部分内容为AVL树的类，主要作用是来完成后续的插入旋转删除……操作：

//AVL树的类
template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
    //……
private:
	Node* _root;
};

5. AVL树的插入

插入主要分为这几大步骤：

  • 1、一开始为空树，直接new新节点
  • 2、一开始非空树，寻找插入的合适位置
  • 3、找到插入的合适位置后，进行父亲与孩子的双向链接
  • 4、更新新插入的节点祖先的平衡因子
  • 5、针对不合规的平衡因子进行旋转调整

接下来对其进行逐个分析：

  • 1、一开始为空树，直接new新节点

因为树为空的，所以直接new一个新插入的节点，将其作为根_root即可，接着更新平衡因子_bf为0，最后返回true。

  • 2、一开始非空树，寻找插入的合适位置

这里和二叉搜索树的寻找合适的插入位置的思想一样，都要遵循以下几步：

  1. 插入的值 > 节点的值，更新到右子树查找
  2. 插入的值 < 节点的值，更新到左子树查找
  3. 插入的值 = 节点的值，数据冗余插入失败，返回false

当循环结束的时候，就说明已经找到插入的合适位置，即可进行下一步链接。

  • 3、找到插入的合适位置后，进行父亲与孩子的双向链接：

注意这里节点的构成为三叉链，因此最后链接后端孩子和父亲是双向链接，具体操作如下：

  1. 插入的值 > 父亲的值，把插入的值链接在父亲的右边
  2. 插入的值 < 父亲的值，把插入的值链接在父亲的左边
  3. 因为是三叉连，插入后记得双向链接（孩子链接父亲）

走到这，说明节点已经插入完毕，但是接下来就要更新平衡因子了

  • 4、更新新插入的节点祖先的平衡因子：

当我们插入新节点后，子树的高度可能会发生变化，针对这一变化，我们给出以下要求：

  1. 子树的高度变了，就要继续往上更新
  2. 子树的高度不变，则更新完成
  3. 子树违反平衡规则（平衡因子的绝对值 >= 2），则停止更新，需要旋转子树进行调整

具体的更新规则如下：

  1. 新增结点在parent的右边，parent的平衡因子++。
  2. 新增结点在parent的左边，parent的平衡因子 — —。

每更新完一个节点的平衡因子后，都要进行如下判断：

  1. 如果parent的平衡因子等于-1或者1（说明原先是0，左右登高，插入节点后使左子树或右子树增高了）。表明还需要继续往上更新平衡因子。
  2. 如果parent的平衡因子等于0（说明原先是1或-1，一高一低，插入节点后填上了矮的那一方）表明无需更新平衡因子了。
  3. 如果parent的平衡因子等于-2或者2（说明原先是1或-1，一高一低，插入节点后填上了高的那一方），表明此时以parent结点为根结点的子树已经不平衡了，需要进行旋转处理。
  • 5、针对不合规的平衡因子进行旋转调整：

当父亲parent的平衡因子为2或-2时，就要进行旋转调整了，而又要分为以下4类进行旋转：

  1. 当parent的平衡因子为2，cur的平衡因子为1时，进行左单旋。
  2. 当parent的平衡因子为-2，cur的平衡因子为-1时，进行右单旋
  3. 当parent的平衡因子为-2，cur的平衡因子为1时，进行左右双旋。
  4. 当parent的平衡因子为2，cur的平衡因子为-1时，进行右左双旋。

代码如下：

//Insert插入
bool Insert(const pair<K, V>& kv)
{
	//1、一开始为空树，直接new新节点
	if (_root == nullptr)
	{
		//如果_root一开始为空树，直接new一个kv的节点，更新_root和_bf
		_root = new Node(kv);
		_root->_bf = 0;
		return true;
	}
	//2、寻找插入的合适位置
	Node* cur = _root;//记录插入的位置
	Node* parent = nullptr;//保存parent为cur的父亲
	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
		{
			//插入的值 = 节点的值，数据冗余插入失败，返回false
			return false;
		}
	}
	//3、找到了插入的位置，进行父亲与插入节点的链接
	cur = new Node(kv);
	if (parent->_kv.first < kv.first)
	{
		//插入的值 > 父亲的值，链接在父亲的右边
		parent->_right = cur;
	}
	else
	{
		//插入的值 < 父亲的值，链接在父亲的左边
		parent->_left = cur;
	}
	//因为是三叉连，插入后记得双向链接（孩子链接父亲）
	cur->_parent = parent;
	//4、更新新插入节点的祖先的平衡因子
	while (parent)//最远要更新到根
	{
		if (cur == parent->_right)
		{
			parent->_bf++;//新增结点在parent的右边，parent的平衡因子++
		}
		else
		{
			parent->_bf--;//新增结点在parent的左边，parent的平衡因子 --
		}
		//判断是否继续更新？
		if (parent->_bf == 0)// 1 or -1 -> 0 填上了矮的那一方
		{
			//1 or -1 -》 0 填上了矮的那一方，此时正好，无需更新
			break;
		}
		else if (parent->_bf == 1 || parent->_bf == -1)
		{
			//0 -》 1或-1  此时说明插入节点导致一边变高了，继续更新祖先
			cur = cur->_parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
			//1 or -1 -》2或-2 插入节点导致本来高的一边又变更高了
			//此时子树不平衡，需要进行旋转
			if (parent->_bf == 2 && cur->_bf == 1)
			{
				RotateL(parent);//右边高，左单旋
			}
			else if (parent->_bf == -2 && cur->_bf == -1)
			{
				RotateR(parent);//左边高，右单旋
			}
			else if (parent->_bf == -2 && cur->_bf == 1)
			{
				RotateLR(parent);//左右双旋
			}
			else if (parent->_bf == 2 && cur->_bf == -1)
			{
				RotateRL(parent);//右左双旋
			}
			break;
		}
		else
		{
			//插入之前AVL树就存在不平衡树，|平衡因子| >= 2的节点
			//实际上根据前面的判断不可能走到这一步，不过这里其实是为了检测先前的插入是否存在问题
			assert(false);
		}
	}
	return true;
}

6. AVL树的旋转

AVL树的旋转分为4种：

  1. 左单旋
  2. 右单旋
  3. 左右双旋
  4. 右左双旋

AVL树的旋转要遵循下面两个原则：

  • 1、保持搜索树的规则
  • 2、子树变平衡

6.1 左单旋

  • 条件：新节点插入较高右子树的右侧

  左单旋的情况非常多，这里我们画一张抽象图来演示：

这里的长方形条（a、b、c）表示的是子树，h为子树的高度，而30和60为实打实的节点。上述左单旋操作主要是完成了四件事：

  1. 让subRL变成parent的右子树，更新subRL的父亲为parent；
  2. 让subR变成根节点；
  3. 让parent变成subR的左子树，更新parent的父亲为subR；
  4. 更新平衡因子。

注意：

  1. parent可能为整棵树的一个子树，则需要链接parent的父亲和subR。
  2. subRL可能为空，但是更新subRL的父亲为parent是建立在subRL不为空的前提下完成的。

解释为何上述左单旋的可行性：

  • 首先，根据底层二叉搜索树的结构：b节点的值肯定是在30~60之间的，b去做30的右子树没有任何问题，且这里把60挪到根部，随即把30作为60的右子树，这样整体的变化就像是一个左旋一样，而且也满足二叉搜索树的性质且均平衡。

代码如下：

void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	Node* ppNode = parent->_parent;//提前保持parent的父亲
	//1、建立parent和subRL之间的关系
	parent->_right = subRL;
	if (subRL)//防止subRL为空
	{
		subRL->_parent = parent;
	}
	//2、建立subR和parent之间的关系
	subR->_left = parent;
	parent->_parent = subR;
	//3、建立ppNode和subR之间的关系
	if (parent == _root)
	{
		_root = subR;
		_root->_parent = nullptr;
	}
	else
	{
		if (parent == ppNode->_left)
		{
			ppNode->_left = subR;
		}
		else
		{
			ppNode->_right = subR;
		}
		subR->_parent = ppNode;//三叉链双向链接关系
	}
	//4、更新平衡因子
	subR->_bf = parent->_bf = 0;
}

6.2 右单旋

  •  条件：新节点插入较高左子树的左侧

图示：

同样这里的长方形条（a、b、c）表示的是子树，h为子树的高度，而30和60为实打实的节点。上述左单旋操作主要是完成了四件事：

  1. 让subLR变成parent的左子树，更新subLR的父亲为parent
  2. 让subL变成根节点
  3. 让parent变成subL的右子树，更新parent的父亲为subL
  4. 更新平衡因子

注意：

  1. parent可能为整棵树的一个子树，则需要链接parent的父亲和subL。
  2. subLR可能为空，但是更新subLR的父亲为parent是建立在subLR不为空的前提下完成的。

代码如下：
 

//2、右单旋
void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	Node* ppNode = parent->_parent;
	//1、建立parent和subLR之间的关系
	parent->_left = subLR;
	if (subLR)
	{
		subLR->_parent = parent;
	}
	//2、建立subL和parent之间的关系
	subL->_right = parent;
	parent->_parent = subL;
	//3、建立ppNode和subL的关系
	if (parent == _root)
	{
		_root = subL;
		_root->_parent = nullptr;
	}
	else
	{
		if (parent == ppNode->_left)
		{
			ppNode->_left = subL;
		}
		else
		{
			ppNode->_right = subL;
		}
		subL->_parent = ppNode;//三叉链双向关系
	}
	//4、更新平衡因子
	subL->_bf = parent->_bf = 0;
}

6.3 左右双旋 

  • 条件：新节点插入较高左子树的右侧

接下来图示解析左右双旋的具体解法。

  • 1、插入新节点：

此类模型既不满足左单旋的条件也不满足右单旋的条件，但是我们可以将其组合起来，即左右双旋（先左单旋，再右单旋）的办法重新建立平衡。接下来执行下一步左单旋：

  • 2、以节点30（subL）为旋转点左单旋：

此时再观察这幅图，这部就是一个妥妥的右单旋模型吗，把60的左子树看成一个整体，此时新插入的节点即插入较高左子树的左侧，刚好符合右单旋的性质，接下来即可进行右单旋：

  • 3、以节点90（parent）为旋转点进行右单旋：

此时左右双旋已经完成，最后一步为更新平衡因子，但是更新平衡因子又分如下三类：

  • 1、当subLR原始平衡因子是-1时，左右双旋后parent、subL、subLR的平衡因子分别更新为1、0、0。

  •  2、当subLR原始平衡因子是1时，左右双旋后parent、subL、subLR的平衡因子分别更新为0、-1、0。

  •  3、当subLR原始平衡因子是0时，左右双旋后parent、subL、subLR的平衡因子分别更新为0、0、0。  

这里可以看出唯有subLR平衡因子为0的情况下在进行左右旋转后，三个节点的平衡因子都要更新为0。

  • 代码如下：
//3、左右双旋
void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;//提前记录subLR的平衡因子
	//1、以subL为根传入左单旋
	RotateL(subL);
	//2、以parent为根传入右单旋
	RotateR(parent);
	//3、重新更新平衡因子
	if (bf == 0)
	{
		parent->_bf = 0;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else if (bf == 1)
	{
		parent->_bf = 0;
		subL->_bf = -1;
		subLR->_bf = 0;
	}
	else if (bf == -1)
	{
		parent->_bf = 1;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else
	{
		assert(false);//此时说明旋转前就有问题，检查
	}
}

6.4 右左双旋

  • 条件：新节点插入较高右子树的左侧

接下来图示解析左右双旋的具体解法。

  • 1、插入新节点：

注意这里的新节点插在了较高右子树的左侧，不能用上文的单旋转以及左右旋转，相反而应使用右左旋转（先右单旋，再左单旋）来解决，接下来执行下一步右单旋：

  • 2、以节点90（subR）为旋转点右单旋：

 此时再观察这幅图，这部就是一个妥妥的左单旋模型吗，把60的右子树看成一个整体，此时新插入的节点即插入较高右子树的右侧，刚好符合左单旋的性质，接下来即可进行左单旋：

  • 3、以节点30（parent）为旋转点左单旋：

此时左右双旋已经完成，最后一步为更新平衡因子，但是更新平衡因子又分如下三类：

  • 1、当subRL原始平衡因子是-1时，右左双旋后parent、subR、subRL的平衡因子分别更新为0、1、0。

  •  2、当subRL原始平衡因子是1时，右左双旋后parent、subR、subRL的平衡因子分别更新为-1、0、0。

  •  3、当subRL原始平衡因子是0时，右左双旋后parent、subR、subRL的平衡因子分别更新为0、0、0。 

 这里可以看出唯有subRL平衡因子为0的情况下在进行左右旋转后，三个节点的平衡因子都要更新为0。

  • 代码如下：
//4、右左双旋
void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;//提前记录subLR的平衡因子
	//1、以subL为根传入左单旋
	RotateR(subR);
	//2、以parent为根传入右单旋
	RotateL(parent);
	//3、重新更新平衡因子
	if (bf == 0)
	{
		parent->_bf = 0;
		subR->_bf = 0;
		subRL->_bf = 0;
	}
	else if (bf == 1)
	{
		parent->_bf = -1;
		subR->_bf = 0;
		subRL->_bf = 0;
	}
	else if (bf == -1)
	{
		parent->_bf = 0;
		subR->_bf = 1;
		subRL->_bf = 0;
	}
	else
	{
		assert(false);//此时说明旋转前就有问题，检查
	}
}

7. AVL树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，就是看它是否为二叉搜索树，以及是否为一颗平衡树。接下来分别讨论：

  • 1、验证其为二叉搜索树：

这里我们只需要进行中序遍历看看结果是否可得到一个有序的序列，如果可以则证明是二叉搜索树，而中序遍历的实现非常简单，先前的二叉搜索树的实现已然完成过，这里直接给出代码：

//中序遍历的子树
void _InOrder(Node* root)
{
	if (root == nullptr)
		return;
 
	_InOrder(root->_left);
	cout << root->_kv.first << " ";
	_InOrder(root->_right);
}
//中序遍历
void InOrder()
{
	_InOrder(_root);
	cout << endl;
}

检测是否为二叉搜索树的代码实现后，接下来开始验证是否为平衡树。

  • 2、验证其为平衡树：

规则如下：（递归的思想）

  1. 空树也是平衡树，一开始就要判断
  2. 封装一个专门计算高度的函数（递归计算高度）后续用来计算高度差（平衡因子diff）
  3. 如过diff不等于root的平衡因子（root->_bf），或root平衡因子的绝对值超过1，则一定不是AVL树
  4. 继续递归到子树&&右树，直至结束

代码如下：

//验证一棵树是否为平衡树
bool IsBalanceTree()
{
	return _IsBalanceTree(_root);
}
//判读是否平衡的子树
bool _IsBalanceTree(Node* root)
{
	//空树也是AVL树
	if (nullptr == root)
		return true;
	//计算root节点的平衡因子diff：即root左右子树的高度差
	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);
	int diff = rightHeight - leftHeight;
	//如果计算出的平衡因子与root的平衡因子不相等，或root平衡因子的绝对值超过1，则一定不是AVL树
	if ((abs(diff) > 1))
	{
		cout << root->_kv.first << "节点平衡因子异常" << endl;
		return false;
	}
	if (diff != root->_bf)
	{
		cout << root->_kv.first << "节点平衡因子与root的平衡因子不等，不符合实际" << endl;
		return false;
	}
	//继续递归检测，直到结束
	return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}
//求高度的子树
int _Height(Node* root)
{
	if (root == nullptr)
		return 0;
	int lh = _Height(root->_left);
	int rh = _Height(root->_right);
	return lh > rh ? lh + 1 : rh + 1;
}

综合上述两大步骤的操作即可对一棵树充分的验证是否为AVL树。

8. AVL树的查找

Find查找函数的思路很简单，定义cur指针从根部开始按如下规则遍历：

  1. 若key值小于当前结点的值，则应该在该结点的左子树当中进行查找。
  2. 若key值大于当前结点的值，则应该在该结点的右子树当中进行查找。
  3. 若key值等于当前结点的值，则查找成功，返回true。
  4. 若遍历一圈cur走到nullptr了说明没有此结点，返回false。
//Find查找
bool Find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		if (cur->_key < key)
		{
			cur = cur->_right;//若key值大于当前结点的值，则应该在该结点的右子树当中进行查找。
		}
		else if (cur->_key > key)
		{
			cur = cur->_left;//若key值小于当前结点的值，则应该在该结点的左子树当中进行查找。
		}
		else
		{
			return true;//若key值等于当前结点的值，则查找成功，返回true。
		}
	}
	return false;//遍历一圈没找到返回false
}

9. AVL树的删除

删除了解即可。

因为AVL树也是二叉搜索树，主要是三个大思路：

  1. 按二叉搜索树的规则删除
  2. 更新平衡因子
  3. 出现不平衡，需要旋转调整

只不过与搜索二叉树的删除不同的是，删除节点后的平衡因子需要不断更新，最差情况下一直要调整到根节点的位置。具体这里就不再实现了，因为着实有点复杂。不过《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版这两本书上是有详细的讲解的哈。

10. AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即O(logN)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

11. 总代码

11.1 AVLTree

#pragma once
#include<queue>
#include<vector>
#include<iostream>
using namespace std;
//节点类
template<class K, class V>
struct AVLTreeNode
{
	//存储的键值对
	pair<K, V> _kv;
	//三叉连结构
	AVLTreeNode<K, V>* _left;//左孩子
	AVLTreeNode<K, V>* _right;//右孩子
	AVLTreeNode<K, V>* _parent;//父亲
	//平衡因子_bf
	int _bf;//右子树 - 左子树的高度差
	//构造函数
	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{}
};
//AVL树的类
template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	//1、按照搜索树的规则插入
	//2、是否违反平衡规则，如果违反就需要处理：旋转
	bool Insert(const pair<K, V>& kv)
	{	
		//1、一开始为空树，直接new新节点
		if (_root == nullptr)
		{
			//如果_root一开始为空树，直接new一个kv的节点，更新_root和_bf
			_root = new Node(kv);
			_root->_bf = 0;
			return true;
		}
		//2、寻找插入的合适位置
		Node* cur = _root;//记录插入的位置
		Node* parent = nullptr;//保存parent为cur的父亲
		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
			{
				//插入的值 = 节点的值，数据冗余插入失败，返回false
				return false;
			}
		}
		//3、找到了插入的位置，进行父亲与插入节点的链接
		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			//插入的值 > 父亲的值，链接在父亲的右边
			parent->_right = cur;
		}
		else
		{
			//插入的值 < 父亲的值，链接在父亲的左边
			parent->_left = cur;
		}
		//因为是三叉连，插入后记得双向链接（孩子链接父亲）
		cur->_parent = parent;
		//4、更新新插入节点的祖先的平衡因子
		while (parent)//最远要更新到根
		{
			if (cur == parent->_right)
			{
				parent->_bf++;//新增结点在parent的右边，parent的平衡因子++
			}
			else
			{
				parent->_bf--;//新增结点在parent的左边，parent的平衡因子 --
			}
			//判断是否继续更新？
			if (parent->_bf == 0)// 1 or -1 -> 0 填上了矮的那一方
			{
				//1 or -1 -》 0 填上了矮的那一方，此时正好，无需更新
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				//0 -》 1或-1  此时说明插入节点导致一边变高了，继续更新祖先
				cur = cur->_parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//1 or -1 -》2或-2 插入节点导致本来高的一边又变更高了
				//此时子树不平衡，需要进行旋转
				if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);//右边高，左单旋
				}
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);//左边高，右单旋
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);//左右双旋
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);//右左双旋
				}
				break;
			}
			else
			{
				//插入之前AVL树就存在不平衡树，|平衡因子| >= 2的节点
				//实际上根据前面的判断不可能走到这一步，不过这里其实是为了检测先前的插入是否存在问题
				assert(false);
			}
		}
		return true;
	}
//求一棵树的高度
	int Height()
	{
		return _Height(_root);
	}
//验证是否为一颗搜索二叉树
	void InOrder()
	{
		_InOrder(_root);//调用中序遍历子树
		cout << endl;
	}

//验证一棵树是否为平衡树
	bool IsBalanceTree()
	{
		return _IsBalanceTree(_root);
	}

private:
//1、左单旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* ppNode = parent->_parent;//提前保持parent的父亲
		//1、建立parent和subRL之间的关系
		parent->_right = subRL;
		if (subRL)//防止subRL为空
		{
			subRL->_parent = parent;
		}
		//2、建立subR和parent之间的关系
		subR->_left = parent;
		parent->_parent = subR;
		//3、建立ppNode和subR之间的关系
		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;//三叉链双向链接关系
		}
		//4、更新平衡因子
		subR->_bf = parent->_bf = 0;
	}
//2、右单旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* ppNode = parent->_parent;
		//1、建立parent和subLR之间的关系
		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}
		//2、建立subL和parent之间的关系
		subL->_right = parent;
		parent->_parent = subL;
		//3、建立ppNode和subL的关系
		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;//三叉链双向关系
		}
		//4、更新平衡因子
		subL->_bf = parent->_bf = 0;
	}
//3、左右双旋
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;//提前记录subLR的平衡因子
		//1、以subL为根传入左单旋
		RotateL(subL);
		//2、以parent为根传入右单旋
		RotateR(parent);
		//3、重新更新平衡因子
		if (bf == 0)
		{
			parent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else
		{
			assert(false);//此时说明旋转前就有问题，检查
		}
	}
//4、右左双旋
	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;//提前记录subLR的平衡因子
		//1、以subL为根传入左单旋
		RotateR(subR);
		//2、以parent为根传入右单旋
		RotateL(parent);
		//3、重新更新平衡因子
		if (bf == 0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else
		{
			assert(false);//此时说明旋转前就有问题，检查
		}
	}

	//中序遍历的子树
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;

		_InOrder(root->_left);
		cout << root->_kv.first <<" ";
		_InOrder(root->_right);
	}
	//求一棵树的高度的子树
	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;
		int lh = _Height(root->_left);
		int rh = _Height(root->_right);
		return lh > rh ? lh + 1 : rh + 1;
	}
	//判读是否平衡的子树
	bool _IsBalanceTree(Node* root)
	{
		//空树也是AVL树
		if (nullptr == root)
			return true;
		//计算root节点的平衡因子diff：即root左右子树的高度差
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		int diff = rightHeight - leftHeight;
		//如果计算出的平衡因子与root的平衡因子不相等，或root平衡因子的绝对值超过1，则一定不是AVL树
		if ((abs(diff) > 1))
		{
			cout << root->_kv.first << "节点平衡因子异常" << endl;
			return false;
		}
		if (diff != root->_bf)
		{
			cout << root->_kv.first << "节点平衡因子与root的平衡因子不等，不符合实际" << endl;
			return false;
		}
		//继续递归检测，直到结束
		return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
	}
public:
	vector<vector<int>> levelOrder() {
		vector<vector<int>> vv;
		if (_root == nullptr)
			return vv;

		queue<Node*> q;
		int levelSize = 1;
		q.push(_root);

		while (!q.empty())
		{
			// levelSize控制一层一层出
			vector<int> levelV;
			while (levelSize--)
			{
				Node* front = q.front();
				q.pop();
				levelV.push_back(front->_kv.first);
				if (front->_left)
					q.push(front->_left);

				if (front->_right)
					q.push(front->_right);
			}
			vv.push_back(levelV);
			for (auto e : levelV)
			{
				cout << e << " ";
			}
			cout << endl;
			// 上一层出完，下一层就都进队列
			levelSize = q.size();
		}
		return vv;
	}
	
private:
	Node* _root = nullptr;
};

11.2 Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<time.h>
#include<assert.h>
using namespace std;
#include"AVLTree.h"

void TestAVLTree1()
{
	int a[] = { 1,2,3,4,5,6,7,8 };
	AVLTree<int, int> t;
	t.Insert(make_pair(1, 1));
	t.Insert(make_pair(2, 2));
	t.Insert(make_pair(3, 3));
}
void TestAVLTree2()
{
	//int a[] = { 1,2,3,4,5,6,7,8 };
	int a[] = { 8,7,6,5,4,3,2,1 };
	AVLTree<int, int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
	}
}
void TestAVLTree3()
{
	const size_t N = 1024;
	vector<int> v;
	srand(time(0));
	v.reserve(N);
	for (size_t i = 0; i < N; i++)
	{
		//v.push_back(i);
		v.push_back(rand());
	}
	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}
	t.levelOrder();
	cout << endl;
	t.InOrder();
}
void TestAVLTree4()
{
	const size_t N = 1024 * 1024;
	vector<int> v;
	srand(time(0));
	v.reserve(N);
	for (size_t i = 0; i < N; i++)
	{
		v.push_back(i);//有序插入 --》检测单旋是否正确
		//v.push_back(rand());//乱序插入 --》检测双旋是否正确
	}
	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}
	cout << "是否平衡？" << t.IsBalanceTree() << endl;
	cout << "高度：" << t.Height() << endl;
	//t.InOrder();//判断是否二叉搜索树
}
int main()
{
	//TestAVLTree1();
	//TestAVLTree2();
	//TestAVLTree3();
	TestAVLTree4();
}

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

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

相关文章

SuperMap GIS基础产品移动GIS FAQ集锦（3）

SuperMap GIS基础产品移动GIS FAQ集锦（3）

SuperMap GIS基础产品移动GIS FAQ集锦&#xff08;3&#xff09; 【iMobile】网络分析中设置权值字段&#xff0c;如何添加多个权值字段&#xff1f; 【解决办法】通过权值字段集合类&#xff08;WeightFieldInfos&#xff09;设置&#xff0c;该类是权值字段信息对象&#x…
阅读更多...
【AI】Stable-Diffusion-WebUI使用指南

【AI】Stable-Diffusion-WebUI使用指南

注&#xff1a;csdn对图片有审核&#xff0c;审核还很奇葩&#xff0c;线稿都能违规&#xff0c;为保证完整的阅读体验建议移步至个人博客阅读 最近AI绘画实现了真人照片级绘画水准&#xff0c;导致AI绘画大火&#xff0c;公司也让我研究研究&#xff0c;借此机会正好了解一下…
阅读更多...
django旅游推荐系统-计算机毕设 附源码82884

django旅游推荐系统-计算机毕设 附源码82884

django旅游推荐系统 摘 要 随着社会的快速发展和人们生活水平的不断提高&#xff0c;旅游已逐渐成为人们生活的重要组成部分&#xff0c;用户能够获取旅游信息的渠道也随信息技术的广泛应用而增加。大量未经过滤的信息在展示给用户的同时&#xff0c;也淹没了用户真正感兴趣的信…
阅读更多...
配置NIS服务器及客户端

配置NIS服务器及客户端

在服务端安装所需软件包 设置主机名和NIS域名 编辑 NIS服务器主配置文件 最下面编辑访问控制 建立测试用户 配置NFS&#xff0c;否则客户端切换用户时&#xff0c;用户没有家目录 安装NFS所需软件包 Nfs-utils 给两个共享目录权限&#xff0c;编辑NFS配制文件 共享两个目录 重…
阅读更多...
【从零开始学习C++ | 第二十一篇】C++新增特性 （上）

【从零开始学习C++ | 第二十一篇】C++新增特性 （上）

目录 前言&#xff1a; 委托构造函数&#xff1a; 类内初始化&#xff1a; 空指针&#xff1a; 枚举类&#xff1a; 总结&#xff1a; 前言&#xff1a; C的学习难度大&#xff0c;内容繁多。因此我们要及时掌握C的各种特性&#xff0c;因此我们更新本篇文章&#xff0c;向…
阅读更多...
【数据管理架构】什么是 OLTP？

【数据管理架构】什么是 OLTP？

OLTP&#xff08;在线事务处理&#xff09;支持在 ATM 和在线银行、收银机和电子商务以及我们每天与之交互的许多其他服务背后进行快速、准确的数据处理。 什么是 OLTP&#xff1f; OLTP 或在线事务处理允许大量人员&#xff08;通常通过 Internet&#xff09;实时执行大量数据…
阅读更多...
【SpringCloud-5】gateway网关

【SpringCloud-5】gateway网关

网关是干啥用的就不用再说了。 sringcloud中的网关&#xff0c;第一代是zuul&#xff0c;但是性能比较差&#xff08;1.x是阻塞式的&#xff0c;2.x是基于Netty的&#xff09;&#xff0c;然后有了第二代GateWay&#xff0c;基于Reactor模型 异步非阻塞。 springcloud网关就是一…
阅读更多...
C++智能指针

C++智能指针

RAII RAII&#xff08;Resource Acquisition Is Initialization&#xff09;是一种利用对象生命周期来控制程序资源的技术 不需要显示的释放资源对象的资源在其生命周期类保持有效 通常控制的资源&#xff1a;动态申请的内存、文件描述符、互斥量、网络连接等 在对象构造时…
阅读更多...
多线程/std::thread线程退出方式详解

多线程/std::thread线程退出方式详解

文章目录 概述不 join 也不 detach执行了detach并不能万事大吉建议使用 join 函数 概述 这里默认你已经了解 std::thread 类的基本使用&#xff0c;和WinAPI多线程编程中 “如何优雅的退出线程” 等相关知识。阅读该文前&#xff0c;建议先看看《多线程 /C 11 std::thread 类深…
阅读更多...
python、pyqt5实现人脸检测、性别和年龄预测

python、pyqt5实现人脸检测、性别和年龄预测

摘要&#xff1a;这篇博文介绍基于opencv&#xff1a;DNN模块自带的残差网络的人脸、性别、年龄识别系统&#xff0c;系统程序由OpenCv, PyQt5的库实现。如图系统可通过摄像头获取实时画面并识别其中的人脸表情&#xff0c;也可以通过读取图片识别&#xff0c;本文提供完整的程…
阅读更多...
【IIS建站教程】windows本地搭建web服务，内网穿透发布公网访问

【IIS建站教程】windows本地搭建web服务，内网穿透发布公网访问

✨个人主页&#xff1a;bit me&#x1f447; 目 录 &#x1f43e;1.前言&#x1f490;2.Windows网页设置&#x1f338;2.1 Windows IIS功能设置&#x1f337;2.2 IIS网页访问测试 &#x1f340;3. Cpolar内网穿透&#x1f339;3.1 下载安装Cpolar&#x1f33b;3.2 Cpolar云端设…
阅读更多...
【Leetcode60天带刷】day36——56. 合并区间，738.单调递增的数字

【Leetcode60天带刷】day36——56. 合并区间，738.单调递增的数字

​ 题目&#xff1a; 56. 合并区间 以数组 intervals 表示若干个区间的集合&#xff0c;其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间&#xff0c;并返回 一个不重叠的区间数组&#xff0c;该数组需恰好覆盖输入中的所有区间 。 示例 1&#xff1a;…
阅读更多...
菜鸡shader:L4三色环境光原理妙用并在ue4中实现

菜鸡shader:L4三色环境光原理妙用并在ue4中实现

三色环境光的拓展运用 我的上一篇博客写了关于三色环境光的原理&#xff0c;这次就来简单拓展一下。最重要的核心思想其实就是取法线向量的第二个分量&#xff0c;因为它控制方法是指向xz平面的上或者下。 所以这次要用这个原来来单独摘出上层环境光&#xff0c;乘上菲涅尔&a…
阅读更多...
ASP.NET Core Web API之Token验证

ASP.NET Core Web API之Token验证

在实际开发中&#xff0c;我们经常需要对外提供接口以便客户获取数据&#xff0c;由于数据属于私密信息&#xff0c;并不能随意供其他人访问&#xff0c;所以就需要验证客户身份。那么如何才能验证客户的身份呢&#xff1f;今天以一个简单的小例子&#xff0c;简述ASP.NET Core…
阅读更多...
交叉熵、Focal Loss以及其Pytorch实现

交叉熵、Focal Loss以及其Pytorch实现

交叉熵、Focal Loss以及其Pytorch实现 本文参考链接&#xff1a;https://towardsdatascience.com/focal-loss-a-better-alternative-for-cross-entropy-1d073d92d075 文章目录 交叉熵、Focal Loss以及其Pytorch实现一、交叉熵二、Focal loss三、Pytorch1.[交叉熵](https://pyto…
阅读更多...
Python 动态生成系统数据库设计到word文档

Python 动态生成系统数据库设计到word文档

背景 经常需要交付一些系统文档而且基本都是word的&#xff0c;其中又有系统数据库介绍模块&#xff0c; 看着数据库里的几百张表于是我开始怀疑人生, 所以咱手写一个 涉及知识 pymysql 操作数据库 -tkinter GUI图形库threading 线程queue 阻塞队列pandas python数据计算…
阅读更多...
layui(5)——内置模块分页模块

layui(5)——内置模块分页模块

模块加载名称&#xff1a;laypage laypage 的使用非常简单&#xff0c;指向一个用于存放分页的容器&#xff0c;通过服务端得到一些初始值&#xff0c;即可完成分页渲染&#xff1a; <!DOCTYPE html> <html lang"en"><head><meta charset&quo…
阅读更多...
RocketMQ --- 实战篇

RocketMQ --- 实战篇

一、案例介绍 1.1、业务分析 模拟电商网站购物场景中的【下单】和【支付】业务 1.1.1、下单 流程 用户请求订单系统下单 订单系统通过RPC调用订单服务下单 订单服务调用优惠券服务&#xff0c;扣减优惠券 订单服务调用调用库存服务&#xff0c;校验并扣减库存 订单服务调…
阅读更多...
长尾关键词有什么作用？要怎么用？

长尾关键词有什么作用？要怎么用？

长尾关键词很多的网站都会忽略其存在&#xff0c;其实你不要小看长尾关键词&#xff0c;他将带给网站的流量也是极其可观的&#xff0c;所说比不上那些重点关键词的流量&#xff0c;但是对提升网站的权重还是有着重要的作用。 长尾关键词有什么用&#xff1f;长尾关键词的3…
阅读更多...
Gitlab群组及项目仓库搭建

Gitlab群组及项目仓库搭建

1、新建群组 2、新建项目 3、克隆到Visualstudio 复制克隆地址&#xff0c;克隆到本地 这里会让你登录账号 可以添加成员并邀请ta进项目组 从已注册用户列表中选择 4、Git工作流 回顾一下Git工作流&#xff0c;工程人员只需要从Develop分支新建自己的分支即可。分支命名以姓名…
阅读更多...
最新文章

Copyright @ 2022~2023