红黑树比较函数

Question

我已经在 C 中实现了红黑树。在 C++ 映射中，可以提供仅执行操作 value1 < value2 的自定义比较。这个操作returns true or false 但是没有比较操作的树是怎么实现的呢？我希望我的比较函数 return 只有 1 或 0，没有任何 == 运算符。我试图在 stl 中阅读它，但代码不可读，尽管我有 C++ 经验。

不需要完整代码，因为它与所有其他树实现的代码相同。目前有以下比较功能：

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

我想要这样的比较功能：

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

我不明白搜索是如何使用这个比较函数的，因为在找到节点时没有停止条件。

Answer 1

你可以用严格不等式来表达相等：

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

等价假设比较关系是严格的全序。这是 C++ 比较类型所要求的，也是您在树实现中必须从比较函数中要求的。

就你的二叉树搜索而言，看看第一个cmp是如何实现的。注意它如何仅使用 < 找出何时 return 0。您的实现可以使用第二个 cmp.

做完全相同的事情

红黑树比较函数

Red black tree comparison function

c

algorithm

red-black-tree

binary-search-tree