1

我正在考虑使用一个不支持多次插入同一个键的 RedBlack 树，它使用类似于这个的比较函数：

int compare(MyObject A, MyObject B)
{
   if (A.error > B.error) return 1;
   if (A.error < B.error) return -1;
   if (A.name == B.name) return 0;
   return 1;
}

这个技巧对于有多个具有相同错误但“名称”不同的项目很有用。如果找到两个具有相同错误的项，但值不重合，则将比较项视为“较大”。

我很确定这个技巧适用于普通的 BST ......但我在使用红黑树时遇到了麻烦。我不知道红黑树算法，我正在使用一个实现，所以我想知道是否有任何原因导致这不起作用。

PS：名称没有比较关系...所以我唯一能做的就是检查它们是否相同。

PPS：假设这不起作用并且知道我不能在“名称”值之间建立顺序关系，我还有什么其他可能性？我可以使用允许使用相同键插入多个值的数据结构，但这对我不起作用，因为当我删除一个值时，我必须确保我正在删除我实际传递的值（基本上是我的键和值是一样的，我需要一种有序的多集数据结构！）

4

2 回答 2

1

您的二叉搜索树希望您的比较函数遵守通常的规则，以便对要插入到树中的元素进行总排序。您当前的比较函数不遵守这一点，因为如果您的对象 A 和 B 具有相同的error键但不同的value 键，那么根据compare您的说法A < B，它们B < A都是有效的。

我认为如果您将比较功能更改为

int compare(MyObject A, MyObject B)
{
   if (A.error > B.error) return 1;
   if (A.error < B.error) return -1;
   if (A.value > B.value) return 1;
   if (A.value < B.value) return -1;
   return 0;
}
于 2013-10-30T19:25:36.300 回答
0

您没有定义订单关系。

在您的情况下，您的对象是二维的。我从您的问题中了解到，应优先考虑订购该error领域。因此，顺序关系（使用字典顺序）应该是：

struct my_object {
    int error;
    int value;
};

int compare(struct my_object *a, struct my_object *b)
{
    int ret;
    if (!a) {
        return 1;
    }
    else if (!b) {
        return -1;
    }
    ret = a->error - b->error;
    if (!ret) {
        ret = a->value - b->value;
    }
    return ret;
}
于 2013-10-30T19:21:15.870 回答