C++数据结构——AVL树

C++数据结构——AVL树

码农世界 2024-05-14 前端 60 次浏览 0个评论

前言：本篇文章将紧随二叉搜索树的节奏，分享一个新的数据结构——AVL树。

目录

一.AVL树概念

二.AVL树插入规则

三.AVL树实现

1.基本框架

2.插入

3.旋转

1）左\右单旋

2）左右/右左双旋

4.遍历

5.求树高度

6.判断平衡

7.求树高度

总结

一.AVL树概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。

但是当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

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

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

    二.AVL树插入规则

    由于AVL树的独特结构，我们给出以下的插入规则： 

    1.按照搜索树规则插入。

    2.更新插入节点的祖先节点的平衡因子：

            a.插入父亲的左边，父亲的平衡因子--。

            b.插入父亲的右边，父亲的平衡因子++。

            c.父亲的平衡因子 == 0，父亲所在的子树高度不变，不再往上更新，插入结束。

            d.父亲平衡因子 == 1 or -1，父亲所在的子树高度变了，往上更新，重复以上步骤。

            e.父亲平衡因子 == 2 or -2，父亲所在的子树已经不平衡了，需要旋转处理。

    三.AVL树实现

    1.基本框架

    template
struct AVLTreeNode
{
	struct AVLTreeNode* _left;
	struct AVLTreeNode* _right;
	struct AVLTreeNode* _parent;
	int _bf;
	pair _kv;
	AVLTreeNode(const pair& kv)
		:_left(nullptr)
		, _right(nullptr)
		,_parent(nullptr)
		, _kv(kv)
		,_bf(0)
	{}
};
template
class AVLTree
{
	typedef AVLTreeNode Node;
private:
	Node* _root;
};

    基本框架与平衡二叉树类似，区别在于AVL树的节点为键值对。

    同时我们还需增加平衡因子_bf和父节点_parent，方便我们进行调整。

    2.插入

    	//插入
	bool Insert(const pair& kv)
	{
		//判空
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		//找到插入位置
		Node* parent = nullptr;
		Node* cur = _root;
		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
				return false;
		}
		//插入
		cur = new Node(kv);
		if (kv.first < parent->_kv.first)
			parent->_left = cur;
		else
			parent->_right = cur;
		cur->_parent = parent;
		//更新平衡因子
		return true;
	}

    基本的插入步骤与平衡二叉树一模一样，需要关注的就是插入的节点变为键值对。

    下面我们单独来看如何更新平衡因子：

            while (parent)
		{
			if (cur == cur->_parent->_left)
				parent->_bf--;
			else
				parent->_bf++;
			if (parent->_bf == 0)
				//更新结束
				break;
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				//往上更新
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//出现问题，进行旋转
				break;
			}
			else
				assert(false);
		}

    按照我们上边的规则其实很好写出上述代码，要注意循环条件为parent，如果没有父亲，也就是到达了根节点，那就无法再进行调整。 

    下面我们来重点关注，如何进行旋转。

    3.旋转

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

    1.  新节点插入较高左子树的左侧---左左：右单旋。
    2.  新节点插入较高右子树的右侧---右右：左单旋。
    3. 新节点插入较高左子树的右侧---左右：先左单旋再右单旋。
    4. 新节点插入较高右子树的左侧---右左：先右单旋再左单旋。

    下面我们就一一来看这四种情况。

    1）左\右单旋

    先来看右单旋，可以抽象理解为，左子树过高，需要向右边旋转拉低。 

    从上图能够看出，右单旋的步骤为：

    1. 让平衡因子为-2的节点成为它的左子节点的右子节点；
    2. 同时让该左子节点的右子节点成为平衡因子为-2的节点的左子节点。

    同时我们需要关注的细节是：

    • 平衡因子为-2的节点是否为根节点。如果不是根节点则需要调整其父节点的指向。
    • 左子节点的右子节点是否为空。

      通过这样的调整，就可以实现平衡，同时调整的两个关键节点的平衡因子均归0。 

      下面来看代码：

      	void RotateR(Node* parent)
	{
		//定义左子节点
		Node* subL = parent->_left;
		//定义左子节点的右子节点
		Node* subLR = subL->_right;
		//调整
		parent->_left = subLR;
		//判空
		if (subLR)
			subLR->_parent = parent;
		//调整
		subL->_right = parent;
		Node* ppNode = parent->_parent;
		parent->_parent = subL;
		if (parent == _root)//判断是否为根
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else//不是根节点，调整父节点指向
		{
			if (ppNode->_left == parent)
				ppNode->_left = subL;
			else
				ppNode->_right = subL;
			subL->_parent = ppNode;
		}
		//平衡因子归0
		parent->_bf = subL->_bf = 0;
	}

      再来看左单旋： 

       左单旋则与右单旋完全相反，所以我们不做过多解释，直接给出代码：

      	//左单旋
	void RotateL(Node* parent)
	{
		//定义右子节点
		Node* subR = parent->_right;
		//定义右子节点的左子节点
		Node* subRL = subR->_left;
		//调整
		parent->_right = subRL;
		//判空
		if (subRL)
			subRL->_parent = parent;
		//调整
		subR->_left = parent;
		Node* ppNode = parent->_parent;
		parent->_parent = subR;
		if (parent == _root)//判断是否为根
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else//不是根节点，调整父节点指向
		{
			if (ppNode->_left == parent)
				ppNode->_left = subR;
			else
				ppNode->_right = subR;
			subR->_parent = ppNode;
		}
		//平衡因子归0
		parent->_bf = subR->_bf = 0;
	}

      2）左右/右左双旋

      如果说树并不是子树的一条斜边独高，而是折线型的一颗子树高，此时单靠单旋是解决不了问题的，因此需要通过双旋来解决。

      上图所示为先左后右的折线型，所以我们需要进行左右双旋，步骤为：

      1. 先从折线的折点位置，即上图的30位置，进行左单旋，使树变为左边一条斜边独高的树。
      2. 在从折线起点位置进行右单旋。
      3. 更新平衡因子。

      其中更新平衡因子也分为不同的情况，以上图为例：

      • 如果新节点插入位置为60的左，那么旋转后60为0,30为0,90为1。
      • 如果新节点插入位置为60的右，那么旋转后60为0,30为-1,90为0。
      • 如果新节点就是60，那么三者的平衡因子均为0。

        下面上代码：

        	//左右双旋
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;
		RotateL(parent->_left);
		RotateR(parent);
		if (bf == -1)
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 1)
		{
			subL->_bf = -1;
			subLR->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == 0)
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

         注意更新平衡因子是通过初始时折线末点的平衡因子判断的，所以要提前记录。

        再来看右左双旋：

         与左右双旋相反，右左双旋是先右后左的折线，所以其操作步骤与之相反：

        1. 先从折线的折点位置，即上图的90位置，进行右单旋，使树变为右边一条斜边独高的树。
        2. 在从折线起点位置进行左单旋。
        3. 更新平衡因子。

        其中更新平衡因子也同样分为不同的情况，以上图为例：

        • 如果新节点插入位置为60的左，那么旋转后60为0,30为0,90为1。
        • 如果新节点插入位置为60的右，那么旋转后60为0,30为-1,90为0。
        • 如果新节点就是60，那么三者的平衡因子均为0。

          代码如下：

          	//右左双旋
	void RotateLR(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;
		RotateR(parent->_right);
		RotateL(parent);
		if (bf == -1)
		{
			subR->_bf = 1;
			subRL->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == 1)
		{
			subR->_bf = 0;
			subRL->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == 0)
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

          根据父节点及其左右子节点的平衡因子，即可判断对应的旋转方式，下面补充插入步骤：

           

          			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//出现问题，进行旋转
				//左单旋
				if (parent->_bf == -2 && parent->_left->_bf == -1)
				{
					RotateL(parent);
				}
				//右单旋
				else if (parent->_bf == 2 && parent->_right->_bf == 1)
				{
					RotateR(parent);
				}
				//左右单旋
				else if (parent->_bf == -2 && parent->_left->_bf == 1)
				{
					RotateLR(parent);
				}
				//右左单旋
				else
				{
					RotateRL(parent);
				}
				break;
			}

          4.遍历

          遍历操作与二叉搜索树类似，需要修改的是我们需要将键值对均打印出来：

          	//遍历
	void InOrder()
	{
		inOrder(_root);
		cout << endl;
	}
	void inOrder(const Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		inOrder(root->_left);
		cout << root->_kv.first << ':' << root->_kv.second << " ";
		inOrder(root->_right);
	}

          为了方便调用函数而无需传参，我们采用如上方式进行代码编写。 

          5.求树高度

          求树高度我们前边在讲解二叉树的时候已经分享过了，只需求出左右子树高度的最大值＋1即可，通过递归计算：

          	//求树高度
	int Height(const Node* root)
	{
		if (root == nullptr)
			return 0;
		return max(Height(root->_left), Height(root->_right)) + 1;
	}

          6.判断平衡

          判断树是否平衡，即判断两棵子树的高度差是否大于等于2：

          	//判断平衡
	bool IsBalance()
	{
		return isBalance(_root);
	}
	bool isBalance(const Node* root)
	{
		if (root == nullptr)
			return true;
		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);
		if (abs(leftHeight - rightHeight) >= 2)
			return false;
		//检查平衡因子
		if (rightHeight - leftHeight != root->_bf)
			return false;
		return isBalance(root->_left) && isBalance(root->_right);
	}

          同时还需要通过递归来判断各个子树是否平衡。

          7.求树高度

          求树的大小，通过递归即求左子树的大小+右子树的大小+根节点：

          	//求树大小
	int Size()
	{
		return size(_root);
	}
	int size(const Node* root)
	{
		if (root == nullptr)
			return 0;
		return size(root->_left) + size(root->_right) + 1;
	}

          总结

          关于AVL树的基本内容就分享这么多，喜欢本篇文章的小伙伴记得一键三连，我们下期再见！

转载请注明来自码农世界，本文标题：《C++数据结构——AVL树》

百度分享代码，如果开启HTTPS请参考李洋个人博客
37815篇文章 站点 微博
每一天，每一秒，你所做的决定都会改变你的人生！

发表评论

快捷回复：

评论列表 （暂无评论，60人围观）参与讨论

还没有评论，来说两句吧...

Top