-1

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.

Gustavo
  • 143
  • 9
  • "I have implemented a red black tree in C. In the C++ map ..." - So which language is it? C and C++ are **different** languages! – too honest for this site Feb 17 '16 at 21:09
  • My intention was to look in the C++ stl library to understand how it works. – Gustavo Feb 17 '16 at 21:11
  • You can also look into the Python or a Fortran library. But that does not show how to implement it in C. And C very well **does** have comparison operators. To learn C, read a C book, not a C++ book or a novel. If you have a **specific** problem with your C code, state it clearly and provide a [mcve]. – too honest for this site Feb 17 '16 at 21:13

1 Answers1

4

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.

eerorika
  • 223,800
  • 12
  • 181
  • 301