二叉搜索树中的删除，仅具有 'right child' 的节点
Deletion in Binary Search Tree, node with 'right child' only
我试图在 BST 中编写删除节点的代码，现在我对节点只有 right_child 的情况感到有点困惑。
大多数算法处理 4 种情况：
如果是叶节点，则删除
如果节点只有left_child，则提升
如果节点只有right_child，则提升
如果node有2个children，将值替换为node的inorder_successor，删除后继[=13] =]
当我尝试编码时，我处理了以下 3 种情况：
如果是叶节点，则删除
如果节点没有right_child，提升左边child
否则，将值替换为节点的inorder_successor，并删除后继
最终，对于以下情况，生成的 BST 将有所不同：
- With the way I delete node with right child only:
1 Delete(1) 3
4 -----------> 4
3
- The way other algos suggest:
1 Delete(1) 4
4 -----------> 3
3
我好像找不到我删除的方式有什么问题
当然，BST 可能更多 right-skewed 并且会递归地发生更多删除，但是 BST 不变量仍然完好无损，对吧？
有一些讨论here and here但没有被接受的答案
When I was trying to code it, I handled following 3 cases ...
加个case更自然：
- 如果是叶节点，则删除
- 如果节点没有right_child，提升左边child
- 如果节点没有left_child，提升右边child
- 否则，将值替换为节点的inorder_successor，并删除后继
这将最后一个要点中的算法的使用限制在最低限度，因为这是成本更高的算法。
但是，获得有效 BST 的方法不止一种，因此即使您跳过这种情况并为其使用“Else”算法，您仍然会获得有效 BST。
我试图在 BST 中编写删除节点的代码，现在我对节点只有 right_child 的情况感到有点困惑。
大多数算法处理 4 种情况：
如果是叶节点，则删除
如果节点只有left_child，则提升
如果节点只有right_child，则提升
如果node有2个children，将值替换为node的inorder_successor，删除后继[=13] =]
当我尝试编码时，我处理了以下 3 种情况：
如果是叶节点，则删除
如果节点没有right_child，提升左边child
否则，将值替换为节点的inorder_successor，并删除后继
最终，对于以下情况，生成的 BST 将有所不同：
- With the way I delete node with right child only:
1 Delete(1) 3
4 -----------> 4
3
- The way other algos suggest:
1 Delete(1) 4
4 -----------> 3
3
我好像找不到我删除的方式有什么问题
当然，BST 可能更多 right-skewed 并且会递归地发生更多删除，但是 BST 不变量仍然完好无损，对吧？
有一些讨论here and here但没有被接受的答案
When I was trying to code it, I handled following 3 cases ...
加个case更自然：
- 如果是叶节点，则删除
- 如果节点没有right_child，提升左边child
- 如果节点没有left_child，提升右边child
- 否则，将值替换为节点的inorder_successor，并删除后继
这将最后一个要点中的算法的使用限制在最低限度，因为这是成本更高的算法。
但是，获得有效 BST 的方法不止一种，因此即使您跳过这种情况并为其使用“Else”算法，您仍然会获得有效 BST。