algorithm - 红黑树可以应付这种比较功能吗？

Question

我正在考虑使用不支持使用类似于此的比较函数多次插入同一键的 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...但是我在使用红黑树时遇到了麻烦。我不知道红黑树算法，我正在使用一个实现，所以我想知道是否有任何原因导致它不起作用。

P.S.: name没有比较关系...所以我唯一能做的就是检查它们是否相同。

P.P.S.:假设这行不通，并且知道我无法在“名称”值之间建立顺序关系，那么我还有哪些其他可能性？我可以使用允许使用相同键插入多个值的数据结构，但这对我不起作用，因为当我删除一个值时，我必须确保我正在删除我实际传递的值(基本上是为了我的键和值是一样的，我需要一种有序的多集数据结构!)

Answer 1

您的二叉搜索树期望您的比较函数遵守 total ordering 的通常规则在你要插入到树中的元素上。您当前的比较函数不遵守此规定，因为如果您的对象 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;
}