瑜伽 网站模板,慈溪网站制作哪家最便宜,wordpress读取菜单,医疗网站建设网站文章目录 前言 AVL树为什么要旋转#xff1f;一、插入一个值的大概过程1. 插入一个值的大致过程2. 平衡因子更新原则3. 旋转处理的目的 二、左单旋1. 左单旋旋转方式总处理图2. 左单旋具体会遇到的情况3. 左单旋代码总结 三、右单旋1. 右单旋旋转方式总处理图2. 右单旋具体会遇… 文章目录 前言 AVL树为什么要旋转一、插入一个值的大概过程1. 插入一个值的大致过程2. 平衡因子更新原则3. 旋转处理的目的 二、左单旋1. 左单旋旋转方式总处理图2. 左单旋具体会遇到的情况3. 左单旋代码总结 三、右单旋1. 右单旋旋转方式总处理图2. 右单旋具体会遇到的情况3. 右单旋代码总结 四、双旋1. 右左双旋旋转逻辑2. 右左双旋可能会遇到的问题辨析3. 右左双旋平衡因子的处理4. 右左双旋代码总结 五、左右双旋总结 前言 AVL树为什么要旋转
AVL树需要旋转是为了保持平衡。当插入或删除节点后某些子树的高度差超过1就会破坏AVL树的平衡性。为了让树重新平衡避免一边过高、一边过低的情况旋转可以调整节点的位置使树保持左右高度差不超过1。这样做的目的是确保查找、插入、删除操作的效率始终保持在 O(log₂ n)。简单来说旋转就是“调位置让树站得更稳”。 一、插入一个值的大概过程
1. 插入一个值的大致过程 按照二叉搜索树规则插入 插入的新节点位置依据二叉搜索树的性质确定即小于当前节点放左子树大于当前节点放右子树。 更新平衡因子 新增节点后只会影响其祖先节点的高度可能导致部分祖先节点的平衡因子发生变化。从新增节点向根节点逐步更新平衡因子。如果在更新过程中某节点的平衡因子变为2或-2说明该节点的子树已经不平衡需要旋转处理否则插入结束。 检查平衡并调整 如果更新平衡因子的过程中没有发现问题平衡因子均为0、1或-1插入操作完成。如果出现不平衡则对不平衡的子树进行旋转处理。旋转不仅恢复子树的平衡还会降低子树的高度确保不再影响其父节点的平衡因子从而结束插入过程。 2. 平衡因子更新原则 平衡因子公式 只有子树高度发生变化时才会影响当前节点的平衡因子。 更新规则 若新增节点在父节点的右子树则父节点的平衡因子增加11。若新增节点在父节点的左子树则父节点的平衡因子减少1-1。 更新停止条件 平衡因子变为0 父节点平衡因子从 -1 变为 0 或从 1 变为 0说明新增节点插入到高度较低的一侧子树高度未改变更新过程可以停止。平衡因子变为1或-1 父节点平衡因子从 0 变为 1 或从 0 变为 -1说明新增节点插入后子树高度增加但仍符合平衡要求需继续向上更新。平衡因子变为2或-2 父节点平衡因子从 1 变为 2 或从 -1 变为 -2说明子树高度过高已失去平衡需要进行旋转处理。 3. 旋转处理的目的
恢复平衡 通过单旋转或双旋转调整节点位置使当前子树符合平衡要求。降低子树高度 旋转后子树高度恢复到插入前的水平确保不会对更高层节点产生影响插入过程结束。 二、左单旋
形成条件parent-_bf 2 cur-_bf 1
1. 左单旋旋转方式总处理图 失衡检测 当插入的新节点导致父节点的平衡因子为 2并且新节点被插入到右子树的右侧时发生右右失衡RR失衡。 旋转操作 左单旋的核心目标是将父节点的右子树即失衡节点的右子树根提升为新的根节点并将原来的父节点挂接到新根节点的左子树上。
parent-right cur-left; // 将右子树的左子树挂接到父节点的右子树
cur-left parent; // 将父节点挂接为右子树的左子树处理父节点链接问题 需要确保旋转后父节点的父节点如果存在正确地连接到新的根节点。 如果原父节点有父节点即不是根节点则要更新父节点的左右子树指向新的根节点。如果原父节点是根节点则更新树的根节点。 更新平衡因子 旋转后原父节点和新的根节点的平衡因子都应设置为 0因为旋转使得这两颗子树已经平衡。 旋转结束 完成旋转后新的根节点成为子树的根树恢复平衡。 2. 左单旋具体会遇到的情况
我们具体会遇到比如 h 0 h 1, h 2 …无穷多种情况
分析如下: 3. 左单旋代码总结
// 左单旋
void RotateL(Node* parent)
{Node* cur parent-_right;Node* curleft cur-_left;// 重新链接parent-_right curleft;if (curleft) // 如果curleft存在{curleft-_parent parent;}cur-_left parent;Node* ppnode parent-_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;
}三、右单旋
形成条件parent-_bf -2 cur-_bf -1
1. 右单旋旋转方式总处理图
右单旋处理的方式与左单旋是一致的只不过是反过来了就不多介绍了。 失衡检测 当插入的新节点导致父节点的平衡因子为 -2并且新节点被插入到左子树的左侧时发生左左失衡LL失衡。 旋转操作 右单旋的核心目标是将父节点的左子树即失衡节点的左子树根提升为新的根节点并将原来的父节点挂接到新根节点的右子树上。
parent-left cur-right; // 将左子树的右子树挂接到父节点的左子树
cur-right parent; // 将父节点挂接为左子树的右子树处理父节点链接问题 需要确保旋转后父节点的父节点如果存在正确地连接到新的根节点。 如果原父节点有父节点即不是根节点则要更新父节点的左右子树指向新的根节点。如果原父节点是根节点则更新树的根节点。 更新平衡因子 旋转后原父节点和新的根节点的平衡因子都应设置为 0因为旋转使得这两颗子树已经平衡。 旋转结束 完成旋转后新的根节点成为子树的根树恢复平衡。 2. 右单旋具体会遇到的情况 3. 右单旋代码总结
// 右单旋
void RotateR(Node* parent)
{Node* cur parent-_left;Node* curright cur-_right;parent-_left curright;if (curright){curright-_parent parent;}cur-_right parent;Node* ppnode parent-_parent;if (ppnode nullptr){cur-_parent nullptr;_root cur;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}// 改变平衡因子parent-_bf cur-_bf 0;
}四、双旋
1. 右左双旋旋转逻辑
形成条件parent-_bf 2 cur-_bf -1
这里是右左双旋的处理方式 插入新节点以cur进行右单旋以parent进行左单旋 2. 右左双旋可能会遇到的问题辨析
h 0 的情况
h 1 的情况
h 2 的情况 3. 右左双旋平衡因子的处理
右左双旋的平衡因子与前面的单旋的平衡因子处理方式不同单旋平衡因子再旋转过后全都是0但是双旋的平衡因子不一样。 它分为以下三种情况 h 0 的情况及curleft._bf 0 结果——parent._bf 0cur._bf 0curleft._bf 0 h 0 的情况下及curleft._bf 1 以以下C位置插入引发的旋转。 结果 parent._bf -1cur._bf 0curleft._bf 0 h 0 的情况下及curleft._bf -1 以以下B位置插入引发的旋转。 结果 parent._bf 0cur._bf 1curleft._bf 0 4. 右左双旋代码总结
// 右左双旋
void RotateRL(Node* parent)
{Node* cur parent-_right;Node* curleft cur-_left;int bf curleft-_bf;// 右旋RotateR(cur);// 左旋RotateL(parent);// 调整平衡因子if (bf 0){parent-_bf 0;cur-_bf 0;curleft-_bf 0;}else if (bf 1){parent-_bf -1;cur-_bf 0;curleft-_bf 0;}else if (bf -1){parent-_bf 0;cur-_bf 1;curleft-_bf 0;}else{assert(false);}
}五、左右双旋
形成条件parent-_bf -2 cur-_bf 1
左右双旋与右左双旋类型就是反过来的过程~ // 左右双旋
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;}
}总结
那么到这里就结束啦
通过学习AVL树的旋转机制我们不仅掌握了数据结构平衡的重要性更感受到了算法的巧妙与严谨。
如果对您有帮助的话麻烦点一个一键三连谢谢啦~
