處理AVL樹內的重複密鑰

Question

我想讓我的avl-tree支持重複密鑰，但binary search tree的默認行爲存在問題，重複的情況是輪換可能會使相同密鑰的節點位於左側和右側父母。

對於添加三個節點時，例如所有鍵A將導致樹做旋轉到是這樣的：

A 
/\ 
A A 

所以讓所有的與該鍵的條目將是一個問題......並且在兩個方向搜索都不好。

，我已經想到的是使每個節點存儲重複的陣列 所以加入已經存在將只是加入新的項目到陣列的新的項目時的溶液， 與主要去除項目將刪除整個節點，而用鍵查找所有項目將返回該數組。

是否有其他方法來處理重複？

插入項需要一個鍵和一個值..所以我需要存儲值以便通過findAll以某種關鍵方法返回它們。

Answer 1

另一種通用方法是在內部創建密鑰的值部分，以便您不再擁有重複的密鑰。無論如何，您需要同時使用密鑰和值才能從允許重複的樹中刪除條目。

要搜索的關鍵不知道的價值，那麼你會做這樣的事情（僞代碼）：

searchResult = myTree.SearchGreaterOrEqual(Key); 
found = (searchResult != null) && (searchResult.Key == Key); 

Answer 2

讓每個節點都包含一個計數：添加重複項會增加計數，刪除會減少計數，除非它是1，在這種情況下整個節點將被刪除。