平武建站

数据结构(C++):AVL树实现篇-创新互联

目录

成都网站建设、网站建设服务团队是一支充满着热情的团队，执着、敏锐、追求更好，是创新互联的标准与要求，同时竭诚为客户提供服务是我们的理念。成都创新互联公司把每个网站当做一个产品来开发，精雕细琢，追求一名工匠心中的细致，我们更用心！

1.AVL树引入

(1)二叉搜索树缺点

(2)AVL树简介

  [1]问题的解决

  [2]AVL树的性质

2.AVL树的插入旋转操作

(1)术语解释

(2)左单旋

  [1]插入到右侧的左边

  [2]插入到右侧的右边

(3)右单旋

  [1]插入到左侧的左边

  [2]插入到左侧的右边

(4)左右双旋

  [1]插入到右侧的左边

  [2]插入到右侧的右边

(5)右左双旋

  [1]插入到左侧的左边

  [2]插入到左侧的右边

3.AVL树的局部实现

(1)AVL树的结点类

(2)AVL树成员变量

(3)无参构造 

(4)左单旋

(5)右单旋

(6)左右双旋

(7)右左双旋

(8)插入函数

(9)中序遍历

(10)析构函数

(11)验证函数

4.AVL树的整体实现与验证

(1)AVL树的整体实现

(2)AVL树的验证

AVL树也叫平衡二叉搜索树，它是二叉搜索树的升级版，修复了二叉树中存在的缺点，但因此也带来了更复杂的逻辑，所以本文需要搭配大量图片来理解。

  本文在win10系统的vs2019中验证。

1.AVL树引入   (1)二叉搜索树缺点

  来看这幅图，这是用二叉搜索树存储的五个元素：由于二叉搜索树的特性，导致了这棵树成为了单支树。这样二叉搜索树在中序遍历时效率就会降低，为了解决这样的缺点，又引入了AVL树。(平衡二叉搜索树)

b3830a37758d4c5c91863410dd009c30.png

(2)AVL树简介     [1]问题的解决

  AVL树是为了解决上述问题而出现。如何解决呢？

  当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1，就可以降低树的高度，从而减少平均搜索长度。

  如何使高度之差的绝对值不超过1就是AVL树的难点，需要对AVL树进行调整，才可以达到这样的状态，这也是本文的重点。

  [2]AVL树的性质

  一棵AVL树只有两个状态：

  • 空树
  • 满足下列性质的二叉搜索树
  1. 它的左右子树都是AVL树
  2. 左右子树高度之差(平衡因子)的绝对值不超过1（也就是说，平衡因子可以是1 0 -1）
2.AVL树的插入旋转操作   (1)术语解释

b5ca0cd65bd24ab293beae4ef3ec02f1.png

  较高左子树：如图，以30为根结点的树，左子树有2层，右子树只有1层，因此左子树就是较高左子树。

  较高右子树：如图，以70为根结点的树，左子树只有1层，右子树有2层，因此右子树就是较高右子树。

  较高左子树的左侧/右侧：以30为根结点的树，将新结点作为0的孩子插入。也就是将新结点插入较高左子树的左侧。

  较高右子树的左侧/右侧：以70为根结点的树，将新结点作为90的孩子插入。也就是将新结点插入到较高右子树的右侧。

 平衡因子：本文中指定用某个结点的右子树的高度减去左子树的高度的值作为平衡因子。如：30这个结点的平衡因子就是(1 - 2) == -1。90这个结点的平衡因子就是0。

  接下来讲解的旋转操作就需要用到平衡因子，本文用bf表示平衡因子。

(2)左单旋

  将新结点插入到较高右子树的右侧，分为两类：插入到右侧的左边，插入到右侧的右边。(以下几种情况同理，都会分左右两边) 此时需要左单旋。

  [1]插入到右侧的左边

692c85dd7bc6463294ab2eefc380748d.png

  如图：左右两棵子树的根结点用parent表示(注意：这里的根结点不只是整棵树的根结点，也可以是一棵子树的根结点)，右子树的根结点用subR表示，右子树的左孩子的根节点用subRL表示（很好记的，右子树的左孩子就是RrightLeft---->RL）。

  此时图一中：parent结点的平衡因子bf就是 (2 - 1) == 1，subR的平衡因子是0，subRL的平衡因子是0。(后面就不会仔细介绍图片的细节了，因为都和这个一样) 图一此时的平衡因子的绝对值都不大于1，说明符合AVL树的要求。

  图二：将75插入到了右侧的左边。AVL树的插入算法和二叉平衡树相比，就是多了各种旋转操作，因此如何寻找结点的合适位置和二叉搜索树是一样的：根结点左侧比根节点小，根节点右侧比根结点大。

  图二中插入了新结点后，就应该把树中的各个结点的平衡因子更新，更新后subR的平衡因子更新为1，parent的平衡因子更新为2。(平衡因子的更新是从下到上进行更新) 更新后parent的平衡因子的绝对值大于1，不满足AVL树，就应该进行调整。

  调整方法：首先将parent结点的右孩子指针指向subRL，然后将subR的左孩子指针指向parent。这个过程简单的就是说，儿变爹，爹变儿。

  调整后：不要忘记从修改这几个结点的平衡因子，可以发现，这个情况是将三个结点的平衡因子都变成0。

  这种调整就像是把双亲结点旋转到了孩子结点的左侧，所以叫做左单旋。

  [2]插入到右侧的右边

b7c3221ceacc416fbb6bd66847ff7b29.png

  新结点插入到较高右子树的右侧的右边。这个情况的处理方法和插入到左边的处理方式完全相同，这里就不赘述了。

(3)右单旋

  将新结点插入到较高左子树的左侧。

  [1]插入到左侧的左边

5d9501ef7e7b411d929090316313542b.png

将新结点插入到较高左子树的左侧的左边，依旧需要标结点，作为根节点的parent结点，根结点的左孩子subL结点，左孩子的右孩子subLR，同时标出它们的平衡因子。

  这种情况的解决的办法：首先让parent结点的左孩子指针指向subLR结点，然后让subL结点的右孩子指针指向parent结点，然后更新平衡因子，这种情况依旧是将这几个结点平衡因子更新为0。

  这就像是把双亲结点旋转到了孩子结点的右侧，所以叫做右单旋。

  [2]插入到左侧的右边

b2d483dadc93429694f7afb77edd1780.png

将新结点插入到较高左子树的左侧的右边，这种情况的处理方法和插入到左边的方法相同，这里也不再赘述了。

(4)左右双旋

  双旋比单旋要复杂，所以要仔细看图。

  将新结点插入到较高左子树的右侧。

  [1]插入到右侧的左边

ade2d5a0e16445318d8a92866b1280c6.png

如图二：将新结点插入到了较高左子树的右侧的左边，更新平衡因子后需要调整。此时如果按照右单旋的方式调整，调整完后依然不满足条件。(读者可以试着按右单旋画图，这样就很好理解了)

  解决办法：此时需要把以subL为根的子树进行左单旋，从而将整棵树转换成可以使用右单旋的状态，然后把以parent为根的树进行右单旋。

  具体操作：首先把以subL为根的子树进行左单旋：先让subL的右孩子指针指向subLR的左孩子，然后让subLR的左孩子指针指向subL结点，最后让parent的左孩子指针指向subLR结点。左单旋完成。

然后把以parent为根的树进行右单旋：这里就和右单旋的示意图一样了，但为了避免命名混乱，这里希望读者可以对照着右单旋的图看一下。

  注意：这里的三个结点的命名始终没有变过，这三个名字一直都对应这三个结点，这很重要，因为这里跟前面的单旋相比多了一个步骤。

  大家仔细看以下前面的单旋，到最后，单旋的三个结点的平衡因子全都更新成0。但是双旋不一样，仔细看图6，parent的平衡因子是1。

  总结：左右双旋中，如果图二的subLR的平衡因子是-1，那么图六中parent的平衡因子将被更新为1。如果图二的subLR的平衡因子是1，那么图六中subL的平衡因子将被更新为-1。(第二个是插入到右侧的右边的特点，这里提前给出)

  [2]插入到右侧的右边

745c4d8067ba4e109f5f005edf93ded4.png

如图二：将新结点插入到了较高左子树的右侧的右边，需要进行双旋来调整。解决办法和上面差不多，但这里还是要写一下，因为双旋比较复杂。

  解决办法：首先把以subL为根的子树进行左单旋：先把subL的右孩子指针指向subLR的左孩子，然后让subLR的左孩子指针指向subL结点，最后让parent的左孩子指针指向subLR结点。

然后把以parent为根的树进行右单旋，同时双旋全都需要考虑平衡因子和单旋的不同。

总结：左右双旋中，如果图二的subLR的平衡因子是-1，那么图六中parent的平衡因子将被更新为1。如果图二的subLR的平衡因子是1，那么图六中subL的平衡因子将被更新为-1。

(5)右左双旋

  将新结点插入到较高右子树的左侧。

  [1]插入到左侧的左边

489e7a2a6dcf44c9934bd1152d29dfe4.png

把新结点插入到较高右子树的左侧的左边，这种情况也是无法通过单旋解决的，需要使用双旋。

  如图二：把新结点插入到较高右子树的左侧的左边，同时更新平衡因子，发现不满足AVL树的条件。

  解决办法：把以subR为根的树进行右单旋，然后把以parent为根的树进行左单旋，然后和左右双旋一样，需要更新图六的平衡因子。

总结：左右双旋中，如果图二的subRL的平衡因子是-1，那么图六中subR的平衡因子将被更新为1。如果图二的subRL的平衡因子是1，那么图六中parent的平衡因子将被更新为-1。

  [2]插入到左侧的右边

52e5d55f04f54b38b1208921ac31bbdb.png

把新结点插入到较高右子树的左侧的右边，这种情况也是无法通过单旋解决的，需要使用双旋。

  如图二：把新结点插入到较高右子树的左侧的右边，同时更新平衡因子，发现不满足AVL树的条件。

  解决办法：把以subR为根的树进行右单旋，然后把以parent为根的树进行左单旋，然后和左右双旋一样，需要更新图六的平衡因子。

总结：左右双旋中，如果图二的subRL的平衡因子是-1，那么图六中subR的平衡因子将被更新为1。如果图二的subRL的平衡因子是1，那么图六中parent的平衡因子将被更新为-1。

3.AVL树的局部实现

  AVL树的删除操作也比较繁琐，因此本文只主要介绍插入操作。同时为了方便操作，我们规定这里实现的AVL树中的元素唯一，不存在相同的。

(1)AVL树的结点类

  AVL树就是升级版的二叉搜索树，因此和二叉搜索树一样也需要实现结点类来存储元素。因为结点中可能存储各种类型的元素，因此也是模板。

  结点中有三个指针：指向此结点左右孩子的指针，指向此结点双亲的指针。保存元素的变量，保存平衡因子的变量。

//结点类
templatestruct AVLTreeNode {
	AVLTreeNode* left;//左孩子指针
	AVLTreeNode* right;//右孩子指针
	AVLTreeNode* parent;//双亲指针
	T value;//存储元素的变量
	int bf;//平衡因子

	//用传入的值构造结点
	AVLTreeNode(const T& _value = T())
		:left(nullptr)
		,right(nullptr)
		,parent(nullptr)
		,value(_value)
		,bf(0)
	{}
};
(2)AVL树成员变量

  AVL树的成员变量只有指向根结点的指针。这里需要用typedef关键字给结点类起别名，使用会更方便。

//AVL树类
templateclass AVLTree {
	//给结点类起别名，方便使用
	typedef AVLTreeNodeNode;
private:
	//指向根结点的结点指针
	Node* root;
};
(3)无参构造 
//无参构造
//让根结点指针指向空即可
AVLTree()
	:root(nullptr)
{}
(4)左单旋

  新结点插入到较高右子树的右侧。

  根据图片讲解中的步骤进行理解。

  首先让parent的右孩子指针指向subL，然后让subR的左孩子指针指向parent，同时记得更新结点的双亲指针，最后更新平衡因子。

//左单旋
//以下过程建议搭配图片理解
void RotateLeft(Node* parent) {
	//这里的指针设计在讲解旋转的时候已经解释过
	Node* subR = parent->right;
	Node* subRL = subR->left;

	//用pparent(祖父结点)来保存parent结点的双亲
	//因为parent并不一定是整棵树的根，还有可能只是一棵子树的根
	Node* pparent = parent->parent;

	//第一步：首先让双亲的右孩子指针指向subRL
	parent->right = subRL;

	//之所以要判断是因为subRL结点可能不存在
	if (subRL)
		//更新双亲
		subRL->parent = parent;

	//第二步：让subR的左孩子指针指向parent
	subR->left = parent;

	//不要忘记给这些结点更新它们的双亲
	parent->parent = subR;
	subR->parent = pparent;

	//祖父结点是空，说明parent结点是整棵树的根结点
	if (pparent == nullptr) {
		root = subR;
	}
	//说明parent是子树的根结点
	else {
		//原本祖父结点的孩子是parent
		//经过旋转他的孩子变成了subR
		//需要判断parent是祖父结点的左孩子还是右孩子，然后让对应指针指向subR结点
		if (pparent->left == parent) {
			pparent->left = subR;
		}
		else {
			pparent->right = subR;
		}
	}
	//更新平衡因子
	parent->bf = subR->bf = 0;
}
(5)右单旋

  新结点插入到较高左子树的左侧。

  与左单旋相似，也是两步走，然后更新双亲指针和平衡因子。

//右单旋
void RotateRight(Node* parent) {
	Node* subL = parent->left;
	Node* subLR = subL->right;

	//祖父结点
	Node* pparent = parent->parent;

	//第一步：让parent的左孩子指针指向subLR
	parent->left = subLR;
	//之所以要判断是因为subLR结点可能不存在
	if (subLR)
		subLR->parent = parent;
	//第二步：让subL的右孩子指针指向parent
	subL->right = parent;

	//更新双亲结点
	parent->parent = subL;
	subL->parent = pparent;

	//祖父结点是空，说明parent是整棵树的根结点
	if (pparent == nullptr) {
		root = subL;
	}
	//parent是子树的根结点
	else {
		//这里和左单旋一样
		if (pparent->left == parent) {
			pparent->left = subL;
		}
		else {
			pparent->right = subL;
		}
	}
	//更新平衡因子
	parent->bf = subL->bf = 0;
}
(6)左右双旋

  新结点插入到较高左子树的右侧。

  首先保存初始状态的subLR的平衡因子，后面根据它来更新其他结点的平衡因子。然后对以subL为根的树进行左单旋，对以parent为根的树进行右单旋。

  最后根据保存的subLR结点的平衡因子进行更新，如果BF是-1，就把parent的平衡因子更新为1，否则把subL的平衡因子更新为-1。(这里很重要，一定要跟图片结合看)

//左右双旋
void RotateLR(Node* parent) {
	Node* subL = parent->left;
	Node* subLR = subL->right;
	//保存subLR的平衡因子，后面需要根据它来更新别的平衡因子
	int BF = subLR->bf;

	//对以subL为根结点的树进行左单旋
	RotateLeft(subL);
	//对以parent为根结点的树进行右单旋
	RotateRight(parent);

	//根据保存的平衡因子更新
	//当subLR平衡因子为-1，将parent的平衡因子更新为1
	if (BF == -1)
		parent->bf = 1;
	//当subLR平衡因子不是-1，将subL的平衡因子更新为-1
	else
		subL->bf = -1;
}
(7)右左双旋

  新结点插入到较高右子树的左侧。

  首先保存初始状态的subRL的平衡因子，后面根据它来更新其他结点的平衡因子。然后对以subR为根的树进行右单旋，对以parent为根的树进行左单旋。

  最后根据保存的subRL结点的平衡因子进行更新，如果BF是-1，就把subR的平衡因子更新为1，否则把parent的平衡因子更新为-1。(跟左右双旋一样，一定要跟图片结合看)

//右左双旋
void RotateRL(Node* parent) {
	Node* subR = parent->right;
	Node* subRL = subR->left;
	//保存subRL的平衡因子，后面根据它更新其他结点平衡因子
	int BF = subRL->bf;

	//对以subR为根的树进行右单旋
	RotateRight(subR);
	//对以parent为根的树进行左单旋
	RotateLeft(parent);

	//根据保存的subRL平衡因子的不同来进行不同的更新。
	if (BF == -1)
		subR->bf = 1;
	else
		parent->bf = -1;
}
(8)插入函数

  插入函数首先为元素找合适的位置，同时判断是否已经有相同元素了。成功插入后，需要更新平衡因子，然后对平衡因子进行检测，不符合AVL树性质的，需要根据情况进行单旋或双旋。

  如果进行了单旋，那么就需要继续往上检测平衡因子，因为单旋之后可能会影响上层的平衡因子。但进行双旋后，就可以直接返回了，因为双旋后已经处理好了。

//插入函数
bool Insert(const T& _value) {
	//树为空，将新结点作为根结点即可
	if (root == nullptr) {
		root = new Node(_value);
		return true;
	}

	//树非空
	Node* cur = root;
	//用来保存cur的双亲结点
	Node* parent = nullptr;

	//为新结点的插入寻找合适的位置
	//同时判断是否树中有相同结点
	while (cur) {
		parent = cur;
		if (_value< cur->value) {
			cur = cur->left;
		}
		else if (_value >cur->value) {
			cur = cur->right;
		}
		else {
			return false;
		}
	}

	//构造新结点
	cur = new Node(_value);
	//判断是新结点应该插在双亲的左边还是右边
	if (_value< parent->value) {
		parent->left = cur;
	}
	else {
		parent->right = cur;
	}
	//更新新结点的双亲
	cur->parent = parent;

	//更新平衡因子
	//从下往上
	while (parent) {
		//cur是双亲左孩子
		//左子树高度变高，平衡因子就减1
		//平衡因子：右子树高度减左子树高度
		if (cur == parent->left) {
			parent->bf--;
		}
		//右子树变高，平衡因子加1
		else {
			parent->bf++;
		}

		//判断更新后的平衡因子是否满足AVL树
		//证明parent之前只有一个孩子，而新结点插到另一个空着的位置了
		if (parent->bf == 0) {
			break;
		}
		//证明parent之前没有孩子，新结点插入后只有一个孩子
		else if (-1 == parent->bf || 1 == parent->bf) {
			cur = parent;
			parent = cur->parent;
		}
		//如下就是parent的平衡因子变成2或-2了
		//需要根据图片进行理解
		else {
			//说明parent的右子树高
			if (parent->bf == 2) {
				//根据cur的平衡因子判断是左单旋还是右左双旋
				if (cur->bf == 1)
					RotateLeft(parent);
				else
					RotateRL(parent);
			}
			//parent左子树高
			else {
				if (cur->bf == -1)
					RotateRight(parent);
				else
					RotateLR(parent);
			}

			//使用双旋调整后就不需要向上继续调整了，可以直接退出循环
			break;
		}
	}
	return true;
}
(9)中序遍历

  根据中序遍历规则：左、根、右。进行遍历即可。

//中序遍历
void InOrder() {
	cout<< "中序遍历：";
	InOrder(root);
	cout<< endl;
}

//中序遍历内部实现
void InOrder(Node* root) {
	if (root) {
		//首先递归遍历左子树，然后打印根结点，最后递归遍历右子树
		InOrder(root->left);
		cout<< root->value<< " ";
		InOrder(root->right);
	}
}
(10)析构函数

  析构函数没有参数，所以需要单独实现一个销毁函数。先递归删除左右子树，最后删除根结点。

//析构函数
//因为析构函数无参数，需要单独定义销毁函数
~AVLTree() {
	Destroy(root);
}

//销毁函数(和二叉搜索树一模一样)
void Destroy(Node*& root) {
	if (root) {
		//递归销毁根的左子树和右子树然后删除根结点
		Destroy(root->left);
		Destroy(root->right);
		delete root;
		root = nullptr;
	}
}
(11)验证函数

  验证函数通过高度函数获得左右子树的高度，进而计算出高度差，同时将高度差的绝对值和高度差与平衡因子的比较结合在一起判断这棵树是否满足AVL树的性质。

//验证函数
bool IsAVLTree() {
	return IsAVLTree(root);
}

//验证函数主体实现
bool IsAVLTree(Node* root) {
	if (root == nullptr) {
		return true;
	}
	//计算根结点左右子树高度
	int leftHeight = Height(root->left);
	int rightHeight = Height(root->right);

	//根据平衡因子绝对值 和 子树高度差与根结点平衡因子是否相等
	//判断是否满足AVL树性质
	if (abs(rightHeight - leftHeight) >1 || rightHeight - leftHeight != root->bf) {
		cout<< "结点值："<< root->value<< "  结点平衡因子："<< root->bf<< endl;
		return false;
	}

	//递归调用
	return IsAVLTree(root->left) && IsAVLTree(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);
}
4.AVL树的整体实现与验证   (1)AVL树的整体实现
#include "iostream"
using namespace std;

//结点类
templatestruct AVLTreeNode {
	AVLTreeNode* left;//左孩子指针
	AVLTreeNode* right;//右孩子指针
	AVLTreeNode* parent;//双亲指针
	T value;//存储元素的变量
	int bf;//平衡因子

	//用传入的值构造结点
	AVLTreeNode(const T& _value = T())
		:left(nullptr)
		,right(nullptr)
		,parent(nullptr)
		,value(_value)
		,bf(0)
	{}
};


//AVL树类
templateclass AVLTree {
	//给结点类起别名，方便使用
	typedef AVLTreeNodeNode;
private:
	//指向根结点的结点指针
	Node* root;
public:
	//无参构造
	//让根结点指针指向空即可
	AVLTree()
		:root(nullptr)
	{}

	//析构函数
	//因为析构函数无参数，需要单独定义销毁函数
	~AVLTree() {
		Destroy(root);
	}

	//销毁函数(和二叉搜索树一模一样)
	void Destroy(Node*& root) {
		if (root) {
			//递归销毁根的左子树和右子树然后删除根结点
			Destroy(root->left);
			Destroy(root->right);
			delete root;
			root = nullptr;
		}
	}

	//左单旋
	//以下过程建议搭配图片理解
	void RotateLeft(Node* parent) {
		//这里的指针设计在讲解旋转的时候已经解释过
		Node* subR = parent->right;
		Node* subRL = subR->left;

		//用pparent(祖父结点)来保存parent结点的双亲
		//因为parent并不一定是整棵树的根，还有可能只是一棵子树的根
		Node* pparent = parent->parent;

		//第一步：首先让双亲的右孩子指针指向subRL
		parent->right = subRL;

		//之所以要判断是因为subRL结点可能不存在
		if (subRL)
			//更新双亲
			subRL->parent = parent;

		//第二步：让subR的左孩子指针指向parent
		subR->left = parent;

		//不要忘记给这些结点更新它们的双亲
		parent->parent = subR;
		subR->parent = pparent;

		//祖父结点是空，说明parent结点是整棵树的根结点
		if (pparent == nullptr) {
			root = subR;
		}
		//说明parent是子树的根结点
		else {
			//原本祖父结点的孩子是parent
			//经过旋转他的孩子变成了subR
			//需要判断parent是祖父结点的左孩子还是右孩子，然后让对应指针指向subR结点
			if (pparent->left == parent) {
				pparent->left = subR;
			}
			else {
				pparent->right = subR;
			}
		}
		//更新平衡因子
		parent->bf = subR->bf = 0;
	}

	//右单旋
	void RotateRight(Node* parent) {
		Node* subL = parent->left;
		Node* subLR = subL->right;

		//祖父结点
		Node* pparent = parent->parent;

		//第一步：让parent的左孩子指针指向subLR
		parent->left = subLR;
		//之所以要判断是因为subLR结点可能不存在
		if (subLR)
			subLR->parent = parent;
		//第二步：让subL的右孩子指针指向parent
		subL->right = parent;

		//更新双亲结点
		parent->parent = subL;
		subL->parent = pparent;

		//祖父结点是空，说明parent是整棵树的根结点
		if (pparent == nullptr) {
			root = subL;
		}
		//parent是子树的根结点
		else {
			//这里和左单旋一样
			if (pparent->left == parent) {
				pparent->left = subL;
			}
			else {
				pparent->right = subL;
			}
		}
		//更新平衡因子
		parent->bf = subL->bf = 0;
	}

	//左右双旋
	void RotateLR(Node* parent) {
		Node* subL = parent->left;
		Node* subLR = subL->right;
		//保存subLR的平衡因子，后面需要根据它来更新别的平衡因子
		int BF = subLR->bf;

		//对以subL为根结点的树进行左单旋
		RotateLeft(subL);
		//对以parent为根结点的树进行右单旋
		RotateRight(parent);

		//根据保存的平衡因子更新
		//当subLR平衡因子为-1，将parent的平衡因子更新为1
		if (BF == -1)
			parent->bf = 1;
		//当subLR平衡因子不是-1，将subL的平衡因子更新为-1
		else
			subL->bf = -1;
	}

	//右左双旋
	void RotateRL(Node* parent) {
		Node* subR = parent->right;
		Node* subRL = subR->left;
		//保存subRL的平衡因子，后面根据它更新其他结点平衡因子
		int BF = subRL->bf;

		//对以subR为根的树进行右单旋
		RotateRight(subR);
		//对以parent为根的树进行左单旋
		RotateLeft(parent);

		//根据保存的subRL平衡因子的不同来进行不同的更新。
		if (BF == -1)
			subR->bf = 1;
		else
			parent->bf = -1;
	}

	//插入函数
	bool Insert(const T& _value) {
		//树为空，将新结点作为根结点即可
		if (root == nullptr) {
			root = new Node(_value);
			return true;
		}

		//树非空
		Node* cur = root;
		//用来保存cur的双亲结点
		Node* parent = nullptr;

		//为新结点的插入寻找合适的位置
		//同时判断是否树中有相同结点
		while (cur) {
			parent = cur;
			if (_value< cur->value) {
				cur = cur->left;
			}
			else if (_value >cur->value) {
				cur = cur->right;
			}
			else {
				return false;
			}
		}

		//构造新结点
		cur = new Node(_value);
		//判断是新结点应该插在双亲的左边还是右边
		if (_value< parent->value) {
			parent->left = cur;
		}
		else {
			parent->right = cur;
		}
		//更新新结点的双亲
		cur->parent = parent;

		//更新平衡因子
		//从下往上
		while (parent) {
			//cur是双亲左孩子
			//左子树高度变高，平衡因子就减1
			//平衡因子：右子树高度减左子树高度
			if (cur == parent->left) {
				parent->bf--;
			}
			//右子树变高，平衡因子加1
			else {
				parent->bf++;
			}

			//判断更新后的平衡因子是否满足AVL树
			//证明parent之前只有一个孩子，而新结点插到另一个空着的位置了
			if (parent->bf == 0) {
				break;
			}
			//证明parent之前没有孩子，新结点插入后只有一个孩子
			else if (-1 == parent->bf || 1 == parent->bf) {
				cur = parent;
				parent = cur->parent;
			}
			//如下就是parent的平衡因子变成2或-2了
			//需要根据图片进行理解
			else {
				//说明parent的右子树高
				if (parent->bf == 2) {
					//根据cur的平衡因子判断是左单旋还是右左双旋
					if (cur->bf == 1)
						RotateLeft(parent);
					else
						RotateRL(parent);
				}
				//parent左子树高
				else {
					if (cur->bf == -1)
						RotateRight(parent);
					else
						RotateLR(parent);
				}

				//使用双旋调整后就不需要向上继续调整了，可以直接退出循环
				break;
			}
		}
		return true;
	}


	//中序遍历
	void InOrder() {
		cout<< "中序遍历：";
		InOrder(root);
		cout<< endl;
	}

	//中序遍历内部实现
	void InOrder(Node* root) {
		if (root) {
			//首先递归遍历左子树，然后打印根结点，最后递归遍历右子树
			InOrder(root->left);
			cout<< root->value<< " ";
			InOrder(root->right);
		}
	}
	


	//验证函数
	bool IsAVLTree() {
		return IsAVLTree(root);
	}

	//验证函数主体实现
	bool IsAVLTree(Node* root) {
		if (root == nullptr) {
			return true;
		}
		//计算根结点左右子树高度
		int leftHeight = Height(root->left);
		int rightHeight = Height(root->right);

		//根据平衡因子绝对值 和 子树高度差与根结点平衡因子是否相等
		//判断是否满足AVL树性质
		if (abs(rightHeight - leftHeight) >1 || rightHeight - leftHeight != root->bf) {
			cout<< "结点值："<< root->value<< "  结点平衡因子："<< root->bf<< endl;
			return false;
		}

		//递归调用
		return IsAVLTree(root->left) && IsAVLTree(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 main() {

	int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	AVLTreeavl;

	for (int i = 0; i< 10; i++) {
		avl.Insert(arr[i]);
		avl.InOrder();
	}

	if (avl.IsAVLTree()) {
		cout<< "是AVL树"<< endl;
	}
	else {
		cout<< "不是AVL树"<< endl;
	}
}
(2)AVL树的验证

  上文代码的运行结果如下：符合AVL树的性质。同时中序遍历也是一个升序的序列。

8e108958b3cc4d60976f6a01e0dbad19.png

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


分享名称：数据结构(C++):AVL树实现篇-创新互联
分享链接：http://pwwzsj.com/article/icidg.html

其他资讯