Handling duplicates keys within an AVL tree

问题:

I want to make my avl-tree support duplicate keys but there is a problem with the default behavior of the binary search tree with duplicates that the rotation could make nodes with equal key be on the left and the right of the parent.

For example when adding three nodes all with key A will cause the tree to do a rotation to be something like this:

   A
  /  \ 
 A    A

So getting all the entries with that key will be a problem...and searching in both direction is not good.

The solution that i have thought of is making each node stores an array of duplicates so when adding a new item that already exists will be just adding a new item to the array , removing item with key will delete the whole node while the find all items with key will return that array.

Are there are any other methods to handle duplicates ?

The insert item takes a key and a value .. so i need to store the values inorder to return them by the findAll with certain key method.

回答1:

Another general approach is to internally make the value part of the key so that you don't really have duplicate keys anymore. You'll need both the key and the value anyway in order to delete an entry from a tree that allows duplicates.

To search for a key without knowing the value, you would then do something like (pseudo-code):

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

回答2:

Have each node contain a count: addition of duplicates will increment the count, removals will decrement the count unless it's 1, in which case the whole node will be removed.