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

Question

BST删除节点的思路是:

1. 如果该节点没有子节点，则将其删除，并将父节点指向该节点的指针更新为null

2. 如果该节点有一个 child ，通过更新该节点的父节点指向其 child 的指针，用其 child 替换该节点

3. 如果该节点有两个子节点，找到该节点的前任节点并将其替换为其前任节点，同时更新前任节点的父指针，指向其唯一的 child (只能是左 child )

最后一种情况也可以使用继任者而不是前任来完成!

据说如果我们在某些情况下使用前驱，而在另一些情况下使用后继(给予它们同等优先级)，我们可以获得更好的经验性能，

现在的问题是，它是如何完成的？基于什么策略？以及它如何影响性能？ (我猜他们所说的性能是指时间复杂度)

我的想法是，我们必须选择前任或继任者才能拥有更平衡的树!但我不知道如何选择使用哪一个!

一种解决方案是随机选择其中之一(公平随机性)，但采用基于树结构的策略不是更好吗？但问题是什么时候选择哪个？

Answer 1

关键是要找到正确的 BST 移除算法。 50 年来，人们一直试图解决它(就像就地合并一样)，但他们没有找到比通常的算法(删除前任/后继者)更好的方法。那么，经典算法有什么问题呢？实际上，这种删除会使树不平衡。经过几次随机操作 add/remove 你会得到高度为 sqrt(n) 的不平衡树。而且无论您选择什么 - 删除继任者或前任(或随机选择这些方式) - 结果都是一样的。

那么，选择什么呢？我猜测基于随机(succ 或 pred)的删除将推迟树的不平衡。但是，如果你想要完美平衡的树 - 你必须使用红黑树或类似的东西。