1

Most BST examples show a sample of a BST with unique values; mainly to demonstrate the order of values. e.g. values in the left subtree are smaller than the root, and values in the right subtree are larger.

Is this because BSTs are normally just used to represents SETs ?

If I insert an element say 4 which already exists in the BST, what should happen ? e.g. In my case, 4 is associated with a payload. Does it mean I override the existing node's payload.

1 Answer 1

1

The classic examples of the BST demonstrate a set where there is one entry for a given value in the structure. An example of this is the TreeSet in Java (yes, thats a red-black tree behind the scenes - but its a tree and a set).

However, there's nothing saying that there can't be additional values stored at the location indicated by the value. Once you decide to do this, it becomes an associative array (sometimes called a map). Again, going to Java for the example, there is the TreeMap.

An example of this could be:

TreeMap<Integer, String> ageToName = new TreeMap<Integer, String>();
ageToName.put(4,"Alice");
ageToName.put(25,"Bob");
ageToName.put(16,"Charlie");

The structure of this would look like:

      16 -> Charlie          
     /             \         
    /               \        
4 -> Alice          25 -> Bob

A balanced binary tree (the red-black part of that structure) with a left child and a right child. You access it by looking for the value 4, or 16, or 25 and get back the associated data stored in that node.

One aspect of the tree is that you can't have two different values with the same index. There is no way with this design to insert David at age 16 also. However, one could put another data structure such as a list instead of the String at the node and allow you to store multiple items in that list.

But the (binary) tree, by itself, is a set that requires the indexes into it to be comparable (orderable) and that it will contain only distinct values (no duplicates).

Realize that everyone is free to implement their own trees and sets and how they deal with the addition of another item with the same key. With a TreeSet, if you add an already existing value, the add function returns false and leaves the set unchanged. With a TreeMap, if you call put with a key that already exists, it replaces the old value and returns the replaced value (null if nothing was there).

What should happen is whatever you need to have happen for that implementation. There's no inscribed tablet that all the computer scientists signed that dictates how any abstract data structure should behave. They behave as they should and when they need to behave other ways, document it and do it that way.

3
  • Don't maps need to have O(1) access ? If it were a tree (as in TreeMap, then a query for a map.get(key) would be O(logN) ?
    – Bon Ami
    Apr 20, 2014 at 22:09
  • A map needs to map one item to another item. There is nothing about O(1) in the definition of the map. In Java, HashMaps (and enum maps) provide O(1) access, but there's also TreeMap and ConcurrentSkipListMap which meet the requirements of the Map Interface and are O(logN) for lookup. All that one needs for a map is that it maps a key to a value. Realize that HashMap doesn't let you do such queries as "give me all the key,value pairs less than some key" (well, it would be O(N) - having to look at every value in its array).
    – user40980
    Apr 20, 2014 at 22:19
  • Ok. I think I had the concept of hash tables in mind with regard to O(1) access. Java maps are more general, as you described above.
    – Bon Ami
    Apr 20, 2014 at 22:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.