問題タブ [tree-balancing]

練習用に C++ で古いバイナリ ツリーから AVL ツリーを作成しましたが、正しく動作しません。ノードの高さを正しく更新していない可能性があると思いますが、問題の根本を突き止めることはできません (ヘルパー関数 getHeight、setHeight、getBalance と関係があると 90% 確信しています)。

いくつかのテスト実行例..:

6,3,4 を追加すると、Right Rotation が発生し、RL 回転が発生するはずです

同様に、20、30、25 を追加すると、LR 回転が発生するはずのときに LL 回転が発生します

20,30,10,5,6 を追加すると、RL 回転が発生するはずのときに、2 つの別々の右回転が発生します

これをさらに理解するためのヒント/ヘルプをいただければ幸いです。他に役立つ情報があればお知らせください。

ありがとうございました。

指定されたツリーがバランスであるかどうかを確認する際に混乱しています。ツリーのバランスが取れているかどうかを確認するために、mod (左側のサブツリーの高さの差 - 各ノードの右側のサブツリーの高さ) を計算します。
ツリーの例を図で見てみましょう。youtube での講義の赤いノードの差は 2 として計算されます。左のサブツリーの高さが 1 で、右のサブツリーが -1 であるとのことでした。しかし、これまでのところ、高さは左のサブツリーが2で右のサブツリーが0であることを理解しています

誰でもこの混乱を解消するのを手伝ってください。

doublelyLinkedList を取り込んでバランスのとれた二分探索木を構築するこの関数を作成しようとしています。TreeNode.left は前のポインターに相当し、TreeNode.right は次のポインターに似ています。ここのプログラムからインスピレーションを得ていますが、うまくいきません:

http://www.geeksforgeeks.org/in-place-conversion-of-sorted-dll-to-balanced-bst/

火曜日に中間試験があるのですが、赤黒木を理解するのに苦労しています。木がバランスが取れていることをどのように知ることができますか? 私はそれが正しい量の黒いノードと黒い深さと関係があることを知っています. しかし、私はそれをよく理解していません。ツリーの回転はこれに基づいているため、これを知る必要があります。誰かが段階的な説明を提供できれば、それは素晴らしいことです。ありがとう！

この演習では、受講者に AVL ツリーからノードを削除するよう求めます。この場合、最も深い深さと最も浅い深さの差が 1 より大きいため、ある程度のバランス調整が必要です。それとも関係ありませんか？

問題の AVL ツリーの画像

ヒットとその要素に応じてノードのバランスを取る BST に取り組んでいます。ヒットとは、find()、contains() などを使用してノードが見つかったときに増加する属性です。ツリーのルートはノードです。ヒット数が最も多い。ヒットをインクリメントした後にツリーのバランスを取る balance メソッドを除いて、私のコードはすべて問題ありません。変更された AVL ツリーの回転メソッド ( https://users.cs.fiu.edu/~weiss/dsj2/code/weiss/nonstandard/Rotations.java ) を使用しています。ここでは、要素ではなく、ヒット数を比較します。ノード。何を試しても機能しません。ツリーを正しくバランスさせることができません。これまでのコードは次のとおりです。

現在、balance メソッドは、回転するはずのノードを削除するだけです。デバッグを試みましたが、何が問題なのかわかりませんでした。

どこで問題が発生しているのかわかりませんが、MQL4/MQL5言語に翻訳された AVL 実装で奇妙なエラーが発生しています。

失敗した場合、私はどちらかに入ります

• 同じノードの問題を再帰的に指す

また

• 親のない切り離されたノード、

したがって、バランスを取りながら、ヌルポインターの問題が発生しています。

テストケース:

MetaTrader4/5 Terminal [ Journal ]のコピー/ペーストを以下に同封します

パスケース：

失敗したケース:

これはMQL4/MQL5コードですが、言語は多かれ少なかれ CPP を反映しています。

Cpp とヘッダー ファイルの両方のソース:

リクエストごとの詳細: MQL スクリプトのテスト:

端末出力: