我正处于basic algorithms course的中间 .
讲座讨论如何在长时间的随机插入和删除中，标准"Hibbard"删除将偏向树形状，将操作的深度和性能从log（N）降低到sqrt（N）（即使您随机选择左侧或右子树从中推广，as described in the answer to this question） .
讲座还提到人们一直在寻找一种更好的删除方法50年 .
我在下面有一个算法大纲，看起来应该是"unbiased" .
所以我有几个问题：
-
我错了，这是坏了吗？
-
这个算法叫什么？ （我怀疑我在这里发明了什么新东西）
-
这有什么问题，它不是标准的BST删除？
我的算法很简单，我也喜欢你不需要先实现delete-min / delete-max来实现删除 .
随机地将节点插入BST导致“无偏”树 . 删除节点时，尝试构建如果已删除的节点从未存在过的树 .
如果节点有时间戳，则很容易，应该提升旧节点 . 但是对节点加时间戳可能不值得 .
但是，对于节点来说，包含子树的大小似乎很常见，这可以用来猜测哪个节点首先出现 .
具体来说：
如果删除的节点没有子节点，则表示已完成 . 如果它有1个孩子宣传孩子，那么你已经完成了 .
否则，已删除的节点的子节点都在其后添加 . 如果从未插入已删除的节点，则其中一个已删除节点的子节点将占据该位置 .
两个孩子的大小可以看作来自二项分布的样本 . 这些可用于轻松估计节点从已删除节点向左或向右移动的可能性 .
使用该二项式概率随机选择将左侧或右侧子树提升到已删除节点的位置（或者只选择最大的？）
（自动提升较大的子树是否有可能使树略短于无偏树的预期？） .
未提升的“自由”子树将在提升的子树中向左或向右流动，因为它的所有节点都比提升的树中的任何节点更大或者更少 .
对于“自由”子树遇到的每个节点，断开“遇到”节点的子树与主树的连接 .
假装一个节点刚被删除在“遇到”节点的位置，并且“自由”子树和“遇到的”子树是它的子节点，并递归/循环
2 回答
据我了解你的概念，它的问题在于线性时间复杂度 . 这在BST世界中效率不高 . Hibbard删除与树的高度成正比（不幸的是，即使它以lgN开始，也会在一段时间后得到sqrt（N）），但是当你重新插入树的“相当大的”部分时，你的线性是线性的（数字）您必须重新插入的节点不受树高度的常数倍的限制 .
你的方法可以保持 balancer ，但是在删除后保持BST balancer 不是一个悬而未决的问题，而是要保持它们的有效 balancer .
事实证明，这是Randomized BST的删除方法 .
即使项目以非随机顺序插入，随机化BST也会为您提供无偏的树形状 .