删除在二叉搜索树

为什么删除的BST一个O（日志（n））的操作。正如我undersand涉及释放的节点和指向父对NULL参考。如果不采取这种O（1）删除在二叉搜索树

2011-03-28 shreyasva

它是O（log n）的仅在平衡树... – 2011-03-28 15:42:42

@Moron：这使得O（LG * n *）**在非自平衡BST中的预期时间**。 – 2011-03-28 16:17:10

@lars：同意。猜猜谁回复了你的答案:-) – 2011-03-28 16:47:23

的问题是如何删除它有两个孩子的节点 - 树必须进行重组，让孩子找到合适的新父母。详细解释here。 Google是你的朋友。

2011-03-28 15:07:21 Jon

这是O（lg n）如果您从树的根开始，那么您需要搜索要删除的元素，然后搜索其按序继任者。

2011-03-28 15:09:15

如果你想删除一个节点和所有的孩子那么它很简单，但你必须重建孩子，如果你想要保持排序顺序。

2011-03-28 15:10:21 vbence

那么即使在这种情况下，如果你已经有了你想要删除的（内部）节点，它也只会是O（1）。通常，删除必须从根开始，并从给定的值O（log n）本身中搜索正确的节点。 – Voo 2011-03-28 15:20:08

不，这需要O（k）其中* k *是节点的子节点数，假设手动内存管理（否则您将为后面的垃圾回收付费）。此外，除非你删除一个范围，并确定范围完全在节点下面需要O（lg * n *）时间，否则这不是一个明智的操作。 – 2011-03-28 16:16:21

删除在二叉查找树是O（h），其中h是树的高度。

现在，美都没有提到树是否是平衡或不是最坏的情况下复杂性不平衡的树会为O（n），即当它是一个堕落的树。

如果b.s.t是平衡点之一（Avl，红色黑色等），那么最坏情况的复杂度就是O（lg n）作为几乎所有平衡点b.s.t的高度。是K *（lg n）。

例如，对于AVL树K = 1和用于红黑树K = 2

2011-07-12 06:54:12

回答