0

C ++で赤黒木を実装していますが、回転メソッドに問題があります。挿入方法はバランスが取れていなくても問題なく機能しますが、回転しようとするとすぐにツリーの情報が失われます。私の推測では、ノードへのポインターを正しい方法で設定していませんが、ここで何が問題になっているのかを正確に理解していません。

これが私の右回転方法です：

void RedBlackTree::rotateRight(RedBlackNode *localRoot) {
cout << "rotateRight - local root " << localRoot->data << endl;
RedBlackNode *temp = localRoot->left;
localRoot->left = temp->right;
temp->right = localRoot;
localRoot = temp;
}

起こっていることの例は、c、b、およびaを挿入することです。ツリーは最初は次のようになります。

    c
   /
  b
 /
a

ローテーション後、ツリーはルートノードのみを出力します。

何が起こっているのかについて何かアイデアはありますか？ありがとう！

4

1 に答える 1

4

コード セグメントに基づいて判断するのは困難localRootですが、関数を終了した瞬間に変更が忘れられるローカル ポインターです。関数が呼び出されているコンテキストで変更したい場合は、それを渡すかRedBlackNode*&、結果として値を返す必要があります。

于 2012-12-12T22:16:28.377 に答える