how to handle duplicates in AVL tree

Posted by Ahmed Kotb on Stack Overflow See other posts from Stack Overflow or by Ahmed Kotb
Published on 2010-03-18T19:58:40Z Indexed on 2010/03/18 20:01 UTC
Read the original article Hit count: 519

Filed under:
|

I want to make my avl tree support adding duplicates 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 adding A,A,A will cause the tree to do a rotation to be something like that

   A
  /  \ 
 A    A

so getting all the entries with that key will be a problem...and searching in both direction is not something 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 ?

© Stack Overflow or respective owner

Related posts about avl-tree

Related posts about homework