3

私はAVLサーチツリーの実装に取り​​組んでいます。これまでのところ、コーディング部分を終了し、バグのテストを開始しました。ノードのローテーション方法にバグがあることがわかりました。神のために、何が問題なのか理解できません。

アルゴリズムは紙の上では正常に機能しますが、マシン上で実行するとうまく機能します...ツリーノードをリークします。

これは、ノードを左に回転させるために使用される方法です：http: //pastebin.com/mPHj29Af

bool avl_search_tree::avl_tree_node::rotate_left()
{
    if (_right_child != NULL) {
        avl_tree_node *new_root = _right_child;
 
        if (_parent != NULL) {
            if (_parent->_left_child == this) {
                _parent->_left_child = new_root;
            } else {
                _parent->_right_child = new_root;
            }
        }
 
        new_root->_parent = _parent;
        _parent = new_root;
 
        _right_child = new_root->_left_child;
        new_root->_left_child = this;
 
        if (_right_child != NULL) {
            _right_child->_parent = this;
        }
 
        //update heights
        update_height();
        new_root->update_height();
 
        return true;
    }
 
    return false;
}

私の挿入方法では、AVLバランシング部分にコメントを付けましたが、代わりに、新しく挿入されたノードを左に回転させようとしています。整数を昇順で挿入した結果：私のツリーには最初のルート（最初に挿入されたノード）のみが含まれ、他のすべてのノードがリークされます。

私が怒り始めているので、問題を特定するのにどんな助けでも大いに感謝されます。

記録のために：回転を使用しない場合、ツリーはノードをリークせず、通常の不平衡二分探索ツリーとして機能します（挿入とルックアップ用）。

編集：AJG85のコメントにより、私は観察を追加します：

クリーンアップの前にキー値（私の場合は32ビット整数）を出力するavl_search_tree :: avl_tree_nodeのデストラクタメソッドと、挿入されたばかりのキーを出力するavl_search_treeのinsertメソッドにprintf'checks'を追加しました。

次に、プログラムのエントリポイントで、ヒープにavl_search_treeを割り当て、昇順でキーを追加してから削除します。

AVLバランシングを有効にすると、ターミナルに次の出力が表示されます。

bool avl_search_tree::insert(const int&) : 1
bool avl_search_tree::insert(const int&) : 2
bool avl_search_tree::insert(const int&) : 3
bool avl_search_tree::insert(const int&) : 4
bool avl_search_tree::insert(const int&) : 5
bool avl_search_tree::insert(const int&) : 6
bool avl_search_tree::insert(const int&) : 7
bool avl_search_tree::insert(const int&) : 8
avl_search_tree::avl_tree_node::~avl_tree_node() : 1

これは、すべての挿入が成功したが、ルートのみが削除されたことを意味します。

AVL Balancingがコメントアウトされているので、通常の二分探索木のように機能します。端末出力は次のとおりです。

bool avl_search_tree::insert(const int&) : 1
bool avl_search_tree::insert(const int&) : 2
bool avl_search_tree::insert(const int&) : 3
bool avl_search_tree::insert(const int&) : 4
bool avl_search_tree::insert(const int&) : 5
bool avl_search_tree::insert(const int&) : 6
bool avl_search_tree::insert(const int&) : 7
bool avl_search_tree::insert(const int&) : 8
avl_search_tree::avl_tree_node::~avl_tree_node() : 1
avl_search_tree::avl_tree_node::~avl_tree_node() : 2
avl_search_tree::avl_tree_node::~avl_tree_node() : 3
avl_search_tree::avl_tree_node::~avl_tree_node() : 4
avl_search_tree::avl_tree_node::~avl_tree_node() : 5
avl_search_tree::avl_tree_node::~avl_tree_node() : 6
avl_search_tree::avl_tree_node::~avl_tree_node() : 7
avl_search_tree::avl_tree_node::~avl_tree_node() : 8

これは、すべてが適切にクリーンアップされることを意味します。

さて...どのようにして回転方法が問題であるという結論に達しましたか？コメント付きのAVLバランシングサブルーチンの下に、新しく挿入されたすべてのノードを左に回転させる行を追加しました。結果？AVLバランシングサブルーチンが有効になっている場合と同じです。

また、update_height（）メソッドに関しては、ツリーの構造を変更することはありません。

これで明らかになることを願っています。

編集2：

さらにいくつかのことを明確にするために、彼はavl_tree_nodeデストラクタがどのように実装されているかを示しています。

avl_search_tree::avl_tree_node::~avl_tree_node()
{
    printf("%s : %d\n", __PRETTY_FUNCTION__, *_key);

    if (_left_child != NULL) {
        delete _left_child;
    }

    if (_right_child != NULL) {
        delete _right_child;
    }

    if (_key != NULL) {
        delete _key;
    }
}

_left_childと_right_childは、ヒープに割り当てられたavl_tree_nodeオブジェクトへのポインターです。

編集3：

AGJ85の2番目のコメントのおかげで、私は問題を見つけました。私のrotateメソッドでは、ルートがシフトされるたびに、ツリーのルートポインタを新しいルートに更新する必要があることを忘れていました。

基本的に、ツリーのルートは常に最初に挿入されたノードを指しており、必要に応じてポインターを更新しなければ、rotateメソッドは実際に正しく構成された新しいツリーのルートをリークしていました。:)

AGJ85ありがとうございます！

4

3 に答える 3

3

AGJ85 さんの 2 回目のコメントのおかげで、問題が見つかりました。私の回転メソッドでは、ルートがシフトされるたびに、実際にツリーのルート ポインターを新しいルートに更新する必要があることを忘れていました。

基本的に、ツリーのルートは常に最初に挿入されたノードを指しており、必要に応じてポインターを更新しないと、回転メソッドは実際に正しく構成された新しいツリーのルートをリークします。:)

于 2011-08-03T09:03:33.677 に答える
2

編集-くそー-問題がすでに解決されていることはわかりませんでした（質問に答えてください）。それでも、この価値のある救助には、答えのないヒントがいくつかあるかもしれません。

よく調べていませんが、この行で間違っていると思います...

_right_child = new_root->_left_child;

問題は、その行ですでに上書きnew_root->_left_childされている可能性があることです...

_parent->_left_child = new_root;

あなたがすべきだと思うことは、最初に、次のようなローカル定義のブロックを用意することです...

avl_tree_node *orig_parent      = _parent;
avl_tree_node *orig_this        = this;
avl_tree_node *orig_left_child  = _left_child;
avl_tree_node *orig_right_child = _right_child;

次に、orig_ローカル変数を後の代入のソースとして使用します。これにより、ローテーション中のさまざまなポインターを介したデータ フローに関する心配がある程度軽減されます。オプティマイザーは、これについて心配する価値のある冗長な作業を取り除く必要がありますが、とにかくそれほど多くはありません。

いくつかの余分なポイント...

まず、C++ (および C) 標準では、先行するアンダースコアと 2 つのアンダースコアを持つ識別子が予約されています。それを尊重しないと、標準およびコンパイラ提供のライブラリとの驚きの相互作用を得ることができると主張されています-しかし、それはメンバー識別子のマクロに関連している必要があると思います. 末尾のアンダースコアは問題ありません。インクルード ガードに使用する傾向があります。

メンバー変数の一般的な規則は、先頭にmorを追加することm_です。さらに一般的なのは、おそらく、特別なプレフィックスやサフィックスがまったくないことです。

第 2 に、ノードに親リンクが格納されていない AVL ツリーを実装する方が簡単であることがわかる場合もあります (またはそうでない場合もあります)。私自身はまだ AVL ツリーを実装していませんが、赤黒ツリーを実装したことは一度あります。多くのアルゴリズムでは、最初のステップとして再帰的検索を含める必要があります。見つかったノードを記憶し、そのノードまでのルートを破棄する標準的な検索を行うことはできません。ただし、再帰的な実装はそれほど悪くはなく、ジャグリングするポインターが少なくなります。

最後に、一般的なヒント - このようなアルゴリズムを「予行演習」しようとすると、手順を追って厳密に作業し、関連するすべての情報源を確認しない限り、簡単につまずく可能性があります (私はすでにこれを変更しましたか?)。全段階で。速度を上げるために詳細の一部をスキップする習慣を身につけるのは非常に簡単です。便利な機械支援の予行演習は、デバッガーでコードを段階的に実行し、各ステップの結果が紙の予行演習と一致するかどうかを確認することです。

編集- もう1つ注意 - この文脈ではよくわからないので、これをヒントとは呼びません。私は通常、単純な構造体を使用してデータ構造ノードを実装します。データを非表示にすることはなく、メンバー関数があったとしてもほとんどありません。ほとんどのコードは、多くの場合「ツール」クラスで、データ構造から分離されています。これが古い「形状がそれ自体を描く」OOPの原則に違反していることは知っていますが、実際にはIMOの方がうまく機能します。

于 2011-08-02T19:34:02.177 に答える
1

コードで探していたバグを見つけたようです。（あなたが言うように、ルートが変更されたときにツリールートポインタを新しいルートに更新していませんでした。これは、リストの先頭またはツリーのルートへのポインタを返すリストおよびツリーの挿入/削除メソッドの一般的なパラダイムです。パラダイムが二度と間違いを犯さないことを覚えています。）

より高いレベルのビューでは、AVLツリーまたは赤黒木コードの問題を回避するために使用した手法は、代わりに、O（n）スペースとO（log）を使用して、それらと同様のパフォーマンスを持つAAツリーを使用することです。 n）挿入、削除、および検索の時間。ただし、AAツリーはコーディングが非常に簡単です。

于 2011-08-04T15:55:29.493 に答える