Which side do we place a node if it is equal to the parent in a binary search tree

user_15611749 0
Viewed 1096

I am learning data structures and algorithms. In particular, I am learning Binary Search Trees (BSTs).

My question, as the title hints, is, if we are placing a value, and it is equal to its parent, which side do we place it? The left side is for values lesser than the parent, and the right side is for values greater than the parent. So, where do we place a value equal to the parent?

Thanks for any help on this.

binary-search-tree nodes data-structures algorithm
3 Answers

There isn’t a universally agreed upon standard way to do this. Some people don’t allow BSTs to store duplicates at all, essentially defining this problem away. (That’s what you often see when using trees for maps and sets). Other implementations might store all equal keys in the same node, perhaps by using a linked list. Others might say that the left subtree holds smaller keys while the right subtree holds keys greater than or equal to the node’s own key.

Each of these approaches has advantages and disadvantages, and it’s up to you to select which one is best for your use case.

user_5015570

Algorithms just make the choice on which side to insert a value that is the same as the current node has. It is of course easiest (and cost effective) to implement when that choice is always the same.

However, binary search trees can only guarantee logarithmic efficiency when they maintain some balance, and so we must also consider what rebalancing does to the position of nodes that have the same value.

For instance, if the binary search tree is an AVL tree, then rotations will occur when there is an imbalance of more than 1 in any subtree.

Let's assume we have an algorithm for an AVL tree that chooses the right side when a value is equal to the current node's value. And let's say we insert the values 1, 1 and 2 in that order in an empty tree. Then after the second insertion, we get this:

  1
   \
    1 (insert at right side of root)

Then we insert 2:

  1
   \
    1
     \
      2

Now the AVL mechanics perform a simple left rotation, and we end up with:

  1
 / \
1   2

...and now the second inserted node became the root, putting the original root at its left side.

So, in conclusion, when we speak of an self-balancing binary search tree, then even when the algorithm chooses one specific side for inserting a duplicate value, there is no guarantee that all equal values are always found at that side, due to the rebalancing feature of the tree.

user_54598390

As @templatetypedef mentioned, one common approach is to only allow a single node for each value (i.e. key) in the BST. For multiset semantics (to keep track of how many times a key is present) it is sufficient to store a counter at each node. This approach is simple and quite efficient.

user_155319860
Related