c++ - 誰かがRedBlackTreeの後継が正しく書かれているかどうかを確認できますか？

Question

pair<K,V> *RedBlackTree<K,V,Compare>::successor(K key) {

    Node *found = findNode(key, root);

    Node *p;
    Node *ch;
    Node *x;

    Node *y;
    if(found->right != sentinel)
        return new pair<K,V>(found->right->key, found->right->value);

    y = found->parent;
    /* if it does not have a left child,
    predecessor is its first left ancestor */
    while(y != NULL && found == y->right) {
            found = y;
            y = y->parent;
    }
    return new pair<K,V>(y->key, y->value);



}

Answer 1

このコードは正しくありません。次のツリーについて考えてみます。

   b
  / \
 a   f
    / \
   d   g
  / \
 c   e

の順序付け後継はbですc。あなたの関数は、順序どおりの後継者がであると考えていfます。順序どおりの後継者を見つけるには、いくつかのケースを処理する必要があります。このサンプルツリーには、処理する必要のある各ケースのインスタンスがあります。各ノードから開始し、それぞれの順序どおりの後継を見つけるために必要な手順を書き留めます。

興味があれば、私が別の質問に答えたところに、完全な説明が付いたアルゴリズムの実装を見つけることができます。

---

無関係なことに、関数はほぼ確実にstd::pair by値を返す必要があり、動的にを割り当てないようにする必要がありますstd::pair。