基于增广二叉搜索树的O(1)MIN/MAX操作实现及删除逻辑优化咨询

现有实现的核心bug #

• TRANSPLANT函数存在传值失效问题：函数入参的根节点为值传递，当被删除节点是根节点时，对根指针的修改仅在函数局部作用域生效，无法同步更新全局根节点，所有根节点删除流程会直接失效。
• fixMax函数存在类型使用错误：函数内部直接将传入的二级指针node赋值给遍历变量current，没有正确解引用，导致父节点遍历流程中全部为野指针访问，完全无法完成max值的回溯更新。
• 删除流程的fix调用触发逻辑冗余：当前删除分支累计触发4次fix调用，大量触发场景不存在对应的极值变更，属于无效遍历。
• 删除双孩子分支的fix触发时机错误：当临时后继节点和被删节点不相邻时，对临时节点右子树触发fixMin之后，没有同步处理临时节点挪位后的max值回溯，容易出现max指针指向错误。

DELETE流程的优化设计 #

首先明确增广节点的核心约束：每个节点的min指针，指向以该节点为根的子树中的最小键值节点；每个节点的max指针，指向以该节点为根的子树中的最大键值节点。
基于这个约束，可以把当前多次分散的fix调用合并为统一的回溯逻辑，完全不需要拆分多次触发：

1. 先修正TRANSPLANT为二级指针传参版本，保证根节点替换时能正确更新全局根指针。
2. 梳理不同删除场景的fix需求：
   • 当被删节点无右孩子时，用左子树替换被删节点。此时仅左分支的最小可能发生变化，只需要从替换后的节点开始，沿着“当前节点是父节点左孩子”的链路向上回溯，同步更新沿途父节点的min值，遇到第一个不是左分支的父节点就停止，全程只需要一次fixMin遍历，不需要额外触发fixMax。
   • 当被删节点无左孩子时，用右子树替换被删节点。此时仅右分支的最大可能发生变化，只需要从替换后的节点开始，沿着“当前节点是父节点右孩子”的链路向上回溯，同步更新沿途父节点的max值，遇到第一个不是右分支的父节点就停止，全程只需要一次fixMax遍历，不需要额外触发fixMin。
   • 当被删节点同时有左右孩子时，取被删节点的中序后继临时节点替换被删节点：
     • 临时节点原本位置被它的右子树替换的过程，仅会影响临时节点原位置所在左分支的最小值，只需要对替换后的右子树触发一次fixMin遍历。
     • 临时节点挪到被删节点位置后，可以直接通过左右子节点的min/max值给自己赋值：如果存在左孩子就取左孩子的min作为自身min，没有左孩子就取自身为min；如果存在右孩子就取右孩子的max作为自身max，没有右孩子就取自身为max。
     • 最后从临时节点的位置沿着父链向上，同时同步更新沿途对应方向的min和max值即可，全程仅需要两次fix遍历，对比当前的4次调用减少一半冗余。
3. 把原来分散的fixMin、fixMax调用统一封装成一个回溯函数，通过传入需要更新的方向标识，避免代码重复。

其他代码优化建议 #

• 插入流程的同步修正：把当前仅在当前递归层更新极值的逻辑，改成从新插入的叶子节点开始，按照统一回溯规则同步更新所有父节点的min/max值，从根源避免中间层极值指针失效的问题。
• 减少冗余比较：回溯更新极值时，不需要每一层都遍历找子树最值，只需要沿着单侧父链同步指针值即可，因为子树内部的极值在插入fix的时候已经同步到当前替换节点上，直接赋值就能保证正确性。
• 空指针判断补全：fix函数中需要额外判断遍历节点为空的场景，避免遍历到父节点为空时出现野指针访问。

内容的提问来源于stack exchange，提问作者user12925759