二叉搜索树中节点的公平删除

Question

二叉搜索树中节点的公平删除

algorithmdata-structuresbinary-search-tree

4

在BST中删除节点的思路如下：

如果该节点没有子节点，则删除该节点并将其父节点的指针更新为null
如果该节点有一个子节点，则用其子节点替换该节点，并更新该节点父节点的指针为其子节点
如果该节点有两个子节点，则找到该节点的前驱，用前驱替换它，并将前驱的父节点指针更新为其唯一的子节点（只能是左子节点）

在某些情况下，也可以使用后继来完成最后一种情况！

据说，如果我们在某些情况下使用前驱，在其他情况下使用后继（给它们相等的优先级），我们可以获得更好的实际性能，

现在的问题是，如何做到这一点？基于什么策略？它如何影响性能？（我想他们的意思是时间复杂度）

我认为我们必须选择前驱或后继来使树更加平衡！但我不知道该选择哪一个！

一种解决方法是随机选择其中之一（公平随机），但是否更好地基于树结构制定策略？但问题是何时选择哪个？

- Arian

2个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- SomeWittyUsername · Answer 1

正如你所说，这是一个平衡的问题，因此通常最不干扰平衡的方法是首选。您可以使用一些指标来衡量平衡水平（例如，最大和最小叶高度之间的差异，平均高度等），但我不确定是否值得这样做。此外，还有自平衡数据结构（红黑树、AVL树等），通过在每次删除后重新平衡来缓解这个问题。如果您想使用基本的BST，我认为在没有树结构和删除序列的先验知识的情况下，对于每个删除，最好的策略是在两种方法之间切换。

- Vladimir Kostyukov · Answer 2

问题在于寻找二叉搜索树的正确删除算法是一个基本问题。50年来，人们一直在尝试解决它（就像原地合并一样），但他们没有找到比通常算法更好的方法（使用前驱/后继删除）。那么，经典算法有什么问题吗？实际上，这种删除会使树失衡。经过几次随机操作添加/删除后，您将得到高度为sqrt(n)的不平衡树。而且无论您选择什么 - 删除后继或前任（或在这些方式之间随机选择）- 结果都是相同的。

那么，该选择什么呢？我猜基于随机的（后继或前任）删除将推迟树的不平衡。但是，如果您想要完美平衡的树 - 您必须使用红黑树或类似的东西。