c - 红黑树比较函数

Question

我已经用 C 实现了红黑树。在 C++ 映射中，可以提供仅执行 value1 < value2 操作的自定义比较。该操作返回 true 或 false，但是如果没有比较操作，树是如何实现的呢？我希望我的比较函数只返回 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 是如何进行的。已实现。注意它如何仅使用 < 来确定何时返回 0 。您的实现可以使用第二个 cmp 执行完全相同的操作。 .