How to allow duplicates in a binary search tree?

Question

I am not looking for the code, just the concept.

As per professor jonathan Shewchuck of UC Berkley (online CS61b course), if you find an exact match, you could insert your new entry as a left child.

Assuming you always pick the left node of the exact match and insert your new entry there, what will happen if the exact match you found already has a left child? Do you detach it and force a new entry in its place and reattach the old left child as this new node's child?

What if the exact match already has a left child, which is itself an exact match? Does the code become too complicated if you allow duplicates?

Sergey Kalinichenko · Accepted Answer · 2015-09-01 01:00:36Z

You need to go all the way to the left as far as you can before attaching a node. Follow the regular insertion logic for the new node into the left subtree. For example, if you are inserting

5, 3, 7, 2, 3, 8, 7, 2, 5

the resultant tree would look like this:

                      5
                    /   \
                   3     7
                  / \   / \
                 2   5 7   8
                / \
               2   3

Note how 3s and 5s are not together in this tree, because the first 3 already has a left child at the time we insert a duplicate, and so does 5.

Of course, this is not ideal, because searching does not end when you find the element that you want. A better approach would be to augment the tree structure by placing the count of duplicates for each node in the tree, or a list of data attached to each individual node if the tree is used for associative storage.

                     5(2)
                    /    \
                  3(2)   7(2)
                 /         \
               2(2)        7(1)

Collectives™ on Stack Overflow

How to allow duplicates in a binary search tree?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related