問題タブ [tree-balancing]

AVL-treeでノードのバランスを計算する最良の方法を探しています。私はそれが機能していると思っていましたが、いくつかの重い挿入/更新の後、正しく機能していないことがわかりました(まったく)。

これは一種の 2 つの部分からなる質問です。最初の部分は、サブツリーの高さを計算する方法です。「ノードの高さは、そのノードから葉までの最長の下り経路の長さです」という定義を知っています。 ." 私はそれを理解していますが、実装に失敗しています。さらに混乱させるために、ツリーの高さに関するウィキペディアでこの引用を見つけることができます。

2番目の部分は、AVLツリーのサブツリーのバランス係数を取得することです。 「あなたLとサブツリーの高さを取得してからR差し引く」RLという概念を理解するのに問題はありません。そして、これは次のように定義されています。BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]

ウィキペディアを読むと、AVL ツリーへの挿入を説明する最初の数行で次のように述べられています。

続いて、「バランス ファクターが 2 または -2 になる場合、このノードをルートとするツリーはバランスが取れていないため、ツリーのローテーションが必要です。ツリーのバランスをとるには、せいぜい 1 回または 2 回のローテーションが必要です。」- 問題なく把握できます。

しかし（はい、常にしかしがあります）。

ここで混乱します。テキストには、「R のバランス係数が 1 の場合、そのノードの (外部) 右側で挿入が発生し、左回転が必要であることを意味します」と記載されています。しかし、私が引用したように、バランス係数が範囲内[-1, 1]にある場合、バランスをとる必要はないとテキストが述べていることを理解していますか?

概念の理解に非常に近づいていると感じています。ツリーのローテーションを減らし、通常のバイナリ検索ツリーを実装し、AVL ツリーを把握しようとしていますが、その本質的なひらめきが欠けているようです。

編集：私は常にコードで何かを把握するのが簡単だったので、コード例は学術的な公式よりも好まれていますが、どんな助けも大歓迎です.

編集：すべての回答を「承認済み」としてマークできたらいいのにと思いますが、私にとっては、NIckの回答が最初に「あはは」になったものでした。

AVL ツリーの実装を依頼する課題に取り組んでいます。回転方法が正しいと確信していますが、いつ使用するかを理解するのに苦労しています。

たとえば、本の説明では、ノード/要素を挿入するために下ったのと同じ道を登る必要があると書かれています。ただし、親ポインターを持つことはできません。

最新のコード:

ここでやりたいことは、ツリーを元に戻すことですが、ノードを挿入した後でのみバランスを確認できます。したがって、これはelse節にあります。

R Samuel Klatchko が提案したバランスコードも入れてみましたが、各インサートのバランスを確認しました。例: 7、9、5、3、および 1 を連続して挿入すると、1 を挿入しようとすると null ポインター例外が発生します。

編集：上記の理由の1つは、私が高さを行っていた方法に関係している可能性があります. height() を使用して毎回高さを計算すると、単一の右回転で正常に動作しますが、AVL ツリーの O(log(n)) 時間を壊します。

これを達成する方法について何か考えはありますか？

私はできるだけ自分自身を明確にするように努めます。隣接リストモデルに基づく：http ：//articles.sitepoint.com/article/hierarchical-data-database

この木のバランスをとる方法が必要です

次のようなものに：

サンプルコードに基づく：

次のようなフラットなhtmlテーブルを出力できるようにコードを変更しました。

$ super_parent = '0000'はノードエントリをフラットリストに残しました：

しかし、親を移動したり回転させたりせずに、これらすべてをバランスの取れたツリーに再編成する方法が必要です。データベースに複製テーブルを作成し、2番目のクエリを実行して別のBinarayツリーを表示または作成することは考えられますが、次のようなフラットツリーを再編成できる可能性があると思いました。

左から右へ。0は、親またはsuper_parent0000を表します。

これを実行したい理由は、プロジェクトの別のアルゴリズムの基礎となる元のツリーから仮想ツリーを作成できるようにするためです。

前もって感謝します。

ボブ

Haskell で自己均衡ツリーを設計しています。練習として、そして後ろ手に持っているといいからです。

以前は C と Python で、単純なバランス ルールのため、Treaps と Splay Trees を好みました。R/B ツリーは、価値がある以上に手間がかかるように思えたので、私はいつも嫌いでした。

現在、Haskell の機能的な性質により、状況が変わったように見えます。R/B 挿入関数を 10 行のコードで記述できます。一方、Treaps は乱数ジェネレーターを格納するためにラップする必要があり、Splay Trees はトップダウンで実行するのが面倒です。

他の種類の木の経験はありますか？関数型言語のパターン マッチングとトップダウンの性質を利用するのに優れているのはどれですか?

手作業で要求されたツリー(bst>avl)のバランシングを実行しましたが、本当に簡単だったので、正しく実行できたかどうかはわかりません。

初期状態: 'a' は 'b' (左) と 'e3' (右) の親、'b' は 'e1' (左) と 'e2' (右) の親です。

右回転を適用すると、次のようになります。

左側に子 'e1'、右側に子 'a' を持つ 'a' の代わりに 'b' を使用すると、'a' は左側に 'b' の 'e2' を取得します。

だから質問：

1. e1 自体が他の要素を含むサブツリーまたはノードである場合でも、このローテーションを実行できますか?
2. 2. e2 と e3 がない場合でも、このローテーションを実行できますか?

例 11; 12;16

初期状態: 16 は 13 の親であり、13 は 10 の親です。それから実行できますか: 13 は 10 (左) と 16 (右) の親です

私はそれが単純化されていることを知っていますが、理論は、それが明確であると仮定して、これらのことをカバーしていないことがよくあります。手伝ってくれてありがとう、

バランスがとれていることを確認するために、作成した二分探索木を変更する必要があります。私の指示に従って、add メソッドと remove メソッドを変更するだけです。これが私が現在持っているものです：

私はこの課題を順を追って説明してくれる人を探しているわけではありません。コードを途中で壊さないように、これをどのように行うべきかについてのアドバイスを探しているだけです。何かが追加または削除されるたびにツリーのバランス係数をチェックする効果を得るために何かを行い、ツリーを再構築するか、バランスが取れていない場合は「回転」します。

事前にアドバイスをいただきありがとうございます。:) すべてのヒントに感謝します。

-クリス

更新：「doAVLBalance」でメンバー関数「isBalanced（）」、「isRightHeavy（）」、「isLeftHeavy」を認識できないため、「Balancing」を機能させることができません。そして、私は理由がわかりません！Sashの例（3番目の回答）を正確に試しましたが、「減速に互換性がありません」と表示され、修正できませんでした...それで、自分のやり方で試してみました...そして、これらのメンバー関数が存在しないと表示されます。彼らは明らかにそうします。

「エラー：クラス「IntBinaryTree：TreeNode」にはメンバー「isRightHeavy」がありません。過去4時間試行した後、スタックします:(。以下の更新されたコード、助けていただければ幸いです!!

文字列ベースの二分探索木を作成していて、それを「バランスのとれた」木にする必要があります。どうすればよいですか？*助けてください!! 前もって感謝します！

BinarySearchTree.cpp：

BinarySearchTree.h：

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

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

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

データ構造に関する本を読んでいますが、左バランス バイナリ ツリーは、葉が最後のレベルの左端の位置のみを占めるツリーであると書かれています。

これは私には少しあいまいに思えました。これは、葉が根の左側にのみ存在し、レベル全体に分布していることを意味しますか、それともツリー全体の左側にのみ葉が存在することを意味しますか。正確に何がバランスの取れたままになっているのですか？

私の推測が答えのいずれかをカバーしているかどうかはわかりません。そのため、誰かが助けてくれれば大歓迎です:-)。

木がバランスが取れているかどうかを教えてくれるプログラムを書きたいです。この場合、バランスが取れているとは、同じ高さまたは高低差が 1 であることを意味します。

ここまで書いてきたのですが、身長差1ではうまくいきません。