手撕 AVL 树——C++ 高阶数据结构详解

目录

    • 传统艺能
    • 概念
    • AVL 树结构定义
    • 数据插入
    • AVL 树旋转
      • 左单旋
      • 右单旋
      • 左右双旋
      • 右左双旋
    • 验证 AVL 树
    • 查找
    • 删除

传统艺能

小编是双非本科大一菜鸟不赘述,欢迎各位指点江山(期待~)(QQ:1319365055)
此前博客点我!点我!请搜索博主 【知晓天空之蓝】

非科班转码社区诚邀您入驻
小伙伴们,打码路上一路向北,彼岸之前皆是疾苦
一个人的单打独斗不如一群人的砥砺前行
这是和梦想合伙人组建的社区,诚邀各位有志之士的加入!!
社区用户好文均加精(“标兵”文章字数2000+加精,“达人”文章字数1500+加精)
直达: 社区链接点我


手撕 AVL 树——C++ 高阶数据结构详解_第1张图片

概念

AVL 树由两位数学家G.M.A delson-Velskii 和 E.M.Landis 发明,AVL 取自这二位名字中的字母。

AVL 树本质上就是一个二叉搜索树,原来的二叉搜索树虽然可以提高搜索效率,但是如果树中的数据是有序或者接近有序的,树就会退回成一个单支树(顺序表),但是在顺序表中数据的查找效率又会变得低下。因此 AVL 树的出现就是为了弥补这个缺陷。

AVL 树可以是空树,而非空树需要具备以下条件才可以:

  1. 左右子树高度差(即平衡因子)绝对值不超过 1;因为只有满二叉树才能做到每个结点左右子树高度之差均为0 ,既然无法做到维持 0 的高度差即退而求其次维持为 1。
  2. 左右子树都是 AVL 树

比如下面就是一个 AVL 树
手撕 AVL 树——C++ 高阶数据结构详解_第2张图片
而下面这个就是非 AVL 树
手撕 AVL 树——C++ 高阶数据结构详解_第3张图片

如果一棵二叉搜索树的高度是平衡的,即树中每个结点左右子树高度之差的绝对值不超过 1。它就是AVL树。如果它有n个结点,其高度可保持在O (log N),搜索时间复杂度也是O (log N)。

AVL 树结构定义

这里使用 BSTree 里面的 kv 模型,简单的 k 模型不再演示,为了方便后续旋转以及节点之间关系的联立,我们需要建立一个三叉链结构,为了维护高度差为 1 ,每个节点代入 _bf 平衡因子进行即时迭代。

template<class K,class V>
struct AVLTreeNode
{
//构造函数将根节点平衡因子初始化为0
	AVLTreeNode(const T& data = T())
		: _pLeft(nullptr)
		, _pRight(nullptr)
		, _pParent(nullptr)
		, _data(data)
		, _bf(0)
	{}

	AVLTreeNode<T,V>* _pLeft;
	AVLTreeNode<T,V>* _pRight;
	AVLTreeNode<T,V>* _pParent;//左右双亲节点组成的三叉链结构
	pair<K,V> _kv;//存储键值对
	int _bf;   // 节点的平衡因子
};

AVL 树每个节点维护平衡因子并不是必须的,只是不使用此方法更为麻烦,比如可以维护一个高度函数每次进行递归计算

数据插入

插入还是先找到需要插入的点,方法和二叉搜索树一样,比根节点小的往左走,比根节点大的往右走,相等节点判定为插入失败,插入完成后更新平衡因子

和二叉搜索树插入不同的就是 AVL 树需要时刻更新平衡因子,当平衡因子绝对值超过 1 就会触发旋转。

我们要明白插入节点后对该节点的祖先节点的影响是最大的,因此平衡因子的更新也不单单是一个节点,他会引发自下而上的一连串更新。正因为是自下而上的更新,因此我们最开始定义的是三叉链,方便通过父指针找到当前 parent 节点的父节点,来进行迭代更新,当然不使用三叉链结构可以考虑用栈存储树的路径,但是这样比较麻烦

手撕 AVL 树——C++ 高阶数据结构详解_第4张图片
为了给平衡因子赋予方向权重去区别左子树和右子树,平衡因子的变化规则就是: 新增节点在右子树则 _bf ++,新增节点在左子树则 _bf –

更新完节点后再对此时的平衡因子值做判断,细分为 3 种情况:

  1. _bf = 0 ,说明之前平衡因子只能是 1 或者 -1,有一边高的情况下加入新节点使树回归平衡
  2. _bf = 1 或 -1,说明之前平衡因子只能是 0,因为是 2 或 -2 不满足树的结构,树从平衡变得一边高
  3. _bf = 2 或 -2,说明之前平衡因子只能是 1 或 -1,由一边高变得一边更高

我们说过新节点加入可能会引发第自下而上的一系列更新,上面 3 种判断分别对应以下情况:

  1. 第一种情况我们不需要做任何更新,parent 节点的平衡因子任然是 0
  2. 第二种情况新节点插入改变了以 parent 为根结点的子树的高度,影响了 parent 父节点的平衡因子,需要进行向上更新
  3. 第三种情况高度差绝对值(平衡因子)已经超过 1 ,则破坏了 AVL 的结构,需要进行旋转矫正。

当然,最坏情况就是自下而上一直更新到根节点为止:
手撕 AVL 树——C++ 高阶数据结构详解_第5张图片

当出现平衡因子为 2、-2 的点就代表需要进行旋转处理,parent 是 当前 cur 节点的双亲节点,因此 parent 为2、-2 时此时 cur 的平衡因子只能是 1、-1,具体情况分为了 4 种

  1. parent 节点为 2,cur 节点为 1,采用左单旋;
  2. parent 节点为 2 ,cur 节点为 -1,采用右左双旋;
  3. parent 节点为 -2,cur 节点为 1,采用左右双旋;
  4. parent 节点为 -2,cur 节点为 -1,采用右单旋;

具体插入功能代码如下:

bool Insert(const pair<K, V>& kv)
{
	if (_root == nullptr) 
	{
		_root = new Node(kv);//空树则插入结点直接作为根结点
		return true;
	}
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (kv.first < cur->_kv.first) //左子树寻找
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (kv.first > cur->_kv.first) //右子树寻找
		{
			parent = cur;
			cur = cur->_right;
		}
		else //key值相等冗余,插入失败
		{
			return false;
		}
	}
	//插入到树中
	cur = new Node(kv); //根据所给值构造一个新结点
	if (kv.first < parent->_kv.first)	//左子树插入
	{
	
		parent->_left = cur;
		cur->_parent = parent;
	}
	else 	//右子树插入
	{
		parent->_right = cur;
		cur->_parent = parent;
	}

	//更新平衡因子
	while (cur != _root) //最坏情况一直更新到根节点
	{
		if (cur == parent->_left) //parent的左子树增高
		{
			parent->_bf--; //parent的平衡因子--
		}
		else if (cur == parent->_right) //parent的右子树增高
		{
			parent->_bf++; //parent的平衡因子++
		}
		//对当前平衡因子情况进行判定
		if (parent->_bf == 0) 
		{
			break; //parent树的高度没有发生变化,不会影响其父结点及以上结点的平衡因子
		}
		else if (parent->_bf == -1 || parent->_bf == 1) 
		{
			//parent树的高度变化,会影响其父结点的平衡因子,需要继续往上更新平衡因子
			cur = parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == -2 || parent->_bf == 2) 
		{
			//需要进行旋转(此时parent树已经不平衡了)
			if (parent->_bf == -2)
			{
				if (cur->_bf == -1)//左子树高了
				{
					RotateR(parent); //触发右单旋
				}
				else //cur->_bf == 1
				{
					RotateLR(parent); //左右双旋
				}
			}
			else //parent->_bf == 2
			{
				if (cur->_bf == -1)//右子树高了
				{
					RotateRL(parent); //右左双旋
				}
				else //cur->_bf == 1
				{
					RotateL(parent); //左单旋
				}
			}
			break; //旋转后一定平衡,无需继续往上更新平衡因子(旋转后树高度变为插入之前的)
		}
		else
		{
			assert(false); //虽然所有情况判断完了,但是为了逻辑严谨这里断言一下false
		}
	}
	return true; //插入成功
}

AVL 树旋转

左单旋

左单旋对应为右边偏高,需要向左调整因此叫做左单旋(这里的红色长方形代表着一个子树):
手撕 AVL 树——C++ 高阶数据结构详解_第6张图片

上图还是诠释的蛮生动的,但是没有过程演示大家细品一下。 60 的左子树 h 一定是比 60 小的,但是 h 在 30 的右子树那么他一定比 30 大,因此我首先将 h 节点旋转到 30 节点的右子树此时依然满足 > 30 && < 60 的条件,在将 30 接在此时空出来 60 的左子树此时依然满足左子树小于 60,在不破坏树原本结构的同时,顺利的将各节点的平衡因子化为了 0

手撕 AVL 树——C++ 高阶数据结构详解_第7张图片
得到上图后开始进行左单旋,具体左单旋就总结为 4 步:

  1. subR 左子树作为 parent 右子树
  2. parent 作为 subR 左子树
  3. 将 subR 定位新的根节点
  4. 更新平衡因子

代码表示为:

		void RotateL(Node* parent)
		{
			Node* SubR = parent->_right;
			Node* SubRL = SubR->_left;
			parent->_right = SubRL;//SubR 左子树作为 parent 右子树
				if (SubRL)//注意SubRL可能为空!
				{
					SubRL->_parent = parent;
				}
			parent->_parent = SubR;//parent 作为 subR 左子树
			SubR->_left = parent;
			Node* Tparent = parent->_parent;//建立Tparent和subR之间的关系
			SubR->_parent = Tparent;
			if (nullptr == Tparent)
			{
				_root == SubR;
				SubR->_parent = nullptr;
			}
			else//Tparent 有意义则需改变父指针指向
			{
				if (parent == Tparent->_left)
					Tparent->_left = SubR;
				else
					Tparent->_right = SubR;
			}
			SubR->_bf = parent->_bf = 0;//更新平衡因子
		}

右单旋

手撕 AVL 树——C++ 高阶数据结构详解_第8张图片

和左单旋一样,得到上图后开始进行右单旋,具体右单旋就总结为 4 步:

  1. 将 SubL 右子树变成 parent 左子树;
  2. parent 变成 SubL 右子树 ;
  3. 将 SubL 作为现在的根节点;
  4. 更新平衡因子;

具体代码如下:

		void RotateR(Node* parent)
		{
			Node* SubL = parent->_left;
			Node* SubLR = SubL->_right;
			parent->_right = SubLR;//将 SubL 右子树变成 parent 左子树
			if (SubLR)
			{
				SubLR->_parent = parent;
			}
			SubL->_right = parent;//parent 变成 SubL 右子树 
			parent->_parent = SubL;
			Node* Tparent = parent->_parent;
			SubL->_parent = Tparent;
			if (Tparent == nullptr)
			{
				_root = SubL;
				SubL->_parent = nullptr;
			}
			else//Tparent 有意义则需改变父指针指向
			{
				if (parent = Tparent->_left)
					Tparent->_left = SubL;
				else
					Tparent->_right = SubL;
			}
			parent->_bf = SubL->_bf = 0;//更新平衡因子
		}

左右双旋

手撕 AVL 树——C++ 高阶数据结构详解_第9张图片
接下来两次旋转是先左旋后右旋,== 左旋==:
手撕 AVL 树——C++ 高阶数据结构详解_第10张图片

右旋

手撕 AVL 树——C++ 高阶数据结构详解_第11张图片
具体步骤总结为 3 步

  1. 以 SubL 为中心进行左旋
  2. 以 parent 为中心进行右旋
  3. 更新平衡因子

在双旋后会出现以下三种情况,他们都会回到插入前的高度,因此无序再向上更新平衡因子!
手撕 AVL 树——C++ 高阶数据结构详解_第12张图片
手撕 AVL 树——C++ 高阶数据结构详解_第13张图片
手撕 AVL 树——C++ 高阶数据结构详解_第14张图片

虽然情况复杂了,但是代码可以直接套用左单旋和右单旋的接口,还是非常简单的,具体代码如下:

	void RotateLR(Node* parent)
	{
		Node* SubL = parent->_left;
		Node* SubLR = SubL->_right;
		int bf = SubLR->_bf;//subLR不可能为nullptr,因为subL的平衡因子是1
  
		RotateL(parent->_left);//以 SubL 为中心进行左旋
		RotateR(parent);//以 parent 为中心进行右旋
		//更新平衡因子
		//区别开三种情况的判断依据就是 SubLR 节点的平衡因子
		if (-1 == bf)
			parent->_bf = 1;
		else if (1 == bf)
			SubL->_bf = -1;
		else if(0 == bf)
		{
			SubL->_bf = 0;
			parent->_bf = 0;
			SubLR->_bf = 0;
		}
		else
	    {
		   assert(false); //在旋转前平衡因子就有问题
	    }
	}

右左双旋

手撕 AVL 树——C++ 高阶数据结构详解_第15张图片
接下来两次旋转是先右旋后左旋,== 右旋==:
手撕 AVL 树——C++ 高阶数据结构详解_第16张图片
左旋
手撕 AVL 树——C++ 高阶数据结构详解_第17张图片
右左双旋总结一下就是三步

  1. 以 SubR 为中心进行右旋
  2. 以 parent 为中心进行左旋
  3. 更新平衡因子

和左右双旋一样分为 3 种情况,但是都不需要进行向上更新:
手撕 AVL 树——C++ 高阶数据结构详解_第18张图片

手撕 AVL 树——C++ 高阶数据结构详解_第19张图片
手撕 AVL 树——C++ 高阶数据结构详解_第20张图片

具体代码如下:

	void RotateRL(Node* parent)
	{
		Node* SubR = parent->_right;
		Node* SubRL = SubR->_left;
		int bf = pSubRL->_bf;

		RotateR(parent->_right);//以 SubR 为中心进行右旋
		RotateL(parent);//以 parent 为中心进行左旋

		// 更新部分节点的平衡因子同左右双旋
		if (bf == -1)
			SubR->_bf = 1;
		else if (bf == 1)
			parent->_bf = -1;
		else if(0 == bf)
		{
			SubL->_bf = 0;
			parent->_bf = 0;
			SubLR->_bf = 0;
		}
		else
	    {
		   assert(false); //在旋转前平衡因子就有问题
	    }
	}

验证 AVL 树

借二叉搜索树的经验,走一波中序遍历看是否得到一个有序序列:

	void _InOrder(Node* pRoot)
	{
		if (pRoot)
		{
			_InOrder(pRoot->_pLeft);
			cout << pRoot->_data << " ";
			_InOrder(pRoot->_pRight);
		}
	}

但是中序遍历依然只能证明他是个能跑的二叉搜索树,最重要的是对 AVL 树的特性——平衡性进行验证!

	bool _IsAVLTree(Node* pRoot)
	{
		if (nullptr == pRoot)
			return true;

		int leftHeight = _Height(pRoot->_pLeft);
		int rightHeight = _Height(pRoot->_pRight);
        //检查该树是否平衡(高度差)
		if (abs(rightHeight - leftHeight) > 1 ||
			rightHeight - leftHeight != pRoot->_bf)//检查节点平衡因子
			return false;

		return _IsAVLTree(pRoot->_pLeft) && _IsAVLTree(pRoot->_pRight);
	}

	size_t _Height(Node* pRoot)
	{
		if (nullptr == pRoot)
			return 0;

		size_t leftHeight = _Height(pRoot->_pLeft);//递归左树
		size_t rightHeight = _Height(pRoot->_pRight);//递归右数

		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;//返回AVL树最大高度
	}

查找

查找就和二叉搜索树别无二样了:

  1. 若树为空树,则查找失败,返回nullptr。
  2. 若key值小于当前结点的值,则应该在该结点的左子树当中进行查找。
  3. 若key值大于当前结点的值,则应该在该结点的右子树当中进行查找。
  4. 若key值等于当前结点的值,则查找成功,返回对应结点。
Node* Find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		if (key < cur->_kv.first) 
		{
			cur = cur->_left; //key值小于该结点的值,左子树当中查找
		}
		else if (key > cur->_kv.first) 
		{
			cur = cur->_right; //key值大于该结点的值,右子树当中查找
		}
		else 
		{
			return cur;
		}
	}
	return nullptr; //查找失败
}

删除

其实 AVL 树的删除比插入还要难还要复杂,出于市面上 99.9% 的公司 99.9% 不会考到的东西,这里就不当砖家去搬弄了,当然我也仔细学习了删除,这里推荐大佬的详细删除方法,有兴趣的自取:
AVL树的删除

aqa 芭蕾 eqe 亏内,代表着开心代表着快乐,ok 了家人们。

你可能感兴趣的