济宁市网站建设_网站建设公司_Oracle_seo优化

1. 二叉排序树的结点删除（左、右子树均不空的情况）
   当待删除结点 *p 同时具有左、右子树时，为保证中序遍历仍有序，不能简单地将其某一子树连接至父节点。通常采用以下两种策略之一：

• 方法一：用中序直接前驱替代
  找到 *p 的中序直接前驱 *s（即左子树中最右侧的结点），将 *s 的值赋给 *p，然后删除结点 *s。由于 *s 是左子树最右下的结点，其必无右孩子，因此删除 *s 属于“最多一个孩子”的情况，易于处理。

• 方法二：用中序直接后继替代
  类似地，也可使用 *p 的中序直接后继 *s（右子树中最左侧的结点），用其值替换 *p，再删除 *s。此时 *s 必无左孩子，同样便于删除。

核心作用：通过替代法，将“双分支结点删除”转化为“单分支或叶子结点删除”，从而在删除后依然保持二叉排序树的中序有序性。

2. 平衡二叉树（AVL 树）
   平衡二叉树是一种特殊的二叉排序树，满足以下条件：

• 它是空树，或者它的左右子树都是平衡二叉树；
• 左右子树的高度差不超过 1（即 |BF| ≤ 1）；

每个结点的平衡因子 BF = 左子树高度 - 右子树高度，仅取 -1、0、1 三种值。

插入操作后的调整机制：
当插入新结点导致某个结点的 |BF| > 1 时，从该结点向下回溯，找到“最小不平衡子树”（距离根最远的不平衡结点作为根的子树），根据插入位置进行四种旋转操作恢复平衡：

• LL 型：左左，右旋
• RR 型：右右，左旋
• LR 型：左右，先左旋再右旋
• RL 型：右左，先右旋再左旋

核心目的：避免普通二叉排序树因数据有序插入而导致退化成链表（最坏查找时间复杂度 O(n)），通过动态调整维持树高接近 log₂n，使查找、插入、删除的时间复杂度稳定在 O(log n)。

补充说明：
二叉排序树本质上是一种“边插入边排序”的数据结构，而平衡二叉树在此基础上引入了自平衡机制，提升了整体性能稳定性，尤其适用于频繁查找的应用场景。
在二叉排序树中删除一个有两个孩子的结点时，选择中序前驱或后继进行替代，是为了在删除操作后依然保持二叉排序树的中序遍历有序性。这是由二叉排序树的定义和中序遍历的特性决定的。

原因分析：

二叉排序树（BST）满足以下性质：

• 对任意结点，其左子树中所有结点值均小于该结点值；
• 其右子树中所有结点值均大于该结点值；
• 中序遍历结果是一个递增有序序列。

当要删除的结点 *p 有左右两个非空子树时，若直接将其从树中移除，会导致结构断裂，难以简单地用某一子树替代而不破坏BST性质。

为什么选择中序前驱或后继？

1. 中序前驱：是比当前结点值小的最大值，即左子树中最右边的结点（最大值），其右子树为空。
2. 中序后继：是比当前结点值大的最小值，即右子树中最左边的结点（最小值），其左子树为空。

这两个结点的特点是：

• 它们都是“只有一个孩子或无孩子”的结点（因为是最左/最右），便于后续删除；
• 它们的值恰好位于被删结点值的“邻接位置”，能保证替换后的值仍符合BST的大小关系。

通过将 *p 的值替换为其中序前驱或后继的值，再删除那个前驱或后继结点，相当于“逻辑上删除”了原结点的值，而物理上只删除了一个易于处理的结点，从而既维持了树的结构完整性，又保持了中序有序性。

✅ 举例说明：
假设结点 *p 的值为 15，左子树最大值（前驱）是 14，右子树最小值（后继）是 16。
将 14 或 16 替换到 15 的位置后，整个树中仍然满足：左 < 根 < 右，中序序列依然有序。

因此，选择中序前驱或后继替代，是一种既能简化删除操作，又能严格维护BST性质的最优策略。

# 示例：用中序后继替代法删除双孩结点defdelete_node_with_two_children(root,target):# 找到目标结点 p 和其父节点p=root.find(target)ifp.leftandp.right:# 找中序后继 s 及其父节点 parent_ss=p.rightwhiles.left:parent_s=s s=s.left# 将后继的值赋给 pp.val=s.val# 删除后继 s（最多一个右孩子）ifparent_s.left==s:parent_s.left=s.rightelse:parent_s.right=s.right