企业官网建设流程全解析

网站收录查询系统,微信咋做自己的网站,wordpress建英文网站,工商局网站实名认证怎么做平衡二叉树#xff08;AVL 树#xff09;通过维护每个节点的平衡因子#xff08;即左右子树高度之差#xff09;来确保整棵树的高度始终接近 $ \log_2 n $#xff0c;从而保障查找、插入和删除操作的时间复杂度稳定在 $ O(\log n) $。当插入或删除节点导致某个节点的平衡因…平衡二叉树AVL 树通过维护每个节点的平衡因子即左右子树高度之差来确保整棵树的高度始终接近 $ \log_2 n $从而保障查找、插入和删除操作的时间复杂度稳定在 $ O(\log n) $。当插入或删除节点导致某个节点的平衡因子绝对值超过 1 时就需要进行旋转调整以恢复平衡。根据失衡情况的不同主要分为四种调整类型图中展示了其中三种典型场景LL 型单向右旋Right Rotation失衡原因在节点 A 的左子树的左子树中插入新节点使得 A 的左子树过高。平衡因子变化A 的平衡因子由 1 变为 2。调整方式将 A 的左孩子 B 提升为新的根节点A 成为 B 的右孩子B 原来的右子树变为 A 的左子树避免断开连接。效果整体高度降低B 和 A 的平衡因子均变为 0子树恢复平衡。defright_rotate(A):BA.left A.leftB.right B.rightA# 更新高度A.heightmax(height(A.left),height(A.right))1B.heightmax(height(B.left),height(B.right))1returnB# 新的根RR 型单向左旋Left Rotation失衡原因在节点 A 的右子树的右子树中插入新节点导致 A 的右子树过高。平衡因子变化A 的平衡因子由 -1 变为 -2。调整方式将 A 的右孩子 B 提升为新的根A 成为 B 的左孩子B 原来的左子树变为 A 的右子树。效果恢复平衡B 和 A 的平衡因子均为 0。defleft_rotate(A):BA.right A.rightB.left B.leftA# 更新高度A.heightmax(height(A.left),height(A.right))1B.heightmax(height(B.left),height(B.right))1returnB# 新的根LR 型先左后右双向旋转Left-Right Rotation失衡原因在 A 的左子树的右子树插入节点造成“折线型”失衡。平衡因子变化A 的平衡因子由 1 变为 2但其左孩子 B 的平衡因子为 -1。调整逻辑对 A 的左孩子 B 执行左旋转化为 LL 型再对 A 执行右旋。效果中间节点 C 成为新根整棵子树恢复平衡。defleft_right_rotate(A):A.leftleft_rotate(A.left)returnright_rotate(A)注还有一种对称情况是RL 型先右旋再左旋用于处理右子树的左子树插入导致的失衡。背景拓展总结AVL 树作为最早的自平衡二叉搜索树之一核心优势在于严格的平衡条件平衡因子 ∈ {-1, 0, 1}每次插入最多触发一次路径上的旋转即可恢复平衡查找效率极高适合读多写少的场景相较于普通二叉排序树避免了退化成链表的风险。虽然由于频繁旋转带来一定开销现代应用中红黑树更常见但 AVL 树仍是理解自平衡机制的重要基础。RL型失衡是AVL树中四种不平衡情况之一属于“折线型”插入导致的失衡。✅失衡产生原因RL型Right-Left Case发生在在节点 A 的右子树的左子树中插入一个新节点导致 A 的平衡因子从 -1 变为 -2。具体结构如下节点 A 的右孩子为 B节点 B 的左孩子为 C新节点插入到 C 的子树中左侧或右侧这种插入方式使得 A 的右子树高度显著增加但路径为“先右再左”形成折线形态称为 RL 型。此时A 的平衡因子 左子树高 - 右子树高 h - (h2) -2失衡B 的平衡因子通常为 1因为C是B的左孩子且较重✅调整方法先右旋再左旋双向旋转步骤分解对 B 进行单向右旋Right Rotation将 B 的左孩子 C 提升B 的左子树变为 C 的右子树C 的右子树接回 B 作为其左子树此步将 RL 型转换为 RR 型对 A 进行单向左旋Left Rotation将 C已提升作为新的根节点A 成为 C 的左孩子完成平衡恢复。最终结果以 C 为根的新子树左右高度一致所有节点恢复平衡。defright_left_rotate(A):# 第一步对右孩子 B 进行右旋处理 RL → RRA.rightright_rotate(A.right)# 第二步对当前节点 A 进行左旋returnleft_rotate(A)✅调整效果子树整体高度降低根节点变为原中间节点 C所有涉及节点的平衡因子恢复至合理范围-1, 0, 1时间复杂度仍为 $ O(\log n) $仅需常数时间完成两次旋转。 示例图示文字描述A (-2) A (-2) \ \ B (1) 插入后 → B / / C C / \ / \ [新节点] ... → 先对 B 右旋 → 得到 A (-2) \ C / \ B ... / ... → 再对 A 左旋 → 得到 C (0) / \ A B / / ...