Handling duplicate keys in the AVL tree

Question

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

For example, if you add three nodes, everything with key A will cause the tree to rotate in this way:

  A / \ AA 

Thus, getting all the records using this key will be a problem ... and searching in both directions is not good.

The solution I was thinking about is that each node stores an array of duplicates so when adding a new element that already exists, it will simply add a new element to the array, deleting the element with the key will delete the entire node, while searching for all elements with will return this array with the key.

Are there any other methods for handling duplicates?

The inserted element accepts the key and value .. so I need to save the inorder values ​​in order to return them with findAll using a specific key method.

Answer 1

Another general approach is to internally make value a part of the key, so that you no longer have duplicate keys. In either case, you will need both a key and a value to remove the entry from the tree, which allows duplicates.

To find the key without knowing the values, you should do something like (pseudocode):

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

Answer 2

Let each node contain a counter: adding duplicates will increase the counter, deleting will decrease the counter, if only 1, in which case the entire node will be deleted.