C++漫步结构与平衡的殿堂：AVL树

06-02 1008阅读

文章目录

  • 1.AVL树的概念
  • 2.AVL树的结构
  • 3.AVL树的插入
  • 4.AVL树的旋转
    • 4.1 左单旋
    • 4.2 右单旋
    • 4.3 右左双旋
    • 4.4 左右双旋
    • 5.AVL树的删除
    • 6.AVL树的高度
    • 7.AVL树的平衡判断
    • 希望读者们多多三连支持
    • 小编会继续更新
    • 你们的鼓励就是我前进的动力！

      二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成 O(N)，因此 map、set 等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现

      1.AVL树的概念

      C++漫步结构与平衡的殿堂：AVL树

      我们已经从多种树型结构走到现在，每一次变化都是为了提高搜索的效率，即时间复杂度

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

      那么什么是AVL树呢？

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

      C++漫步结构与平衡的殿堂：AVL树

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

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

        二叉搜索树在理想情况下时间复杂度与二叉平衡搜索树相同，均为 O ( l o g 2 n ) O(log_2 n) O(log2​n)，但在极端情况下二叉平衡搜索树优于二叉搜索树，因为二叉平衡搜索树会自己调整平衡（后面会详细解释）

        为什么是严格的绝对值为 1，不是 0 或者更大的数字？

        若要求高度差为 0，即严格平衡，树的结构会过于 rigid（僵化）。每次插入或删除节点都可能需要大量调整操作，导致性能下降。允许高度差为 1，在保持较好平衡性的同时，减少了不必要的调整

        若允许高度差为 2，树的平衡性会明显下降，可能出现一侧子树比另一侧高很多的情况，导致查找等操作的时间复杂度增加

        所以平衡因子为 1 是最合适的

        2.AVL树的结构

        template
struct AVLTreeNode
{
	pair _kv;
	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent;
	int _bf;
	AVLTreeNode(const pair& kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
	{ }
};
        • pair _kv：用于存储键值对，pair 是 C++ 标准库中的一个模板类，可将两个不同类型的值组合在一起
        • AVLTreeNode* _left：指向左子节点的指针
        • AVLTreeNode* _right：指向右子节点的指针
        • AVLTreeNode* _parent：指向父节点的指针，这在调整树的平衡时很有用
        • int _bf：平衡因子（Balance Factor），用来记录该节点左右子树的高度差。平衡因子为 0 时表示左右子树高度相等；为 1 时表示右子树比左子树高 1；为 -1 时表示左子树比右子树高 1

          3.AVL树的插入

          	typedef AVLTreeNode Node;
public:
	bool Insert(const pair& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		//寻找节点插入位置
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_kv.first _right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
			//链接插入节点与AVL树
			cur = new Node(kv);
			if (parent->_kv.first _right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			cur->_parent = parent;
			//调整平衡因子
			while (parent)
			{
				if (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)
				{
					//旋转调整（...）
				}
				else
				{
					assert(false);
				}
			}
			return true;
	}

          AVL 树的插入和二叉搜索树是很像的，先根据左大右小的原则，寻找插入节点的位置，然后判断父母节点与插入节点的关系，连接新节点，唯一不同的地方是平衡因子调节的部分，高度差是由右子树减去左子树得出的，可以总结出以下方法：

          🚩 (1)新增在左，parent平衡因子减减

          C++漫步结构与平衡的殿堂：AVL树

          🚩 (2)新增在右，parent平衡因子加加

          C++漫步结构与平衡的殿堂：AVL树

          🚩 (3)更新后parent平衡因子 == 0

          说明 parent 所在的子树的高度不变，不会影响祖先，不用再继续沿着到 root 的路径往上更新，然后循环结束

          🚩 (4)更新后parent平衡因子 == 1 or -1

          说明 parent 所在的子树的高度变化，会影响祖先，需要继续沿着到 root 的路径往上更新，循环继续

          🚩 (5)更新后parent平衡因子 == 2 or -2

          说明 parent 所在的子树的高度变化且不平衡，需要对parent所在子树进行旋转，让他平衡，然后循环结束

          🔥值得注意的是： 如果平衡因子出现比 2 还大，比 -2 还小的数，说明之前的插入就已经出问题了

          4.AVL树的旋转

          4.1 左单旋

          void RotateL(Node* parent)
{
	Node* cur = parent->_right;
	Node* curleft = cur->_left;
	parent->_right = curleft;
	if (curleft)
	{
		curleft->_parent = parent;
	}
	cur->_left = parent;
	Node* ppnode = parent->_parent;
	parent->_parent = cur;
	if (parent == _root)
	{
		_root = cur;
		cur->_parent = nullptr;
	}
	else
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = cur;
		}
		else
		{
			ppnode->_right = cur;
		}
		cur->_parent = ppnode;
	}
	parent->_bf = cur->_bf = 0;
}

          以下将根据一个图例来解释如何进行的左单旋：

          C++漫步结构与平衡的殿堂：AVL树

          左单旋顾名思义就是右子树太长，需要向左旋转形成平衡，平衡因子为 2 的节点定为 parent，其右节点为 cur，cur 的左节点为 curleft

          1. 调整 parent 的右子节点： 把 parent 的右子节点设置成 curleft，若 curleft 不为空，就把 curleft 的父节点设置成 parent
          2. 调整 cur 的左子节点： 把 cur 的左子节点设置成 parent，ppnode 为 parent 的父节点，把 parent 的父节点设置成 cur
          3. 调整根节点或者 ppnode 的子节点： 若 parent 是根节点，那就把 cur 设为新的根节点，并且将 cur 的父节点设为 nullptr。若 parent 不是根节点，就依据 parent 是 ppnode 的左子节点还是右子节点，来更新 ppnode 的相应子节点为 cur，同时把 cur 的父节点设为 ppnode

          4.2 右单旋

          void RotateR(Node* parent)
{
	Node* cur = parent->_left;
	Node* curright = cur->_right;
	parent->_left = curright;
	if (curright)
	{
		curright->_parent = parent;
	}
	Node* ppnode = parent->_parent;
	cur->_right = parent;
	parent->_parent = cur;
	if (ppnode == nullptr)
	{
		_root = cur;
		cur->_parent = nullptr;
	}
	else
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = cur;
		}
		else
		{
			ppnode->_right = cur;
		}
		cur->_parent = ppnode;
	}
	parent->_bf = cur->_bf = 0;
}

          和左单旋类似，这里就不详细解释了

          C++漫步结构与平衡的殿堂：AVL树

          4.3 右左双旋

          void RotateRL(Node* parent)
{
	Node* cur = parent->_right;
	Node* curleft = cur->_left;
	int bf = curleft->_bf;
	RotateR(parent->_right);
	RotateL(parent);
	if (bf == 0)
	{
		cur->_bf = 0;
		curleft->_bf = 0;
		parent->_bf = 0;
	}
	else if (bf == 1)
	{
		cur->_bf = 0;
		curleft->_bf = 0;
		parent->_bf = -1;
	}
	else if (bf == -1)
	{
		cur->_bf = 1;
		curleft->_bf = 0;
		parent->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

          右左双旋适用于新节点插入较高右子树的左侧的情况

          C++漫步结构与平衡的殿堂：AVL树

          30 为 parent 节点，90 为 cur 节点，60 为 curleft 节点

          先以 90 进行右单旋，再以 30 进行左单旋

          双旋的重点是平衡节点的调整，根据多个例子可以知道，主要是看 curleft 节点的平衡因子

          C++漫步结构与平衡的殿堂：AVL树

          如果原来 curleft 平衡因子为 0 ，即 curleft 为新增节点导致的双旋，那么 curleft、cur、parent 平衡因子都为 0

          C++漫步结构与平衡的殿堂：AVL树

          如果原来 curleft 平衡因子为 1 ，即在 curleft 右边新增，那么 cur 和 curleft 平衡因子都为 0，parent 的平衡因子为 1

          C++漫步结构与平衡的殿堂：AVL树

          如果原来 curleft 平衡因子为 -1 ，即在 curleft 左边新增，那么 parent 和 curleft 平衡因子都为 0，cur 的平衡因子为 1

          4.4 左右双旋

          void RotateLR(Node* parent)
{
	Node* cur = parent->_left;
	Node* curright = cur->_right;
	int bf = curright->_bf;
	RotateL(parent->_left);
	RotateR(parent);
	if (bf == 0)
	{
		parent->_bf = 0;
		cur->_bf = 0;
		curright->_bf = 0;
	}
	else if (bf == -1)
	{
		parent->_bf = 1;
		cur->_bf = 0;
		curright->_bf = 0;
	}
	else if (bf == 1)
	{
		parent->_bf = 0;
		cur->_bf = -1;
		curright->_bf = 0;
	}
}

          和右左双旋类似，这里就不详细解释了

          C++漫步结构与平衡的殿堂：AVL树

          5.AVL树的删除

          在实际开发中，虽然 AVL 树是一种自平衡的二叉搜索树，但其删除操作通常不被优先实现

          AVL 树的核心特性是通过旋转操作（左旋、右旋、左右旋、右左旋）来保证树的高度平衡。在插入操作中，仅需从插入节点向上回溯至根节点，检查并调整路径上节点的平衡因子，最多进行两次旋转操作就能恢复树的平衡。然而，删除操作后，平衡的破坏可能会沿着从删除节点到根节点的路径向上传播，导致需要多次旋转操作来恢复平衡。这使得删除操作的实现逻辑变得异常复杂，需要仔细处理各种可能的情况

          而且实现插入删除一般会使用 红黑树、B树 等更优的数据结构

          6.AVL树的高度

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

          比较左子树和右子树的高度，取较大值并加 1（加上当前根节点），得到当前子树的高度

          7.AVL树的平衡判断

          bool IsBalance(Node* root)
{
	if (root == nullptr)
		return true;
	int leftHight = Height(root->_left);
	int rightHight = Height(root->_right);
	if (rightHight - leftHight != root->_bf)
	{
		cout _right);
}

          每遍历一个节点就对其左右子树的高度进行计算，然后判断是否绝对值小于 2

          总结： AVL 树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过 1，这样可以保证查询时高效的时间复杂度，即 l o g 2 ( N ) log_2 (N) log2​(N)。但是如果要对 AVL 树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑 AVL 树，但一个结构经常修改，就不太适合

          希望读者们多多三连支持

          小编会继续更新

          你们的鼓励就是我前进的动力！

          C++漫步结构与平衡的殿堂：AVL树

免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们。

相关阅读

目录[+]

取消
微信二维码
微信二维码
支付宝二维码