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;
}

このトリックは、同じエラーで異なる「名前」のアイテムが複数ある場合に役立ちます。同じエラーのアイテムが 2 つ見つかったが、値が一致しない場合、比較したアイテムは単に「大きい」として扱われます。

このトリックは通常の BST で機能すると確信していますが、redblack ツリーで問題が発生しています。私は赤黒木アルゴリズムを知りません。私は実装を使用しているので、これが機能しない理由があるのだろうかと思います。

PS: name には比較関係がありません...だから、私にできることは、それらが同じかどうかを確認することだけです。

PPS:これが機能しないと仮定し、「名前」値の間に順序関係を持たせないことを知っている場合、他にどのような可能性がありますか? 同じキーで複数の値を挿入できるデータ構造を使用できますが、それはうまくいきません。値を削除するときは、実際に渡している値を削除していることを確認する必要があるためです (基本的には私はキーと値が同じものを共有しているので、並べ替えられたマルチセット データ構造が必要です!)

4

2 に答える 2

1

二分探索ツリーは、比較関数が、ツリーに挿入する要素の全体的な順序付けに関する通常の規則に従うことを期待しています。現在の比較関数はこれに従いません。同じerrorキーで異なるvalue キーを持つオブジェクト A と B がある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

順序関係が定義されていません。

あなたの場合、オブジェクトは 2 次元です。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 に答える