BST中删除节点的思路是：
如果该节点没有子节点，则删除该节点并将父节点指向该节点的指针更新为空
如果该节点有一个子节点，则通过更新该节点的父节点指向其子节点的指针来用其子节点替换该节点
如果该节点有两个子节点，则找到该节点的前驱节点并将其替换为其前驱节点，同时更新前驱节点的父节点指针，将其指向其唯一的子节点（只能是左子节点）
最后一种情况也可以使用后继而不是前任来完成！
据说，如果我们在某些情况下使用前驱，在其他情况下使用后继（给予它们同等的优先级），我们可以获得更好的经验性能，
现在的问题是，它是如何做到的？基于什么策略？它如何影响性能？ （我猜性能指的是时间复杂度）
我认为我们必须选择前任或后继者才能拥有一棵更加平衡的树！但我不知道如何选择使用哪一个！
一种解决方案是随机选择其中之一（公平随机性），但基于树结构的策略不是更好吗？但问题是何时选择哪个？
问题是这是一个根本问题——找到 BST 的正确去除算法。 50 年来，人们一直在尝试解决这个问题（就像就地合并一样），但他们没有找到比通常的算法（删除前驱/后继）更好的算法。那么，经典算法有什么问题呢？实际上，这种删除会使树失去平衡。经过几次随机操作add/remove你会得到高度不平衡的树sqrt(n)。无论您选择什么 - 删除后继者或前任（或在这些方式之间随机选择） - 结果都是相同的。
那么，该选择什么呢？我猜测基于随机（succ 或 pred）的删除将推迟树的不平衡。但是，如果你想拥有完美平衡的树 - 你必须使用红黑树或类似的东西。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
