Red black tree comparison function

Question

I have implemented a red black tree in C. In the C++ map it is possible to provide a custom comparison which only performs the operation value1 < value2. This operation returns true or false but how is the tree implemented without a comparison operation? I want my comparison function to return only 1 or 0 without any == operator. I tried to read it in the stl but the code is unreadable although I have experience in C++.

The full code is not necessary because it's the same code as every other tree implementation. At the moment there is the following compare function:

int cmp(void *key1, void *key2){
  if(*(int*)key1 < *(int*)key2){
    return 1;
  }else if(*(int*)key1 > *(int*)key2){
    return -1;
  }else{
    return 0;
  }
}

I want a compare function like this:

int cmp(void *key1, void *key2){
  if(*(int*)key1 < *(int*)key2){
    return 1;
  }else{
    return 0;
  }
}

I do not understand how searching works with this compare function because there is no stop condition when a node was found.

Answer 1

You can express equality in terms of strict inequality:

(a == b) <==> !(a < b || b < a)

The equivalence assumes that comparison relation is strict total ordering. That's required by C++ Compare types and also what you must require from the comparison function in your tree implementation.

As far as your binary tree search is concerned, take a look at how the first cmp is implemented. Pay attention to how it finds out when to return 0 using only <. Your implementation can do exactly the same using the second cmp.