BST中删除节点的思路是：
如果该节点没有子节点，则将其删除并将父节点指向该节点的指针更新为空
如果节点有一个子节点，则通过更新节点的父节点指向其子节点的指针来用其子节点替换该节点
如果节点有两个子节点，则找到该节点的前驱并将其替换为其前驱，同时更新前驱的父节点指针，将其指向其唯一的子节点（只能是左子节点）
最后一种情况也可以使用后继者而不是前任者来完成！
据说如果我们在某些情况下使用前任，在其他情况下使用后继（给予他们同等的优先级），我们可以获得更好的经验表现，
现在的问题是，它是如何完成的？基于什么策略？以及它如何影响性能？（我猜他们的性能意味着时间复杂度）
我认为我们必须选择前任或继任者才能拥有更平衡的树！但我不知道如何选择使用哪一个！
一种解决方案是随机选择其中一个（公平随机性），但基于树结构的策略不是更好吗？但问题是何时选择哪个？
The thing is that is fundamental problem - to find correct removal algorithm for BST. For 50 years people were trying to solve it (just like in-place merge) and they didn't find anything better then just usual algorithm (with predecessor/successor removing). So, what is wrong with classic algorithm? Actually, this removing unbalances the tree. After several random operations add/remove you'll get unbalanced tree with height sqrt(n). And it is no matter what you choosed - remove successor or predecessor (or random chose beetwen these ways) - the result is the same.
So, what to choose? I'm guessing random based (succ or pred) deletion will postpone unbalancing of your tree. But, if you want to have perfectly balanced tree - you have to use red-black ones or something like that.
正如你所说，这是一个平衡的问题，所以一般来说，扰乱平衡最小的方法是可取的。您可以持有一些指标来衡量平衡水平（例如，最大和最小叶高的差异、平均高度等），但我不确定开销是否值得。此外，还有自平衡数据结构（红黑、AVL 树等）通过在每次删除后重新平衡来缓解此问题。如果你想使用基本的 BST，我想没有先验知识的树结构和删除顺序的最佳策略是在每次删除的 2 种方法之间切换。