数据结构高阶–AVL（平衡二叉树）（图解+实现）

AVL树（平衡二叉树）

概念

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

• 它的左右子树都是AVL树
• 左右子树高度之差的绝对值（也叫平衡因子）不超过1
• 我规定：平衡因子（balance factor）= 右子树高度 - 左子树高度（后面这样实现）

AVL树节点定义以及框架

template <class K,class V> struct AVL_Node { 	//三叉链 	AVL_Node<K, V>* left; 	AVL_Node<K, V>* right; 	AVL_Node<K, V>* parent;//用来定位父节点 	K key; 	V value; 	int bf;//平衡因子 = 右子树 - 左子树 	AVL_Node(const K& key, const V& value):left(nullptr),right(nullptr),parent(nullptr), key(key), value(value),bf(0) 	{} }; template <class K, class V> class AVL_Tree { 	typedef AVL_Node<K,V> Node; public: public: 	Node* root = nullptr; }; 

AVL树的插入

方法概述

第一步： 我们先按照二叉搜索树树插入节点的方式，插入节点（这一步很简单，上一篇博客介绍过）
第二步： 更新平衡因子，更新平衡因子的过程是一个难点，下面我给大家分析一下整个过程

平衡因子的调节

实际上，我们应该能够发现，插入一个节点后，它之后影响它祖先的平衡因子（可能是所有祖先，也可能是一部分祖先），下面就是一个分析过程：

第一步： 判断父亲节点是否存在，不存在直接结束，如果存在，且插入节点是它的左孩子，那么父亲节点的平衡因子就减1，如果是父亲的右孩子，父亲的平衡因子就加1。然后对父亲节点的平衡因子进行检索。
第二步： 继续对父亲节点的平衡因子进行检索，平衡因子会有以下三种情况

• 第一种情况：此时父亲的平衡因子为0，则说明插入前父亲的平衡因子为1或-1，缺少左节点或右节点插入后，插入的节点已经补齐了左节点或右节点，整体高度不变，对上层无影响，不需要继续调节。下面是一个演示图：

• 第二种情况：此时父亲节点的平衡因子为-1或1，则说明插入前父亲的平衡因子为0，插入后增加了一个左节点或右节点，整体高度增加1，对上层有影响，继续迭代更新祖先的平衡因子。下面是一个演示图：

• 第三种情况：此时父亲节点的平衡因子为-2或2，则说明插入前父亲的平衡因子为-1或1，多了一个左节点或一个右节点，插入后增加了一个左节点或右节点，此时多了两个左节点和右节点，这棵子树一边已经被拉高了，此时这棵子树不平衡了，需要旋转处理。下面是一个演示图：

旋转处理（出现了不平衡子树）

一般来说，第一个发生不平衡的节点，我们记作parent，它的孩子分别记作subL(左子树)和subR（右子树）

分四种情况讨论：

• 左单旋（新插入的节点在右子树的右侧）

​ 具体步骤： 让subR的左孩子成为parent的右孩子，然后让parent成为subR的左孩子，最后把两个节点的平衡因子修改为0。
先画一个具像图给大家演示如何进行这个操作（下面是一部分失衡的子树）

抽象图：

代码实现如下

/* 		注意：一般选取第一个不平衡的节点作为parent 	*/ 	//左单旋，新插入的节点在右子树的右侧 	/* 		步骤： 		    1.让subR的左孩子成为parent的右孩子 			2.然后让parent成为subR的左孩子 			3.最后把两个节点的平衡因子修改为0 	*/ 	void RotateL(Node* parent) 	{ 		Node* subR = parent->right; 		Node* subRL = subR->left; 		//1.先把subR左边（可能为空也可能不为空）作为parent的右边 		parent->right = subRL; 		//2.如果subRL不为空，那么就让subRL的父指针指向parent 		if (subRL) 		{ 			subRL->parent = parent; 		} 		//3.先记录parent的父节点的位置，然后把parent作为subR的左边 		Node* ppNode = parent->parent; 		subR->left = parent; 		//4.parent的父指针指向subR 		parent->parent = subR; 		//5.如果ppNode为空-->说明subR现在是根节点，就让subR的父指针指向nullptr 		//如果不是根节点就把subR的父指针指向parent的父节点，parent的父节点（左或右）指向subR 		if (ppNode == nullptr) 		{ 			//更新根节点 			root = subR; 			subR->parent = nullptr; 		} 		else 		{ 			//判断parent是ppNode的左还是右 			if (ppNode->left == parent) 			{ 				ppNode->left = subR; 			} 			else 			{ 				ppNode->right = subR; 			} 			subR->parent = ppNode; 		} 		//6.把parent和subR的平衡因子更新为0 		subR->bf = parent->bf = 0; 	} 

• 右单旋（新节点插入到左子树的左侧）

​ 具体步骤： 让subL的右孩子成为parent的左孩子，然后让parent成为subL的右孩子，最后把两个节点的平衡因子修改为0

先画一个具像图给大家演示如何进行这个操作（下面是一部分失衡的子树）：

抽象图：

代码实现如下：

//右单旋，新插入的节点在左子树的左侧 	/* 		步骤： 			1.让subL的右孩子成为parent的左孩子 			2.然后让parent成为subL的右孩子 			3.最后把两个节点的平衡因子修改为0 	*/ 	void RotateR(Node* parent) 	{ 		Node* subL = parent->left; 		Node* subLR = subL->right; 		//1.先把subL的右边（可能为空也可能不为空）作为parent的左边 		parent->left = subLR; 		//2.如果subLR不为空，就把subLR的父指针指向parent 		if (subLR) 		{ 			subLR->parent = parent; 		} 		//3.记录parent的父节点的位置，然后把parent作为subL的右边 		Node* ppNode = parent->parent; 		subL->right = parent; 		//4.parent的父亲指针指向subL 		parent->parent = subL; 		//5.如果ppNode为空-->说明subL现在是根节点，就让subL的父节点指向nullptr 		//不是根节点就把subL的父节点指向parent的父节点，parent的父节点（左或右）指向subL 		if (ppNode == nullptr) 		{ 			//更新根节点 			root = subL; 			subL->parent = nullptr; 		} 		else 		{ 			//判断parent是ppNode的左还是右 			if (ppNode->left == parent) 			{ 				ppNode->left = subL; 			} 			else 			{ 				ppNode->right = subL; 			} 			subL->parent = ppNode; 		} 		//6.把parent和subL的平衡因子更新为0 		subL->bf = parent->bf = 0; 	} 

• 右左双旋（新节点插入在较高右子树左侧，这里和第一种情况的区别就是前者是直线，后者是折线）

​ 具体步骤 先对subR进行一个右单旋，然后对parent进行左单旋，修改平衡因子，有三种改法。三个节点从左至右的三个节点依次是：parent、subRL和subR。
​ 如果subRL的平衡因子为0，就将它们依次改为0，0, 0；
​ 如果subRL的平衡因子为1，就将它们依次改为-1，0, 0；
​ 如果subRL的平衡因子为-1，就将它们依次改为0，0, 1。
先画一个具像图给大家演示如何进行这个操作（下面是一部分失衡的子树）

抽象图（两种情况）：

subRL的bf为1

subRL的bf为-1

**代码实现如下：**

//右左双旋，新插入的节点在右子树的左侧 	/* 		步骤： 			1.先对subR进行一个右单旋 			2在对parent进行一个左单旋然后修改平衡因子 	*/ 	void RotateRL(Node* parent) 	{ 		Node* subR = parent->right; 		Node* subRL = subR->left; 		int bf = subRL->bf;//保留subRL的平衡因子的值，方便直到新插入的节点是在subRL左子树还是右子树  		//旋转 先对subR进行右旋转，再对parent进行左旋转 		RotateR(subR); 		RotateL(parent);  		// 从左到右 parent subRL subR 		if (bf == -1)// subRL的左子树  bf: 0 0 1 		{ 			parent->bf = 0; 			subRL->bf = 0; 			subR->bf = 1; 		} 		else if (bf == 1)// subRL的右子树 bf: -1 0 0 		{ 			parent->bf = -1; 			subRL->bf = 0; 			subR->bf = 0; 		} 		else if (bf == 0) 		{ 			parent->bf = 0; 			subRL->bf = 0; 			subR->bf = 0; 		} 	} 

• 左右双旋（新节点插入在较高右子树左侧，这里和第一种情况的区别就是前者是直线，后者是折线）

​ 具体步骤先对subL进行一个左单旋，然后对parent进行右单旋，修改平衡因子，有三种改法。三个节点从左至右的三个节点一次是：subL、subLR和parent。（和上面的类似，这样有助于我们记住平衡因子的调整，同时我们也可以画简图理解记忆）
​ 如果subLR的平衡因子为0，就将它们依次改为0，0, 0；
​ 如果subLR的平衡因子为1，就将它们依次改为-1，0, 0；
​ 如果subLR的平衡因子为-1，就将它们依次改为0，0, 1。
先画一个具像图给大家演示如何进行这个操作（下面是一部分失衡的子树）

抽象图（两种情况）：

subLR的bf为-1

subLR的bf为1

代码实现如下：

//左右双旋，新插入的节点在左子树的右侧 	/* 		步骤： 			1.先对subR进行一个左单旋 			2.在对parent进行一个右单旋然后修改平衡因子 	*/ 	void RotateLR(Node* parent) 	{ 		Node* subL = parent->left; 		Node* subLR = subL->right; 		int bf = subLR->bf;//保留subLR的平衡因子的值，方便直到新插入的节点是在subLR左子树还是右子树  		//旋转先对subL进行左旋转，再对parent进行右旋转 		RotateL(subL); 		RotateR(parent);  		//从左到右 subL subLR parent 		if (bf == -1)// subLR的左子树  bf: 0 0 1 		{ 			subL->bf = 0; 			subLR->bf = 0; 			parent->bf = 1; 		} 		else if (bf == 1)// subLR的右子树 bf: -1 0 0 		{ 			subL->bf = -1; 			subLR->bf = 0; 			parent->bf = 0; 		} 		else if (bf == 0) 		{ 			subL->bf = 0; 			subLR->bf = 0; 			parent->bf = 0; 		} 	} 

插入代码的实现

//二叉树的插入 	bool Insert(const K& key, const V& value) 	{ 		//先按照二叉搜索树一样插入元素 		 		//无节点插入 		if (root == nullptr) 		{ 			root = new Node(key,value); 			return true; 		} 		//有节点时插入 		Node* parent = nullptr; 		Node* cur = root; 		while (cur) 		{ 			parent = cur; 			//小于往左走 			if (key < cur->key) 			{ 				cur = cur->left; 			} 			//大于往右走 			else if (key > cur->key) 			{ 				cur = cur->right; 			} 			else 			{ 				//找到了，就返回false 				return false; 			} 		} 		cur = new Node(key,value); 		// 判断cur应该插在parent的左还是右  		// 小于在左，大于在右		 		if (cur->key < parent->key) 		{ 			parent->left = cur; 			cur->parent = parent; 		} 		else 		{ 			parent->right = cur; 			cur->parent = parent; 		} 		// 更新parent的平衡因子  		// 节点的插入只会影响cur的祖先的平衡因子（不是所有的，是一部分，分情况） 		while (parent) 		{ 			// 更新parent的平衡因子 			// cur在parent的左，parent->bf-- 			// cur在parent的右，parent->bf++ 			if (cur == parent->left) 				parent->bf--; 			else 				parent->bf++; 			// bf 可能为 -2、-1、0、1、2 			// 如果平衡因子为0，说明更新之前，parent的bf为-1或1，现在补齐了左节点或右节点，bf==0，对上层无影响 			// 如果平衡因子为-1或1，说明更新之前，parent的bf为0，现在增加了一个左节点或有节点，bf==-1 || bf==1,对上层有影响 			// 如果平衡因子为-2或2，说明更新之前，parent的bf为-1或1，现在往左（右）节点补了左（右）节点，也就是一边 			// 拉高了，树不平衡了，需要用左旋转或右旋转来进行调整 			if (parent->bf == 0) 			{ 				//对上层没有影响，退出 				break; 			} 			else if(parent->bf == -1 || parent->bf == 1) 			{ 				// 对上层有影响，迭代更新 				cur = parent; 				parent = parent->parent; 			} 			else 			{ 				// 平衡树出现了问题，需要调整 				// 1.右边高，左旋转调整 				if (parent->bf == 2) 				{ 					// 如果是一条直线==>左旋转即可 					// 如果是一条折线==>右左旋转 					if (cur->bf == 1) 						RotateL(parent); 					else if (cur->bf == -1) 						RotateRL(parent); 				} 				// 2.左边高，右旋转调整 				else if (parent->bf == -2) 				{ 					// 如果是一条直线==>右旋转即可 					// 如果是一条折线==>左右旋转 					if (cur->bf == -1) 						RotateR(parent); 					else if (cur->bf == 1) 						RotateLR(parent); 				} 				// 调整后是平衡树，bf为0，不需要调整了 				break; 			} 		} 		return true; 	} 

AVL树的删除

方法概述

第一步： 我们先按照二叉搜索树树删除节点的方式，删除节点（这一步很简单，上一篇博客介绍过）
第二步： 然后根据对应删除情况更新平衡因子，这里更新平衡因子的方法与插入的更新方法是相反的，下面我给大家分析一下整个过程

平衡因子调节

原则：旋转的方向取决于是结点parent的哪一棵子树被缩短。且把第一个不平衡的节点设为parent节点。

删除节点后，如果删除的节点为根节点，就结束。否则根据删除节点为父节点的左右调整父节点的平衡因子。如果删除节点是父节点的左孩子，那么父亲节点的平衡因子加1，否则减1。然后对父亲节点进行检索。

有以下几种情况：

第一种情况：此时父亲的平衡因子为0，则说明删除前父亲的平衡因子为1或-1，多出一个左节点或右节点，删除节点后，左右高度相等，整体高度减1，对上层有影响，需要继续调节。下面是一个演示图：（如果此时3为根节点，那么也可以结束）

第二种情况：此时父亲的平衡因子为-1或1，则说明删除前父亲的平衡因子为0，左右高度相等，删除节点后，少了一个左节点或右节点，但是整体高度不变，对上层无影响，不需要继续调节。下面是一个演示图：

第三种情况： 此时父亲节点的平衡因子为-2或2，则说明删除前父亲的平衡因子为-1或1，多了一个左节点或一个右节点，删除了一个右节点或左节点，此时多了两个左节点或右节点，这棵子树一边已经被拉高了，此时这棵子树不平衡了，需要旋转处理。下面是一个演示图：

旋转处理

这里我只分析右边高的情况，左边高和它对称的，操作是相同的。

情况一：若还未删除的时候，parent的平衡因子和subR的平衡因子相同，则执行一个单旋转来恢复平衡
操作方法： 对parent进行左旋转，因为subR的平衡因子为0，需要继续检索，然后继续迭代，把cur迭代sub的位置，parent到cur的父亲的位置

抽象图：

情况二：若还未删除的时候，subR的平衡因子为0，那么执行一个单旋转来恢复parent的平衡
操作方法： 对parent进行左旋，然后修改平衡因子，把subR的平衡因子改为-1，parent的平衡因子改为1，因为subR的平衡因子为-1，所以无需迭代，直接结束

抽象图：

情况三：若还未删除的时候，parent和subR的平衡因子相反，那么就执行一个双旋转来恢复平衡，先围绕subR旋转，再围绕parent旋转
操作方法： 对subR进行右旋，然后对parent进行左旋，此时subR的平衡因子为0，需迭代

抽象图：（三种情况）对应上面的右左双旋

如果subRL的平衡因子为0，就将它们依次改为0，0, 0；
如果subRL的平衡因子为1，就将它们依次改为-1，0, 0；
如果subRL的平衡因子为-1，就将它们依次改为0，0, 1。

值得注意的是，这三种情况最后的平衡树subRL均为0，对应这我们讲的第一种情况，subRL为0，说明它只有一个左子树或只有一个右子树，被删除了，那么高度必然发生变化，一旦高度发生变化，就必须向上迭代调整上面的节点的平衡因子，将其调整成-1或者1的时候，彻底平衡，不需要再继续调整，因为父亲节点是-1或者1，说明删除前它的左右子树均存在，那么删除其中一棵树不会影响树的高度，所以依旧不会对上面的节点的平衡因子产生影响，所以只有当调整后subRL的节点是-1和1的时候，才是真正平衡的时候

删除代码的实现

//二叉搜索树的删除 	bool Erase(const K& key) 	{ 		//树为空，删除失败 		if (root == nullptr) 		{ 			return false; 		} 		//parent始终是cur的父亲节点 		//cur就是要找的删除的当前节点 		Node* parent = nullptr; 		Node* cur = root; 		while (cur) 		{ 			//小于往左边走 			if (key < cur->key) 			{ 				parent = cur; 				cur = cur->left; 			} 			//大于往右走 			else if (key > cur->key) 			{ 				parent = cur; 				cur = cur->right; 			} 			else 			{ 				// 找到了，开始删除 				// 1.左右子树都为空，直接删除，可以归类为左为空 				// 2.左右子树只有一边为空，左为空，父亲指向我的右，右为空，父亲指向我的左   				// 3.左右子树都不为空，取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除  				//当前情况是情景三，删除的节点它的左为空，右未知 				if (cur->left == nullptr) 				{ 					// 要删除节点为根节点时，直接把右子树的根节点赋值给——root 					// 根节点的话会导致parent为nullptr 					if (root == cur) 					{ 						root = root->right; 						delete cur; 						break; 					} 					else 					{ 						//左为空，父亲指向我的右 						//判断cur在父亲的左还是右 						if (parent->left == cur) 						{ 							parent->left = cur->right; 							//左子树少了一个节点 ++ 							parent->bf++; 						} 						else 						{ 							parent->right = cur->right; 							//右子树少了一个节点 -- 							parent->bf--; 						} 					} 					if (parent->bf != -1 && parent->bf != 1) 					{ 						AfterEraseUpdateBf(parent); 					} 					delete cur; 				} 				//当前情况是情景二，删除节点它的右为空，左未知 				else if (cur->right == nullptr) 				{ 					if (root == cur) 					{ 						root = root->left; 						delete cur; 						break; 					} 					else 					{ 						//右为空，父亲指向我的左 						//判断cur在父亲的左还是右 						if (parent->left == cur) 						{ 							parent->left = cur->left; 							parent->bf++; 						} 						else 						{ 							parent->right = cur->left; 							parent->bf--; 						} 					} 					if (parent->bf != -1 && parent->bf != 1) 					{ 						AfterEraseUpdateBf(parent); 					} 					delete cur; 				} 				//只剩下情景四 				else 				{ 					//找右子树中最小的节点，当前cur就是要删除的节点 					Node* rightMinParent = cur; 					Node* rightMin = cur->right;//去右子树找最小的节点 					while (rightMin->left) 					{ 						rightMinParent = rightMin; 						rightMin = rightMin->left;//一直往左走，找右子树最小的节点 					} 					//替代删除 					cur->key = rightMin->key; 					//转化成了情景三，左孩子为空 					if (rightMinParent->left == rightMin) 					{ 						rightMinParent->left = rightMin->right; 						rightMinParent->bf++; 					} 					else 					{ 						rightMinParent->right = rightMin->right; 						rightMinParent->bf--; 					} 					if (rightMinParent->bf != -1 && rightMinParent->bf != 1) 					{ 						AfterEraseUpdateBf(rightMinParent); 					}		 					delete rightMin; 				} 				return true; 			} 		} 		return false; 	} 	void AfterEraseUpdateBf(Node* parent) 	{ 		if (parent == nullptr) 		{ 			return; 		} 		Node* cur = parent; 		goto first; 		while (parent) 		{ 			// 更新parent的平衡因子 			// cur在parent的左，parent->_bf++ 			// cur在parent的右，parent->_bf-- 			if (cur == parent->left) 				parent->bf++; 			else 				parent->bf--; 			// bf 可能为 -2、-1、0、1、2 			// 如果平衡因子为0，说明更新之前，parent的bf为-1或1，现在删掉了左节点或右节点，整体高度变了，对上层有影响 			// 如果平衡因子为-1或1，说明更新之前，parent的bf为0，现在删掉了一个左节点或有节点，整体高度不变，对上层无影响 			// 如果平衡因子为-2或2，说明更新之前，parent的bf为-1或1，现在往左（右）节点补了左（右）节点，也就另一边 			// 拉高了，树不平衡了，需要用左旋转或右旋转来进行调整 		first: 			//此时是博客中介绍的第一种情况 			if (parent->bf == 0) 			{ 				//对上层有影响，迭代更新 				//如果parent是根节点就结束 				if (parent->parent == nullptr) 				{ 					break; 				} 				cur = parent; 				parent = parent->parent; 			} 			//此时是博客中介绍的第二种情况 			else if (parent->bf == -1 || parent->bf == 1) 			{ 				//对上层无影响，退出 				break; 			} 			//只剩下第三种情况 			else 			{ 				//平衡树出现了问题，需要调整 				//1.右边高，左旋转调整 				if (parent->bf == 2) 				{ 					//此时是第三种情况的情景1 					/* 						对parent进行左旋转，迭代 					*/ 					if (parent->right->bf == 1) 					{ 						RotateL(parent); 						cur = parent->parent; 						parent = cur->parent; 					} 					//此时是第三种情况的情景3 					/* 						对subR进行右旋转，然后对parent进行左旋，迭代 					*/ 					else if (parent->right->bf == -1) 					{ 						Node* subR = parent->right; 						Node* subRL = subR->left; 						RotateRL(parent); 						// 不平衡向上调整  注意：bug1（以为调整完就是1或-1了，其实三种情况调整完均为0，需要继续向上迭代 						if (subRL->bf != 1 && subRL->bf != -1) 						{ 							cur = subRL; 							parent = cur->parent; 							continue; 						}  					} 					//此时是第三种情况的情景2 					/* 						 对parent进行左旋，然后修改平衡因子，把subR的平衡因子改为-1， 						 parent的平衡因子改为1，因为subR的平衡因子为-1，所以无需迭代 					*/ 					else if (parent->right->bf == 0) 					{ 						RotateL(parent); 						parent->bf = 1; 						parent->parent->bf = -1; 					} 				} 				// 2.左边高，右旋转调整 				else if (parent->bf == -2) 				{ 					// 如果是一条直线==>右旋转即可 					// 如果是一条折线==>左右旋转 					if (parent->left->bf == -1) 					{ 						RotateR(parent); 						cur = parent->parent;// bug2 cur要变成这个位置是因为选择后父亲的位置变了，画图 						parent = cur->parent; 						continue;//parent不是-1或1就继续 					} 					else if (parent->left->bf == 1)// 调整后 s sR p  如果sR是1或-1可以退出 					{ 						Node* s = parent->left; 						Node* sR = s->right; 						RotateLR(parent); 						// 不平衡向上调整 为0时如果parent为根 						if (sR->bf != 1 && sR->bf != -1) 						{ 							cur = sR; 							parent = cur->parent; 							continue; 						} 					} 					else if (parent->left->bf == 0)// 平衡因子要修改，画图感受 parent->_parent: 1 parent: -1  					{ 						RotateR(parent); 						parent->parent->bf = 1; 						parent->bf = -1; 					} 				}  				// 调整后是平衡树，bf为1或-1，不需要调整了,因为-1和1才是最后真正平衡的状态 				break; 			} 		} 	} 

AVL树的查找

查找的代码和二叉搜索树是一样的，这里就不过多介绍。
代码实现如下：

//AVL树的查找 	bool Find(const K& key) 	{ 		if (root == nullptr) 			return false;  		Node* cur = root; 		while (cur) 		{ 			// 小于往左走 			if (key < cur->key) 			{ 				cur = cur->left; 			} 			// 大于往右走 			else if (key > cur->key) 			{ 				cur = cur->right; 			} 			else 			{ 				// 找到了 				return true; 			} 		}  		return false; 	} 

AVL树完整代码以及测试

#define _CRT_SECURE_NO_WARNINGS #include<iostream> //引入头文件 #include<string>//C++中的字符串 #include<vector> using namespace std; //标准命名空间 template <class K,class V> struct AVL_Node { 	//三叉链 	AVL_Node<K, V>* left; 	AVL_Node<K, V>* right; 	AVL_Node<K, V>* parent;//用来定位父节点 	K key; 	V value; 	int bf;//平衡因子 = 右子树 - 左子树 	AVL_Node(const K& key, const V& value):left(nullptr),right(nullptr),parent(nullptr), key(key), value(value),bf(0) 	{} }; template <class K, class V> class AVL_Tree { 	typedef AVL_Node<K,V> Node; public: 	/* 		注意：一般选取第一个不平衡的节点作为parent 	*/ 	//左单旋，新插入的节点在右子树的右侧 	/* 		步骤： 		    1.让subR的左孩子成为parent的右孩子 			2.然后让parent成为subR的左孩子 			3.最后把两个节点的平衡因子修改为0 	*/ 	void RotateL(Node* parent) 	{ 		Node* subR = parent->right; 		Node* subRL = subR->left; 		//1.先把subR左边（可能为空也可能不为空）作为parent的右边 		parent->right = subRL; 		//2.如果subRL不为空，那么就让subRL的父指针指向parent 		if (subRL) 		{ 			subRL->parent = parent; 		} 		//3.先记录parent的父节点的位置，然后把parent作为subR的左边 		Node* ppNode = parent->parent; 		subR->left = parent; 		//4.parent的父指针指向subR 		parent->parent = subR; 		//5.如果ppNode为空-->说明subR现在是根节点，就让subR的父指针指向nullptr 		//如果不是根节点就把subR的父指针指向parent的父节点，parent的父节点（左或右）指向subR 		if (ppNode == nullptr) 		{ 			//更新根节点 			root = subR; 			subR->parent = nullptr; 		} 		else 		{ 			//判断parent是ppNode的左还是右 			if (ppNode->left == parent) 			{ 				ppNode->left = subR; 			} 			else 			{ 				ppNode->right = subR; 			} 			subR->parent = ppNode; 		} 		//6.把parent和subR的平衡因子更新为0 		subR->bf = parent->bf = 0; 	} 	//右单旋，新插入的节点在左子树的左侧 	/* 		步骤： 			1.让subL的右孩子成为parent的左孩子 			2.然后让parent成为subL的右孩子 			3.最后把两个节点的平衡因子修改为0 	*/ 	void RotateR(Node* parent) 	{ 		Node* subL = parent->left; 		Node* subLR = subL->right; 		//1.先把subL的右边（可能为空也可能不为空）作为parent的左边 		parent->left = subLR; 		//2.如果subLR不为空，就把subLR的父指针指向parent 		if (subLR) 		{ 			subLR->parent = parent; 		} 		//3.记录parent的父节点的位置，然后把parent作为subL的右边 		Node* ppNode = parent->parent; 		subL->right = parent; 		//4.parent的父亲指针指向subL 		parent->parent = subL; 		//5.如果ppNode为空-->说明subL现在是根节点，就让subL的父节点指向nullptr 		//不是根节点就把subL的父节点指向parent的父节点，parent的父节点（左或右）指向subL 		if (ppNode == nullptr) 		{ 			//更新根节点 			root = subL; 			subL->parent = nullptr; 		} 		else 		{ 			//判断parent是ppNode的左还是右 			if (ppNode->left == parent) 			{ 				ppNode->left = subL; 			} 			else 			{ 				ppNode->right = subL; 			} 			subL->parent = ppNode; 		} 		//6.把parent和subL的平衡因子更新为0 		subL->bf = parent->bf = 0; 	} 	//二叉树的插入 	bool Insert(const K& key, const V& value) 	{ 		//先按照二叉搜索树一样插入元素 		 		//无节点插入 		if (root == nullptr) 		{ 			root = new Node(key,value); 			return true; 		} 		//有节点时插入 		Node* parent = nullptr; 		Node* cur = root; 		while (cur) 		{ 			parent = cur; 			//小于往左走 			if (key < cur->key) 			{ 				cur = cur->left; 			} 			//大于往右走 			else if (key > cur->key) 			{ 				cur = cur->right; 			} 			else 			{ 				//找到了，就返回false 				return false; 			} 		} 		cur = new Node(key,value); 		// 判断cur应该插在parent的左还是右  		// 小于在左，大于在右		 		if (cur->key < parent->key) 		{ 			parent->left = cur; 			cur->parent = parent; 		} 		else 		{ 			parent->right = cur; 			cur->parent = parent; 		} 		// 更新parent的平衡因子  		// 节点的插入只会影响cur的祖先的平衡因子（不是所有的，是一部分，分情况） 		while (parent) 		{ 			// 更新parent的平衡因子 			// cur在parent的左，parent->bf-- 			// cur在parent的右，parent->bf++ 			if (cur == parent->left) 				parent->bf--; 			else 				parent->bf++; 			// bf 可能为 -2、-1、0、1、2 			// 如果平衡因子为0，说明更新之前，parent的bf为-1或1，现在补齐了左节点或右节点，bf==0，对上层无影响 			// 如果平衡因子为-1或1，说明更新之前，parent的bf为0，现在增加了一个左节点或有节点，bf==-1 || bf==1,对上层有影响 			// 如果平衡因子为-2或2，说明更新之前，parent的bf为-1或1，现在往左（右）节点补了左（右）节点，也就是一边 			// 拉高了，树不平衡了，需要用左旋转或右旋转来进行调整 			if (parent->bf == 0) 			{ 				//对上层没有影响，退出 				break; 			} 			else if(parent->bf == -1 || parent->bf == 1) 			{ 				// 对上层有影响，迭代更新 				cur = parent; 				parent = parent->parent; 			} 			else 			{ 				// 平衡树出现了问题，需要调整 				// 1.右边高，左旋转调整 				if (parent->bf == 2) 				{ 					// 如果是一条直线==>左旋转即可 					// 如果是一条折线==>右左旋转 					if (cur->bf == 1) 						RotateL(parent); 					else if (cur->bf == -1) 						RotateRL(parent); 				} 				// 2.左边高，右旋转调整 				else if (parent->bf == -2) 				{ 					// 如果是一条直线==>右旋转即可 					// 如果是一条折线==>左右旋转 					if (cur->bf == -1) 						RotateR(parent); 					else if (cur->bf == 1) 						RotateLR(parent); 				} 				// 调整后是平衡树，bf为0，不需要调整了 				break; 			} 		} 		return true; 	} 	//右左双旋，新插入的节点在右子树的左侧 	/* 		步骤： 			1.先对subR进行一个右单旋 			2在对parent进行一个左单旋然后修改平衡因子 	*/ 	void RotateRL(Node* parent) 	{ 		Node* subR = parent->right; 		Node* subRL = subR->left; 		int bf = subRL->bf;//保留subRL的平衡因子的值，方便直到新插入的节点是在subRL左子树还是右子树  		//旋转 先对subR进行右旋转，再对parent进行左旋转 		RotateR(subR); 		RotateL(parent);  		// 从左到右 parent subRL subR 		if (bf == -1)// subRL的左子树  bf: 0 0 1 		{ 			parent->bf = 0; 			subRL->bf = 0; 			subR->bf = 1; 		} 		else if (bf == 1)// subRL的右子树 bf: -1 0 0 		{ 			parent->bf = -1; 			subRL->bf = 0; 			subR->bf = 0; 		} 		else if (bf == 0) 		{ 			parent->bf = 0; 			subRL->bf = 0; 			subR->bf = 0; 		} 	} 	//左右双旋，新插入的节点在左子树的右侧 	/* 		步骤： 			1.先对subR进行一个左单旋 			2.在对parent进行一个右单旋然后修改平衡因子 	*/ 	void RotateLR(Node* parent) 	{ 		Node* subL = parent->left; 		Node* subLR = subL->right; 		int bf = subLR->bf;//保留subLR的平衡因子的值，方便直到新插入的节点是在subLR左子树还是右子树  		//旋转先对subL进行左旋转，再对parent进行右旋转 		RotateL(subL); 		RotateR(parent);  		//从左到右 subL subLR parent 		if (bf == -1)// subLR的左子树  bf: 0 0 1 		{ 			subL->bf = 0; 			subLR->bf = 0; 			parent->bf = 1; 		} 		else if (bf == 1)// subLR的右子树 bf: -1 0 0 		{ 			subL->bf = -1; 			subLR->bf = 0; 			parent->bf = 0; 		} 		else if (bf == 0) 		{ 			subL->bf = 0; 			subLR->bf = 0; 			parent->bf = 0; 		} 	}  	//二叉搜索树的删除 	bool Erase(const K& key) 	{ 		//树为空，删除失败 		if (root == nullptr) 		{ 			return false; 		} 		//parent始终是cur的父亲节点 		//cur就是要找的删除的当前节点 		Node* parent = nullptr; 		Node* cur = root; 		while (cur) 		{ 			//小于往左边走 			if (key < cur->key) 			{ 				parent = cur; 				cur = cur->left; 			} 			//大于往右走 			else if (key > cur->key) 			{ 				parent = cur; 				cur = cur->right; 			} 			else 			{ 				// 找到了，开始删除 				// 1.左右子树都为空，直接删除，可以归类为左为空 				// 2.左右子树只有一边为空，左为空，父亲指向我的右，右为空，父亲指向我的左   				// 3.左右子树都不为空，取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除  				//当前情况是情景三，删除的节点它的左为空，右未知 				if (cur->left == nullptr) 				{ 					// 要删除节点为根节点时，直接把右子树的根节点赋值给——root 					// 根节点的话会导致parent为nullptr 					if (root == cur) 					{ 						root = root->right; 						delete cur; 						break; 					} 					else 					{ 						//左为空，父亲指向我的右 						//判断cur在父亲的左还是右 						if (parent->left == cur) 						{ 							parent->left = cur->right; 							//左子树少了一个节点 ++ 							parent->bf++; 						} 						else 						{ 							parent->right = cur->right; 							//右子树少了一个节点 -- 							parent->bf--; 						} 					} 					if (parent->bf != -1 && parent->bf != 1) 					{ 						AfterEraseUpdateBf(parent); 					} 					delete cur; 				} 				//当前情况是情景二，删除节点它的右为空，左未知 				else if (cur->right == nullptr) 				{ 					if (root == cur) 					{ 						root = root->left; 						delete cur; 						break; 					} 					else 					{ 						//右为空，父亲指向我的左 						//判断cur在父亲的左还是右 						if (parent->left == cur) 						{ 							parent->left = cur->left; 							parent->bf++; 						} 						else 						{ 							parent->right = cur->left; 							parent->bf--; 						} 					} 					if (parent->bf != -1 && parent->bf != 1) 					{ 						AfterEraseUpdateBf(parent); 					} 					delete cur; 				} 				//只剩下情景四 				else 				{ 					//找右子树中最小的节点，当前cur就是要删除的节点 					Node* rightMinParent = cur; 					Node* rightMin = cur->right;//去右子树找最小的节点 					while (rightMin->left) 					{ 						rightMinParent = rightMin; 						rightMin = rightMin->left;//一直往左走，找右子树最小的节点 					} 					//替代删除 					cur->key = rightMin->key; 					//转化成了情景三，左孩子为空 					if (rightMinParent->left == rightMin) 					{ 						rightMinParent->left = rightMin->right; 						rightMinParent->bf++; 					} 					else 					{ 						rightMinParent->right = rightMin->right; 						rightMinParent->bf--; 					} 					if (rightMinParent->bf != -1 && rightMinParent->bf != 1) 					{ 						AfterEraseUpdateBf(rightMinParent); 					}		 					delete rightMin; 				} 				return true; 			} 		} 		return false; 	} 	void AfterEraseUpdateBf(Node* parent) 	{ 		if (parent == nullptr) 		{ 			return; 		} 		Node* cur = parent; 		goto first; 		while (parent) 		{ 			// 更新parent的平衡因子 			// cur在parent的左，parent->_bf++ 			// cur在parent的右，parent->_bf-- 			if (cur == parent->left) 				parent->bf++; 			else 				parent->bf--; 			// bf 可能为 -2、-1、0、1、2 			// 如果平衡因子为0，说明更新之前，parent的bf为-1或1，现在删掉了左节点或右节点，整体高度变了，对上层有影响 			// 如果平衡因子为-1或1，说明更新之前，parent的bf为0，现在删掉了一个左节点或有节点，整体高度不变，对上层无影响 			// 如果平衡因子为-2或2，说明更新之前，parent的bf为-1或1，现在往左（右）节点补了左（右）节点，也就另一边 			// 拉高了，树不平衡了，需要用左旋转或右旋转来进行调整 		first: 			//此时是博客中介绍的第一种情况 			if (parent->bf == 0) 			{ 				//对上层有影响，迭代更新 				//如果parent是根节点就结束 				if (parent->parent == nullptr) 				{ 					break; 				} 				cur = parent; 				parent = parent->parent; 			} 			//此时是博客中介绍的第二种情况 			else if (parent->bf == -1 || parent->bf == 1) 			{ 				//对上层无影响，退出 				break; 			} 			//只剩下第三种情况 			else 			{ 				//平衡树出现了问题，需要调整 				//1.右边高，左旋转调整 				if (parent->bf == 2) 				{ 					//此时是第三种情况的情景1 					/* 						对parent进行左旋转，迭代 					*/ 					if (parent->right->bf == 1) 					{ 						RotateL(parent); 						cur = parent->parent; 						parent = cur->parent; 					} 					//此时是第三种情况的情景3 					/* 						对subR进行右旋转，然后对parent进行左旋，迭代 					*/ 					else if (parent->right->bf == -1) 					{ 						Node* subR = parent->right; 						Node* subRL = subR->left; 						RotateRL(parent); 						// 不平衡向上调整  注意：bug1（以为调整完就是1或-1了，其实三种情况调整完均为0，需要继续向上迭代 						if (subRL->bf != 1 && subRL->bf != -1) 						{ 							cur = subRL; 							parent = cur->parent; 							continue; 						}  					} 					//此时是第三种情况的情景2 					/* 						 对parent进行左旋，然后修改平衡因子，把subR的平衡因子改为-1， 						 parent的平衡因子改为1，因为subR的平衡因子为-1，所以无需迭代 					*/ 					else if (parent->right->bf == 0) 					{ 						RotateL(parent); 						parent->bf = 1; 						parent->parent->bf = -1; 					} 				} 				// 2.左边高，右旋转调整 				else if (parent->bf == -2) 				{ 					// 如果是一条直线==>右旋转即可 					// 如果是一条折线==>左右旋转 					if (parent->left->bf == -1) 					{ 						RotateR(parent); 						cur = parent->parent;// bug2 cur要变成这个位置是因为选择后父亲的位置变了，画图 						parent = cur->parent; 						continue;//parent不是-1或1就继续 					} 					else if (parent->left->bf == 1)// 调整后 s sR p  如果sR是1或-1可以退出 					{ 						Node* s = parent->left; 						Node* sR = s->right; 						RotateLR(parent); 						// 不平衡向上调整 为0时如果parent为根 						if (sR->bf != 1 && sR->bf != -1) 						{ 							cur = sR; 							parent = cur->parent; 							continue; 						} 					} 					else if (parent->left->bf == 0)// 平衡因子要修改，画图感受 parent->_parent: 1 parent: -1  					{ 						RotateR(parent); 						parent->parent->bf = 1; 						parent->bf = -1; 					} 				}  				// 调整后是平衡树，bf为1或-1，不需要调整了,因为-1和1才是最后真正平衡的状态 				break; 			} 		} 	} 	//AVL树的查找 	bool Find(const K& key) 	{ 		if (root == nullptr) 			return false;  		Node* cur = root; 		while (cur) 		{ 			// 小于往左走 			if (key < cur->key) 			{ 				cur = cur->left; 			} 			// 大于往右走 			else if (key > cur->key) 			{ 				cur = cur->right; 			} 			else 			{ 				// 找到了 				return true; 			} 		}  		return false; 	}  	//中序遍历（递归） 	void InOrder() 	{ 		_InOrder(root); 		cout << endl; 	} 	void _InOrder(Node* root) 	{ 		if (root == NULL) 		{ 			return; 		} 		else 		{ 			_InOrder(root->left); 			cout << root->key << ":" << root->value<<" "; 			_InOrder(root->right); 		} 	} 	int _Height(Node* root) 	{ 		if (root == nullptr) 			return 0;  		int leftHeight = _Height(root->left); 		int rightHeight = _Height(root->right);  		return 1 + max(leftHeight, rightHeight); 	}  	bool _IsBalanceTree(Node* root) 	{ 		if (root == nullptr) 			return true; 		int leftHeight = _Height(root->left); 		int rightHeight = _Height(root->right);  		return rightHeight - leftHeight == root->bf 			&& abs(rightHeight - leftHeight) < 2 			&& _IsBalanceTree(root->left) 			&& _IsBalanceTree(root->right); 	}  public: 	Node* root = nullptr; };  void TestAVLTree1() { 	AVL_Tree<int, int> at; 	//srand((size_t)time(nullptr)); 	int b[] = { 4,3,5,3,1,2,7 };//出错 	//int b[] = { 1,2,3,4,5,6,7,8,9 };正确 	//int b[] = { 2,4,6,3,5,1,9,10,8,7 };正确 	//int b[] = {4,2,3,5};//出错,插入3出错 	//int b[] = { 16,3,7,11,9,26,18,14,15 };//出错 	//int b[] = { 4,2,6,1,3,5,15,7,16,14 };//出错 	// int* a = new int[10000]; 	/*int i = 1; 	for (auto& e : a) 	{ 		e = i++; 	}*/ 	vector<int> a; 	for (size_t i = 0; i < sizeof(b)/sizeof(int); ++i) 	{ 		// a.push_back(rand()); 		a.push_back(b[i]); 	} 	for (auto e : a) 	{ 		at.Insert(e,e); 		cout << "插入 " << e << " 后变化 --> Height: " << at._Height(at.root) << " 是否为AVLTree：" << at._IsBalanceTree(at.root)<<endl; 		cout << "打印二叉树： "; 		at.InOrder(); 	}  	cout << "------------------------------------------------------" << endl; 	// at.InOrder(); 	for (auto e : a) 	{ 		at.Erase(e); 		cout << "删除 " << e << " 后变化 --> Height: " << at._Height(at.root) << " 是否为AVLTree：" << at._IsBalanceTree(at.root) << endl; 		cout << "打印二叉树： "; 		at.InOrder(); 	} 	at.InOrder(); } int main() { 	TestAVLTree1(); 	system("pause"); 	return EXIT_SUCCESS; }