刪除BST中的重複元素

Question

考慮有一個BST具有重複的元素。你必須從樹中刪除所有重複的元素。在找到相等密鑰時，在BST中的插入是隨機的，即，當在樹中插入密鑰時，如果所述密鑰已經存在，則可以將密鑰插入到左子樹或右子樹中，但仍然遵循BST的基本屬性。因此，任何節點的左子樹上的所有密鑰都小於或等於該節點，並且任何節點的右子樹上的密鑰都大於或等於該節點。你將如何刪除所有重複的元素。

請注意，如果一個關鍵字例如15在整個樹中出現三次，我們不會刪除所有三個實例，而是刪除兩個，兩個都沒關係。

有PreOrder方式遍歷樹的蠻力方法。然後在左邊和右邊的子樹中找到並刪除元素，它們的關鍵字等於所述節點。

有沒有更好的方法來解決這個問題？

Answer 1

您提到的蠻力方法的最壞情況複雜度爲O(n^2)。

實現更好複雜性的一種方法是使用hash-table。您可以在BST上進行遍歷並將每個節點的計數存儲在散列表中。然後，再次通過（以適合您的任何方式）並刪除其數量大於1的節點。假設樹是平衡的，該方法具有改進的複雜度O(n*logn)。