欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 科技 > 能源 > 如何在AVL树中高效插入并保持平衡:一步步掌握旋转与平衡因子 —— 平衡因子以及AVL结构篇

如何在AVL树中高效插入并保持平衡:一步步掌握旋转与平衡因子 —— 平衡因子以及AVL结构篇

2025/3/16 23:40:33 来源:https://blog.csdn.net/ZWW_zhangww/article/details/146273930  浏览:    关键词:如何在AVL树中高效插入并保持平衡:一步步掌握旋转与平衡因子 —— 平衡因子以及AVL结构篇

文章目录

  • AVL树的概念
  • AVL树的结构
  • AVL树的插入
  • 平衡因子更新终止条件
  • 插入以及平衡因子的保持
  • AVL树的查找

AVL树的概念

AVL树(Adelson-Velsky and Landis Tree)是一种自平衡二叉查找树,它的特点是每个节点的左子树和右子树的高度差不能超过1。这意味着AVL树是一种平衡的二叉树,通过保持树的平衡来保证查找操作的时间复杂度为O(log n),从而提高性能。

AVL树当中,重要的一个概念:

  • 平衡因子(Balance Factor, BF): 每个节点都有一个平衡因子,定义为节点的左子树高度减去右子树高度。(当然,右子树的高度减去左子树的高度也是可以的)平衡因子的值只能是-1、0或1。

  • 今天这篇文章,作者定义的平衡因子是 bf = rh(right height) - lh(left height);即选择右子树高度减去左子树高度

AVL树的结构

在这里插入图片描述

template<class K, class V>
struct AVLTreeNode 
{// 每个节点包含的元素和指针pair<K, V> _kv;           // 存储键值对AVLTreeNode<K, V>* _left;  // 左子树指针AVLTreeNode<K, V>* _right; // 右子树指针AVLTreeNode<K, V>* _parent; // 父节点指针int _bf;                   // 平衡因子// 构造函数AVLTreeNode(const pair<K, V>& kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};template<class K, class V>
class AVLTree 
{typedef AVLTreeNode<K, V> Node;  // 节点类型
public:// 其他操作(插入、删除、查找等)可以在此添加//	旋转/**/   旋转的详细讲解在下一篇文章,有兴趣的读者可以前往下一篇进行查看**private:Node* _root;  // 根节点指针
};

AVL树的插入

重点关注如何在插入时保持树的平衡。

插入操作概述
AVL树插入操作的过程与普通的二叉搜索树插入过程相似,唯一不同的是,AVL树在插入节点后需要检查树的平衡性,并进行必要的旋转操作来保持平衡。我们可以将插入操作分为几个步骤:

  1. 二叉搜索树的插入:按照二叉搜索树的规则插入节点。
  2. 更新节点高度:插入节点后,需要更新沿路径的所有节点的高度。
  3. 检查平衡因子:检查每个节点的平衡因子,确定是否需要进行旋转。
  4. 旋转操作:如果某个节点的平衡因子不在-1, 0, 1范围内,进行旋转以恢复平衡。

平衡因子更新终止条件

  • 更新后parent的平衡因⼦等于0,更新中parent的平衡因⼦变化为-1->0或者1->0,说明更新前parent⼦树⼀边⾼⼀边低,新增的结点插⼊在低的那边,插⼊后parent所在的⼦树⾼度不变,不会影响parent的⽗亲结点的平衡因⼦,更新结束。
  • 更新后parent的平衡因⼦等于1或 -1,更新前更新中parent的平衡因⼦变化为0->1或者0->-1,说明更新前parent⼦树两边⼀样⾼,新增的插⼊结点后,parent所在的⼦树⼀边⾼⼀边低,parent所在的⼦树符合平衡要求,但是⾼度增加了1,会影响arent的⽗亲结点的平衡因⼦,所以要继续向上更新。
  • 更新后parent的平衡因⼦等于2 或 -2,更新前更新中parent的平衡因⼦变化为1->2 或者 -1->-2,说明更新前parent⼦树⼀边⾼⼀边低,新增的插⼊结点在⾼的那边,parent所在的⼦树⾼的那边更⾼了,破坏了平衡,parent所在的⼦树不符合平衡要求,需要旋转处理,旋转的⽬标有两个:1、把parent⼦树旋转平衡。2、降低parent⼦树的⾼度,恢复到插⼊结点以前的⾼度。所以旋转后也不需要继续往上更新,插⼊结束。

平衡因子更新的3种情况。

更新到10结点,平衡因⼦为2,10所在的⼦树已经不平衡,需要旋转处理
在这里插入图片描述
更新到中间结点,3为根的⼦树⾼度不变,不会影响上⼀层,更新结束
在这里插入图片描述
最坏更新到根停⽌
在这里插入图片描述

插入以及平衡因子的保持

	bool Insert(const pair<K, V>& kv) {if (_root == nullptr) {_root = new Node<K, V>(kv);return true;}Node<K, V>* parent = nullptr;Node<K, V>* cur = _root;// 寻找插入位置while (cur) {parent = cur;if (kv.first < cur->_kv.first) {cur = cur->_left;} else if (kv.first > cur->_kv.first) {cur = cur->_right;} else {return false;  // 键值已存在}}// 创建新的节点并连接到父节点cur = new Node<K, V>(kv);if (kv.first < parent->_kv.first) {parent->_left = cur;} else {parent->_right = cur;}cur->_parent = parent;// 更新平衡因子并处理不平衡while (parent) {if (cur == parent->_left) {parent->_bf--;  // 左子树高,平衡因子减1} else {parent->_bf++;  // 右子树高,平衡因子加1}//平衡因子 = 右子树 - 左子树// 如果平衡因子为0,结束更新if (parent->_bf == 0) {break;}// 如果平衡因子为±1,继续向上更新if (parent->_bf == 1 || parent->_bf == -1) {cur = parent;parent = parent->_parent;}// 如果平衡因子为±2,说明不平衡,进行旋转处理else if (parent->_bf == 2 || parent->_bf == -2) {// 旋转处理/**/   旋转的详细讲解在下一篇文章,有兴趣的读者可以前往下一篇进行查看**if (parent->_bf == -2 && cur->_bf == -1)//左高(在左子树)——右旋{RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1)//右高(在左子树)——左旋{RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1)//左高(在右子树)——左右旋{RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1)//右高(在左子树)——右左旋{RotateRL(parent);}else{assert(false);}break;} else {assert(false);  // 应该不会发生}}return true;}

AVL树的查找

⼆叉搜索树逻辑实现即可,搜索效率为 O(logN)

Node* Find(const K& key)
{// 从根节点开始查找Node* cur = _root;// 遍历树,直到找到目标节点或到达空节点while (cur){// 如果当前节点的键小于目标键,向右子树查找if (cur->_kv.first < key){cur = cur->_right;}// 如果当前节点的键大于目标键,向左子树查找else if (cur->_kv.first > key){cur = cur->_left;}// 如果当前节点的键等于目标键,返回当前节点else{return cur;}}// 如果遍历结束仍未找到目标节点,返回 nullptrreturn nullptr;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词