Handling duplicates keys within an AVL tree

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.

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);