問題タブ [avl-tree]

avl ツリーの検索が高速であるいくつかの場所でそれを読みましたが、理解できませんでした。私が理解しているように: 赤黒ツリーの最大高さ = 2*log(N+1) AVL ツリーの高さ = 1.44*logo(N+1)

AVLが短いからですか？

ツリーに新しいアイテムを追加した後、AVLツリーのバランスをとろうとしていますが、NPEを取得し続けています。私はそれを私のbalance（）メソッド、あるいはもっと具体的には私のrotateLeft（）メソッドとrotateRight（）メソッドに関係するものに絞り込んだと思います。これが私のAVLTreeクラスです。

私が言及した方法を間違って行っているのですか、それともバランスを取る前にツリーに間違って追加しているのですか？

Add メソッドと Remove メソッドを使用して AVL ツリーを作成しました。ただし、ツリーを視覚的な形式で出力する必要があります。たとえば、バランス ツリーに現在 1、2、3 が含まれている場合、次のようになります。

これを行うための比較的簡単な方法はありますか?? (値が追加または削除された後、私のツリーは常に適切にバランスが取れていると想定できます。)

順序付けられていないセットs{3,6,5,1,2,4}があり、AVLツリーを構築する必要があるとします。
これで問題ありません...基本的な回転を理解し、ここでこのポイントに到達します。

しかし、4を挿入しようとすると、すべてがバラバラになり、最終的な答えは（左の）として得られます。

そして、それを分解すると、同じローテーションを実行してスタックする
ので、このAVLに有効な親とローテーションを実行するにはどうすればよいですか？

そして私の解決策は有効ですか？

以下のAVLツリーを考えます。

右の40で1回転するだけで大​​丈夫ですか？次のようにします。

それでも、左側のサブツリーと比較して-+1の高さを持つAVLプロパティに準拠しています。

答えでは、それは二重回転を行うので、上の35のサブツリーは次のようになります。

両方がheightプロパティに違反していない場合、いつ2回転するのか、いつ1回転するのかわかりません。

これまで私は攻撃の計画を立てて、これをどのように実行できるかを確認してきました。これが私が持っているものです。

bool isEmpty() const-空の場合はtrueを返し、そうでない場合はfalseを返します

int getSize()-辞書に保存されている単語の数を返します

void insert (String word)-まだ存在しない場合は辞書に単語を挿入し、そうでない場合は更新します。

boolfind(String word, WordNode & x)-単語が存在する場合はtrueを返し、データをxに配置します。

void printSorted()-ツリー内の単語を辞書式順序で出力します（指定）

void remove (String word)-ノードの遅延削除を実装します

私は自分がやりたいことの概念を持っており、AVL木がどのように機能するかを理解しています。しかし、実際にコードを書くことになると、私は完全に行き詰まります。誰かが私が始めるのを手伝ってくれるでしょうか？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

編集2：

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

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

編集3：

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

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

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

「Coding Interview Cracked」という本を読みましたが、BST のバランスが取れているかどうかを確認するには、最大高と最小高の差を見つければよいのですが、それが 100% 正しいかどうかはわかりません。カウンターテストケースが見つかりませんが。

このアプローチが正しいかどうかを誰でも確認できますか。

木のバランスが取れているかどうかを確認するため。

実装しようとしている AVL ツリーでいくつかのコンパイル エラーが発生します。何かが列挙子全体を捨てています。ヘルパークラスを実装しようとするまで、問題なくコンパイルされました。BTNode 自体がプライベートのネストされたクラスであることに関係があると考えていましたが、何が起こるかを確認するためだけに公開しようとしましたが、役に立ちませんでした。

私はこれに少し困惑しています。変換が行われるべきではありません。

どんな助けでも大歓迎です。

ソース コードは次のとおりです。コンパイル エラーが発生している場所に注意し、読みやすくするためにさまざまなネストされたクラスを分割しました。

ノードクラス--

列挙ヘルパークラス --

--

--

追加...

rebalance()AVL の機能の実装に関する記事をいくつか見ました。
各挿入の後、挿入ノードの先祖のバランスをチェックする必要があります。
ということで、先祖のバランスを確認するために、挿入ノードの親を知りました。

しかし、親ポインターを使用せずにそれを行う方法は他にあるのでしょうか?
たとえば、ノード構造体: