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

转载作者：我是一只小鸟更新时间：2022-12-03 14:31:07

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;
}

最后此篇关于数据结构高阶--AVL（平衡二叉树）（图解+实现）的文章就讲到这里了,如果你想了解更多关于数据结构高阶--AVL（平衡二叉树）（图解+实现）的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！。

文章推荐： Promise知一二

文章推荐： [.NET学习]EFCore学习之旅-2简单的增删改查

文章推荐： MySQL锁，锁的到底是什么？

android -/数据/数据/在哪里？
初学者 android 问题。好的，我已经成功写入文件。例如。 //获取文件名 String filename = getResources().getString(R.string.filename
安卓/数据/数据/mypackage/img
我已经将相同的图像保存到/data/data/mypackage/img/中，现在我想显示这个全屏，我曾尝试使用 ACTION_VIEW 来显示 android 标准程序，但它不是从/data/dat
ios - Swift 4:无法将“数据”类型的值转换为预期的参数类型“数据”
我正在使用Xcode 9，Swift 4。我正在尝试使用以下代码从URL在ImageView中显示图像: func getImageFromUrl(sourceUrl: String) -> UII
android - 基因运动。如何从设备中提取数据库。我的/数据/数据/文件夹似乎是空的
我的 Ubuntu 安装 genymotion 有问题。主要是我无法调试我的数据库，因为通过 eclipse 中的 DBMS 和 shell 中的 adb 我无法查看/data/文件夹的内容。没有显示
php - JSON 数据 ajax 不是正确的 POST 数据
我正在尝试用 PHP 发布一些 JSON 数据。但是出了点问题。这是我的 html -- {% for x in sets %}
r - lm(数据~时间)和tslm(数据~趋势)有什么区别
我观察到两种方法的结果不同。为什么是这样？我知道 lm 上发生了什么，但无法弄清楚 tslm 上发生了什么。 > library(forecast) > set.seed(2) > tts lm(t
Spring 数据 JPA 和 Spring 数据 Elasticsearch ；找不到类型的属性索引？
我不确定为什么会这样!我有一个由 spring data elasticsearch 和 spring data jpa 使用的类，但是当我尝试运行我的应用程序时出现错误。 Error creatin
d3.js - 数据过滤器适用于 json 数据，但不适用于 csv 数据
在 this vega 图表，如果我下载并转换 flare-dependencies.json使用以下 jq 到 csv命令， jq -r '(map(keys) | add | unique) as
php - 在 .php 文件中发送 mysql 数据/mysql 数据
我正在提交一个项目，我必须在其中创建一个带有表的 mysql 数据库。一切都在我这边进行，所以我只想检查如何将我所有的压缩文件发送给使用不同计算机的人。基本上，我如何为另一台计算机创建我的数据库文件，
android - 如何使用 Android Device Monitor 的文件资源管理器查找我的应用程序/数据/数据
我有一个应用程序可以将文本文件写入内部存储。我想仔细看看我的电脑。我运行了 Toast.makeText 来显示路径，它说:/数据/数据/我的包但是当我转到 Android Studio 的 An
android - 如何从 Genymotion 的 android 模拟器访问文件/数据/数据？
我喜欢使用 Genymotion 模拟器以如此出色的速度加载 Android。它有非常好的速度，但仍然有一些不稳定的性能。如何从 Eclipse 中的文件资源管理器访问 Genymotion 模拟器
silverlight - 如果我在 setter 中使用不同的值更改绑定(bind)数据，如何刷新绑定(bind)数据
我需要更改 Silverlight 中文本框的格式。数据通过 MVVM 绑定(bind)。例如，有一个 int 属性，我将 1 添加到 setter 中的值并调用 OnPropertyChanged
youtube - 通过 YouTube 数据 API 访问公共(public)数据，无需身份验证。
我想向 Youtube Data API 提出请求，但我不需要访问任何用户信息。我只想浏览公共(public)视频并根据搜索词显示视频。我可以在未经授权的情况下这样做吗？最佳答案 YouTube
python - 无法让 twilio 显示 'from' 数据，但它会显示 'to' 数据
我已经设置了一个 Twilio 应用程序，我想向人们发送更新，但我不想回复单个文本。我只是想让他们在有问题时打电话。我一切正常，但我想在发送文本时显示传入文本，以确保我不会错过任何问题。我正在使用 p
javascript - 向客户端发送 JSON 数据？ D3.js 渲染 JSON 数据
我有一个带有表单的网站(目前它是纯 HTML，但我们正在切换到 JQuery)。流程是这样的: 接受用户的输入 --- 5 个整数通过 REST 调用网络服务在服务器端运行一些计算...并生成一个
javascript - 如何检测一个 JavaScript 文件只包含 JSON 数据，还是打算包含 JSON 数据？
假设我们有一个名为 configuration.js 的文件，当我们查看内部时，我们会看到: 'use strict'; var profile = { "project": "%Projec
javascript - 在初始 .ajax 调用之外使用 JSON 数据 - 访问剩余的 JSON 数据
这部分是对 Previous Question 的扩展我的: 我现在可以从我的 CI Controller 成功返回 JSON 数据，它返回: {"results":[{"id":"1","Sourc
ios - 删除所有 Couchbase 数据/文档 ios(或删除所有 ios 数据？)
有什么有效的方法可以删除 ios 中 CBL 的所有文档存储？我对此有疑问，或者，如果有人知道如何从本质上使该应用程序像刚刚安装一样，那也会非常有帮助。我们正在努力确保我们的注销实际上将应用程序设置为
javascript - $.post(url, 函数(数据,状态) {警报(数据)});警报()不工作
我有一个 Rails 应用程序，它与其他 Rails 应用程序通信以进行数据插入。我使用 jQuery $.post 方法进行数据插入。对于插入，我的其他 Rails 应用程序显示 200 OK。但在
javascript - 断言错误 : expected { status: 'SUCCESS' , 数据 : [] } to equal { Object (status, 数据)}
我正在为服务于发布请求的 API 调用运行单元测试。我正在传递请求正文，并且必须将响应作为帐户数据返回。但我只收到断言错误注意:数据是从 Azure 中获取的 spec.js const accou

我是一只小鸟

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

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

AVL树（平衡二叉树）

概念

AVL树节点定义以及框架

AVL树的插入

方法概述

平衡因子的调节

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

插入代码的实现

AVL树的删除

方法概述

平衡因子调节

旋转处理

删除代码的实现

AVL树的查找

AVL树完整代码以及测试