节点在二叉搜索树公平缺失 [英] Fair deletion of nodes in Binary Search Tree
问题描述
删除在BST一个节点的构思是：
The idea of deleting a node in BST is:
-
如果该节点没有孩子，将其删除并更新家长的指针，该节点为空值
If the node has no child, delete it and update the parent's pointer to this node as null
如果该节点有一个孩子，通过更新节点的父节点的指针，其子替换其子节点
If the node has one child, replace the node with its children by updating the node's parent's pointer to its child
如果该节点有两个孩子，找到节点的predecessor，并将它与它的predecessor取代，也将其指向其独生子女更新predecessor的父母的指针（这只能是左子）
If the node has two children, find the predecessor of the node and replace it with its predecessor, also update the predecessor's parent's pointer by pointing it to its only child (which only can be a left child)
最后一种情况下也可以与使用的继任者，而不是predecessor的完成了！
the last case can also be done with use of a successor instead of predecessor!
有人说，如果我们用在其他一些情况下，predecessor在某些情况下和继承人（给他们同等优先级），我们可以有更好的经验表现，
It's said that if we use predecessor in some cases and successor in some other cases (giving them equal priority) we can have better empirical performance ,
现在的问题是，它怎么办？基于什么样的策略？它是如何影响性能？ （我用的性能估计他们的平均时间复杂度）
Now the question is , how is it done ? based on what strategy? and how does it affect the performance ? (I guess by performance they mean time complexity)
我想的是，我们必须选择predecessor或后续有一个更加平衡的树！但我不知道该如何选择使用哪一个！
What I think is that we have to choose predecessor or successor to have a more balanced tree ! but I don't know how to choose which one to use !
解决方案之一是随机选择他们（公平的随机性）之一，但不是最好有基于树状结构的战略？但问题是，当选择哪个？
One solution is to randomly choose one of them (fair randomness) but isn't better to have the strategy based on the tree structure ? but the question is WHEN to choose WHICH ?
推荐答案
正如你所说，这是一个平衡问题，所以一般扰乱余额最少的方法是preferable。你可以举办一些指标来衡量平衡（例如，从不同的最大和最小叶的高度，平均身高等）的水平，但我不知道的开销是否值得。此外，还有自平衡的数据结构（红 - 黑，AVL树等），通过重新平衡每个删除之后缓解这一问题。如果你想使用基本的BST，我想，没有树结构的先验知识和删除程序的最佳策略是将2种方法对每个删除之间切换。
As you said, it's a question of balance, so in general the method that disturbs the balance the least is preferable. You can hold some metrics to measure the level of balance (e.g., difference from maximal and minimal leaf height, average height etc.), but I'm not sure whether the overhead worth it. Also, there are self-balancing data structures (red-black, AVL trees etc.) that mitigate this problem by rebalancing after each deletion. If you want to use the basic BST, I suppose the best strategy without apriori knowledge of tree structure and the deletion sequence would be to toggle between the 2 methods for each deletion.
这篇关于节点在二叉搜索树公平缺失的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
