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.

"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

eerorika · Accepted Answer · 2016-02-17T21:53:31.357

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.

edited Feb 17 '16 at 21:53

answered Feb 17 '16 at 20:59

eerorika

232,697
12
197
326

Of course, that assumes that the `<` operator describes a total ordering. Not all types afford such an ordering, and not all `<` operators provide one. On the other hand, those that don't probably should not be used in a search tree. – John Bollinger Feb 17 '16 at 21:09
@JohnBollinger indeed, my answer assumes the context of C++ Compare types that require strict total ordering. I shall mention it explicitly. – eerorika Feb 17 '16 at 21:13
OP seems to re-implement in C. Not sure what his problem is, as he does not even show code. – too honest for this site Feb 17 '16 at 21:15
@Olaf my understanding is that Gustavo is asking how to implement equality comparison when the comparison function only does inequality. – eerorika Feb 17 '16 at 21:23
See his comment to the other question. He seems to try learning C using C++ as "template". – too honest for this site Feb 17 '16 at 21:26
@Olaf the other comment appears to pretty much confirm my interpretation. Although, for some reason they contradict the original question by suggesting the use of non-strict inequality. – eerorika Feb 17 '16 at 21:33

Red black tree comparison function

1 Answers1