how to handle duplicates in AVL tree
- by Ahmed Kotb
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 ?
