刪除在二叉搜索樹

爲什麼刪除的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

回答