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