2

Red-Black Tree に実装されている再帰的な挿入メソッドがあります。再帰呼び出しから戻った後、ローカル ルートの子が赤かどうかを確認しようとしています。しかし、実際に起こっているのは、サブツリー (最新の挿入が行われた場所) ではなく、ツリーのルートをチェックしていることです。

私が見ているコードのスニペットは、insertNode メソッド内にあります。

this->insertNode(root->right, value);
if(root->right->is_red) {
    cout << "color again & " << root->data << endl;
    root->right->is_red = false;
    root->is_red = true;
    this->rotateLeft(root);
}

最後の挿入が行われたサブツリーのルートを操作するにはどうすればよいですか? 再帰呼び出しから戻る前に、これが完了していることを確認する必要がありますか?

4

1 に答える 1

1

実際に挿入されたノードを返すように、insertNode を変更します。挿入後、その親に簡単にアクセスできます (そのノードがその親を知っていると仮定します)。

于 2012-12-13T10:34:51.023 に答える