處理bst中的重複

Question

我的bst必須能夠處理重複條目。有沒有人有如何去做這個不需要過多的代碼的任何策略？ 我想一直往右邊添加重複的東西，但那樣會弄亂bst的順序。例如，當副本有兩個孩子又有兩個孩子時會發生什麼？插入副本很容易，但要替換的節點要做什麼？

Answer 1

您可以將二叉搜索樹的節點變爲鏈接列表。

class Data implements Comparable<Data> 
{ 
    // These are the data elements in your binary search tree 
} 

class TreeNode 
{ 
    TreeNode left; // elements less than current node, or null 
    TreeNode right; // elements greater than current node, or null 
    List<Data> items = new LinkedList<Data>();  
} 

這裏，treeNode.items始終是一個非空列表，這樣item1.compareTo(item2) == 0爲每item1和treeNode.itemsitem2。

要插入一個重複元素，您可以找到相關的TreeNode對象並將其添加到items。

查找元素的邏輯幾乎與以前一樣，除了一旦找到相關的TreeNode對象，您必須遍歷鏈表。

Answer 2

只要它不是一個自平衡BST，我不會看到在等於它們的節點的左側或右側放置相等節點的問題。

編輯（simonn後的備註）：

如果有問題的「複製節點」已經​​有2個孩子，後來乾脆將「新的複製節點」到左邊，讓左邊的孩子「舊副本節點「成爲」新副本節點「的左側子節點。

讓我來舉個例子來說明一下。將重複前的樹：

4' 
/\ 
    2 5 
/\ 
1 3 

而現在的元素4''插入：

 4' 
    /\ 
    4'' 5 
/
    2 
/\ 
1 3 

只要樹不是自平衡，你應該沒問題。

Answer 3

我想知道你是否真的需要將重複條目存儲爲單獨的節點？將一個計數器變量添加到Node是否足夠？這樣，如果遍歷樹，您將知道重複條目的數量並仍然保持順序。