1. AI技术聚合首页
  2. IT

【C++】AVL树

心中带点小风骚 • • IT • 阅读 40

AVL树

  • 一、AVL树概念
  • 二、AVL树实现
    • 1. AVL树节点的定义
    • 2. AVL树的定义
    • 3. AVL树的插入
    • 4. AVL树的验证

一、AVL树概念

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

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

  • 它的左右子树都是AVL树
  • 左右子树高度之差(简称平衡因子，等于右子树高度 – 左子树高度)的绝对值不超过1(-1/0/1)

如下是一颗 AVL 树，蓝色数字代表平衡因子：

二、AVL树实现

1. AVL树节点的定义

想要实现一个AVL树 ，首先我们得有树的节点，而树的节点中我们需要存：该节点的父节点、该节点的右孩子、该节点的左孩子、平衡因子以及数据类型；为了方便后面红黑树的学习我们在这里给的数据类型是 pair，大家也可以定义成其他类型；代码如下：

		template<class K, class V>
		struct AVLTreeNode
		{
			AVLTreeNode* _left;		// 左孩子
			AVLTreeNode* _right;	// 右孩子
			AVLTreeNode* _parent;	// 父节点
			pair<K, V> _kv;			// 数据类型
			int _bf;				// 平衡因子
		
			AVLTreeNode(const pair<K, V>& kv)
				:_left(nullptr)
				,_right(nullptr)
				,_parent(nullptr)
				,_kv(kv)
				,_bf(0)
			{}
		};

2. AVL树的定义

AVL树的定义如下：

		template<class K, class V>
		class AVLTree
		{
			typedef AVLTreeNode<K, V> Node;
		private:
			Node* _root = nullptr;
		};

3. AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：

  1. 按照二叉搜索树的方式插入新节点
  2. 调整节点的平衡因子并进行旋转

所以我们先按照原来二叉搜索树的插入逻辑插入节点，插入节点后再进行其它操作，代码如下：

		bool Insert(const pair<K, V>& kv)
		{
			if (_root == nullptr)
			{
				_root = new Node(kv);
				return true;
			}
	
			Node* parent = nullptr, * cur = _root;
			while (cur)
			{
				if (cur->_kv.first > kv.first)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_kv.first < kv.first)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					return false;
				}
			}
	
			cur = new Node(kv);
			if (parent->_kv.first > kv.first)
			{
				parent->_left = cur;
				cur->_parent = parent;
			}
			else
			{
				parent->_right = cur;
				cur->_parent = parent;
			}
		}

新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了AVL树的平衡性。新增可能会影响祖先节点，此时需要判断子树的高度是否发生变化，如果子树高度不变，就不会继续往上影响祖先；如果子树高度发生变化，就会继续往上影响祖先。

因为平衡因子 = 右子树高度 – 左子树高度，所以新增节点在左子树，父节点的 _bf–；新增节点在右子树，父节点的 _bf++；

  • 更新平衡因子

更新平衡因子后有以下三种情况：

  1. 父节点更新后 _bf == 0，说明父节点所在的子树高度不变，不用继续往上更新了，插入结束；如下图所示：

如上图，在插入新节点前，父节点(8所在的节点) _bf == 1 or -1，是一边高一边低，新插入的节点填上低的那边。

  1. 父节点更新后，_bf == 1 or -1，父节点所在的子树高度发生变化，必须继续往上更新；如下图所示：

如上图，在插入节点前，父节点(8所在的节点)的 _bf == 0，两边一样高，插入导致高度发生了变化。

  1. 父节点更新后，_bf == 2 or -2，父节点所在的子树破坏了AVL树的平衡，需要调整处理；如下图所示：

所以更新平衡因子的代码如下，续上面的代码：

			// 循环的结束条件有：1、parent 为空；2、平衡因子为0；3、旋转完成
			while (parent)
			{
				// 更新平衡因子
				if (cur == parent->_left)
				{
					parent->_bf--;
				}
				else
				{
					parent->_bf++;
				}
	
				// 插入后左右子树变平衡
				if (parent->_bf == 0)
				{
					break;
				}
	
				// 插入后左右子树高度差为1，继续往上更新
				else if (parent->_bf == 1 || parent->_bf == -1)
				{
					cur = parent;
					parent = parent->_parent;
				}
	
				// 插入后左右子树高度差超过1，需要调整旋转
				else if (parent->_bf == 2 || parent->_bf == -2)
				{
					// 旋转
				}
				
				// 当走到这里说明这棵树有问题，直接报错
				else
				{
					assert(false);
				}
			}
  • 旋转

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

  1. 新节点插入较高右子树的右侧- – -右右- – – 右边高：左单旋

没插入之前如下图，30 的右子树高度为 h+1，左子树高度为 h，所以平衡因子为1.

当新插入节点在较高右子树的右侧，即在 c 子树的位置插入；以上这个图叫做抽象图，因为情况太多了画不完，所以用抽象图表示更为直观；要在 c 子树插入引起旋转，那么 c 一定为高度为 h 的满AVL树或者空树，a 和 b 就不一定。

我们在 c 子树插入节点，导致以 30 为根的二叉树不平衡，要让它平衡，只能想办法让右子树的高度减少一层，左子树的高度增加一层；即将 60 往上提，30 旋转下来；因为 60 比 30 大，所以 60 所在的子树都比 30 大，所以我们可以将 60 的左子树接到 30 的右边，然后让 60 去做新的根，60 的左边更新为新的 30 的子树；如下图所示：

在旋转过程中，有以下几种情况需要考虑：
（1）60 节点的左孩子可能存在，也可能不存在
（2）30 可能是根节点，也可能是子树；如果是根节点，旋转完成后，要更新根节点；如果是子树，可能是某个节点的左子树，也可能是右子树。
（3）旋转完成后，30 和 60 的 _bf 都变成了 0.

所以左单旋的代码如下：

		// 左单旋
		void RotateL(Node* parent)
		{
			Node* subR = parent->_right, * subRL = subR->_left;
	
			parent->_right = subRL;
			if (subRL)
				subRL->_parent = parent;
			subR->_left = parent;
	
			Node* parentParent = parent->_parent;
			parent->_parent = subR;
	
			// 如果 parent 是根节点，就直接更新 subR 为根节点，并将 subR 的_parent指向空
			if (_root == parent)
			{
				_root = subR;
				subR->_parent = nullptr;
			}
	
			// 否则，先判断 parent 是 parentParent 的右还是左，再将parentParent的左或者右连接subR
			else
			{
				if (parentParent->_left == parent)
				{
					parentParent->_left = subR;
				}
				else
				{
					parentParent->_right = subR;
				}
				subR->_parent = parentParent;
			}
	
			// 最后更新 _bf
			subR->_bf = parent->_bf = 0;
		}
  1. 新节点插入较高左子树的左侧- – -左左- – -左边高：右单旋

没插入之前如下图，60 的右子树高度为 h，左子树高度为 h+1，所以平衡因子为 -1.

与左单旋的分析类似，右单旋中，是在 a 的子树中插入新节点，因为 30 是 60 的左子树，所以 30 这颗子树都比 60 要小，所以可以将 30 的右子树变成 60 的左子树，然后让 30 成为新的根，再让 60 这颗新的子树成为 30 的右子树。如下图所示：

我们可以观察到，无论是左单旋还是右单旋，从新插入节点到根节点的线条是一条直线；我们可以以此作为与下面双旋的区分；如下图：

在旋转过程中，有以下几种情况需要考虑：
（1）30 节点的右孩子可能存在，也可能不存在。
（2）60 可能是根节点，也可能是子树；如果是根节点，旋转完成后，要更新根节点；如果是子树，可能是某个节点的左子树，也可能是右子树。
（3）旋转完成后，30 和 60 的 _bf 都变成了 0.

所以右单旋的代码如下：

		// 右单旋
		void RotateR(Node* parent)
		{
			Node* subL = parent->_left, * subLR = subL->_right;
	
			parent->_left = subLR;
			if (subLR)
				subLR->_parent = parent;
			subL->_right = parent;
	
			Node* parentParent = parent->_parent;
			parent->_parent = subL;
	
			
			if (_root == parent)
			{
				_root = subL;
				subL->_parent = nullptr;
			}
			else
			{
				if (parentParent->_left == parent)
				{
					parentParent->_left = subL;
				}
				else
				{
					parentParent->_right = subL;
				}
				subL->_parent = parentParent;
			}
	
			subL->_bf = parent->_bf = 0;
		}
  1. 新节点插入较高左子树的右侧- – -左右：先左单旋再右单旋(左右双旋)

如下图所示，我们无论在 subLR 节点的左右子树(是满AVL树的前提下)插入的时候，会改变 subLR 的高度，进而会往上更新，一直更新到根 parent，此时单旋就满足不了这种情况了：

通过观察可以得到，我们从 subLR 的左右子树插入新节点，那么新节点到 parent 根节点的线条是一条折线，通过这种方法可以区分不同的旋转；如下图所示：

于是我们有以下方法解决：将双旋变成单旋后再旋转，即：先对以 subL 节点的子树进行左单旋，然后再对 parent 节点为子树进行右单旋，旋转完成后再考虑平衡因子的更新。如下图所示：


因为我们只能从 b 或 c 子树插入新节点，那么我们怎么区分它在哪里插入的呢？通过观察我们可以发现，在 b 或者 c 子树插入新节点，一定会影响 subLR；所以分为以下三种情况：

  1. 当在 subLR 的左子树插入， subLR 的 _bf 就变成了 -1；此时旋转完成后，parent 的 _bf 变为 1，subL 和 subLR 的 _bf 都变成了 0.

  2. 当在 subLR 的右子树插入，subLR 的 _bf 就变成了 1；此时旋转完成后，subL 的 _bf 变为 1，parent 和 subLR 的 _bf 都变成了 0.

  3. 当 subLR 本身就是新增节点， subLR 的 _bf 就是 0；此时旋转完成后 parent 、subLR 和 subL 的 _bf 都是 0.

所以我们可以根据 subLR 的 _bf 来对这三种情况进行区分。代码如下：

		// 左右双旋
		void RotateLR(Node* parent)
		{
			Node* subL = parent->_left, * subLR = subL->_right;
			int bf = subLR->_bf;
	
			RotateL(parent->_left);
			RotateR(parent);
	
			if (bf == 0)
			{
				parent->_bf = subLR->_bf = subL->_bf = 0;
			}
			else if (bf == -1)
			{
				parent->_bf = 1;
				subLR->_bf = subL->_bf = 0;
			}
			else if (bf == 1)
			{
				subL->_bf = -1;
				parent->_bf = subLR->_bf = 0;
			}
			else
			{
				assert(false);
			}
		}
  1. 新节点插入较高右子树的左侧—右左：先右单旋再左单旋(右左双旋)

如下图所示，我们无论在 subRL 节点的左右子树(是满AVL树的前提下)插入的时候，会改变 subRL 的高度，进而会往上更新，一直更新到根 parent，此时单旋就满足不了这种情况了：

右左双旋中新插入节点到 parent 的线条折线为：

分析过程与左右双旋类似：

  1. 当在 subRL 的左子树插入， subRL 的 _bf 就变成了 -1；此时旋转完成后，subR 的 _bf 变为 1，parent 和 subRL 的 _bf 都变成了 0.

  2. 当在 subRL 的右子树插入，subRL 的 _bf 就变成了 1；此时旋转完成后，parent 的 _bf 变为 -1，subR 和 subRL 的 _bf 都变成了 0.

  3. 当 subRL 本身就是新增节点， subRL 的 _bf 就是 0；此时旋转完成后 parent 、subRL 和 subR 的 _bf 都是 0.

如下图所示：


代码如下：

		// 右左双旋
		void RotateRL(Node* parent)
		{
			Node* subR = parent->_right, * subRL = subR->_left;
			int bf = subRL->_bf;
	
			RotateR(parent->_right);
			RotateL(parent);
	
			// 新增节点就是 subRL
			if (bf == 0)
			{
				parent->_bf = subR->_bf = subRL->_bf = 0;
			}
	
			// subRL 的右子树新增节点
			else if (bf == 1)
			{
				parent->_bf = -1;
				subR->_bf = subRL->_bf = 0;
			}
	
			// subRL 的左子树新增节点 
			else if (bf == -1)
			{
				subR->_bf = 1;
				parent->_bf = subRL->_bf = 0;
			}
			else
			{
				assert(false);
			}
		}

其中完整的插入代码如下：

		bool Insert(const pair<K, V>& kv)
		{
			if (_root == nullptr)
			{
				_root = new Node(kv);
				return true;
			}
	
			Node* parent = nullptr, * cur = _root;
			while (cur)
			{
				if (cur->_kv.first > kv.first)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_kv.first < kv.first)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					return false;
				}
			}
	
			cur = new Node(kv);
			if (parent->_kv.first > kv.first)
			{
				parent->_left = cur;
				cur->_parent = parent;
			}
			else
			{
				parent->_right = cur;
				cur->_parent = parent;
			}
	
			// 循环的结束条件有：1、parent 为空；2、平衡因子为0；3、旋转完成
			while (parent)
			{
				// 更新平衡因子
				if (cur == parent->_left)
				{
					parent->_bf--;
				}
				else
				{
					parent->_bf++;
				}
	
				// 插入后左右子树变平衡
				if (parent->_bf == 0)
				{
					break;
				}
	
				// 插入后左右子树高度差为1，继续往上更新
				else if (parent->_bf == 1 || parent->_bf == -1)
				{
					cur = parent;
					parent = parent->_parent;
				}
	
				// 插入后左右子树高度差超过1，需要调整旋转
				else if (parent->_bf == 2 || parent->_bf == -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)
					{
						RotateRL(parent);
					}
					else if (parent->_bf == -2 && cur->_bf == 1)
					{
						RotateLR(parent);
					}
					break;
				}
	
				// 当走到这里说明这棵树有问题
				else
				{
					assert(false);
				}
			}
			return true;
		}

4. AVL树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

  1. 验证其为二叉搜索树
    如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
  2. 验证其为平衡树
    每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)，就说明为平衡树

按中序打印结果，验证是否是搜索二叉树：

			void InOrder()
			{
				_InOrder(_root);
			}
		
			void _InOrder(Node* root)
			{
				if (root == nullptr)
					return;
		
				_InOrder(root->_left);
				cout << root->_kv.first << " ";
				_InOrder(root->_right);
			}

验证是否是平衡树：

			bool IsBalance()
			{
				return _IsBalance(_root);
			}
		
			bool _IsBalance(Node* root)
			{
				if (root == nullptr)
					return true;
		
				int leftHeight = _Height(root->_left);
				int rightHeight = _Height(root->_right);
				if (rightHeight - leftHeight != root->_bf)
				{
					cout << root->_kv.first << "平衡因子异常" << endl;
					return false;
				}
		
				return abs(leftHeight - rightHeight) <= 1
					&& _IsBalance(root->_left)
					&& _IsBalance(root->_right);
			}

			int Height()
			{
				return _Height(_root);
			}			

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

下面我们开始生成一些随机数插入 AVL树 中，观察是否有问题；代码如下：

		int main()
		{
			const int N = 200;
			vector<int> v;
			v.reserve(N);
			srand(time(0));
			
			for (size_t i = 0; i < N; i++)
				v.push_back(rand());
		
			AVLTree<int, int> t;
			for (auto e : v)
				t.Insert(make_pair(e, e));
		
			t.InOrder();
			
			if (t.IsBalance())
				cout << "AVL树正常" << endl;
			else
				cout << "AVL树异常" << endl;
		
			return 0;
		}

我们随机生成 200 个数插入到 AVL树 中，观察是否正常：

如上图，我们就验证了我们写的AVL树是没有问题的。

文章出处登录后可见！

已经登录？立即刷新

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
心中带点小风骚的头像心中带点小风骚普通用户
0
上一篇 2023年12月7日
下一篇 2023年12月7日

相关推荐