Is it necessary to implement a BST with both keys and values?

Question

Is it necessary to implement a BST with both keys and values? I can implement a BST that has method calls such as the following, in which it will make the comparison at each node of whether the traversal should go to the left node or right node based upon the V value:

public class BST<V>
{
    public void Insert(V value)
    {
        //implementation
    }

    public V Remove(V value)
    {
        //implementation
    }

    //other methods
}

Or, I can implement the BST such that it has the method calls like the following, in which the K keys are the comparing determination of whether to traverse to the left node or the right node:

public class BST<K key, V value>
{
    public void Insert(K key, V value)
    {
        //implementation
    }

    //which of the following would then be the appropriate method signature?
    public V Remove(K key)
    {
        //implementation
    }
    //or?
    public V Remove(V Value)
    {
        //implementation
    }

    //other methods
}

Answer 1

Not using a key but only a value is fine. However, the tree will become immutable if you do this. Modifying a value is no longer safe since it will imbalance the tree. You will have to enforce this by providing only a property getter for the node value.

Answer 2

If it is general purpose data structure I'd suggest to use key-value based API (as you do not know in advance the relation between keys and values) with IComparable constraint on TKey. If it is use case specific implementation where a key is a value as well (for example, BST is used to determine whether it contains specified key or not) I'd suggest to use key based API.

Answer 3

It depends on what you actually need. If you need an associative data structure, a key-value based implementation is what you have to implement. Otherwise, if you are simply putting elements into a sorted collection, I don't see the need to have a separate key for each element. Just make sure all elements implement Comparable or you can pass a custom Comparator implementation (like in TreeSet/TreeMap), or any well defined scheme of having a total ordering of the elements of the BST.

Answer 4

No, data structures which need keys to function do not require anything else. It just depends on how you want to implement it. Most of the time using a key-value-pair-based system is the most convenient, but in some implementations you might want to let the user of the data structure specify a comparison function and just have each node store a "value" (an instance of a user-defined class). This class might contain the key among other things, but you don't have to know the format of the class, because the user-specified comparison function will take care of everything.

An example I can think of where this is used is in the Windows kernel.