問題タブ [tree-rotation]

一連の値が与えられると、それらの値から形成できるさまざまな二分探索木が存在する可能性があります。たとえば、値 1、2、および 3 の場合、これらの値から作成できる 5 つの BST があります。

バランスの取れた二分探索木に基づく多くのデータ構造は、必要な二分探索木の不変条件を壊すことなく BST を再形成するためのプリミティブとしてツリーの回転を使用します。次に示すように、ツリーの回転を使用して、ノードをその親の上に引き上げることができます。

値のセットを含む BST が与えられた場合、その BST を同じ値のセットの任意の他の BST に変換することは常に可能ですか? たとえば、ツリーの回転を使用するだけで、上記の 5 つの BST のいずれかを他の BST のいずれかに変換できますか?

本の中でアルゴリズムの紹介 - 創造的なアプローチ、質問4.24：

T1 と T2 を 2 つの任意のツリーとし、それぞれに n 個のノードがあります。T2 と等しくなるように、T1 に最大 2n 回の回転を加えれば十分であることを証明してください。

二分探索木については、次のようなアルゴリズムを見つけました。

1. T2 のルートに等しい要素を見つけます。それをターゲット ルートと呼びましょう。

2. AVL ローテーション戦略を使用して、ターゲット ルートをローテーションし、T1 の新しいルートにします。
   このプロセス中に、複数のローテーションが実行される場合があります。

3. T1 と T2 の左部分木については、上記のように再帰的に処理します。
   T1 と T2 の右側のサブツリーについては、上記のように再帰的に処理します。

このアルゴリズムは、最悪の場合、O(N^2) で実行されます。

「任意ツリー」という言葉がよくわかりません。また、T1 を T2 に等しくする方法もわかりません。

誰でもこの質問を手伝ってもらえますか?

AVL ツリーには、Left-Left、Left-Right、Right-Left、Right-Right の 4 種類の変換があるようです。ただし、それ以外の状況も考えられるようです。私はこれをレフトバランスとして提出します:

左回転も右回転も、このツリーのバランスを取ることはできません。バランスをとるためにどのアルゴリズムを使用しますか?

これはシーケンス 20,10,5,30,40,57,3,2,4,35,25,18,22,27 です。新しく挿入されたすべてのノードをルートとして試してみましたが、うまくいきません。誰かが私に段階的な説明を教えてもらえますか?

AVL ツリーの実装で非常に奇妙な問題に直面しています。以下のコードを考えると、正しい回転なしでしか実行できません。そうすると、クラッシュするからです。私はすでにデバッグ、ファイルの削除、プロジェクトの再作成、再構築を試みましたが、どれもうまくいきませんでした。

事前に、コードが少しわかりにくい場合はお詫びします。私はブラジル人で、変数名はほとんどポルトガル語です。それが問題を解決する上で問題であることが判明した場合は、変数名を英語に変更します。

avl.hファイル：

avl.cファイル：

main.cファイル：

ご覧のとおり、右と左の回転関数 (rotaciona_dirおよびrotaciona_esqそれぞれ) は基本的にミラーなので、右の回転関数が機能しないというバグがあります。さまざまな呼び出しを試しましたが、現在はforテスト用にループを使用しているだけです。入力を減らすと、すべて正常に動作しますが、関数を呼び出す必要があるとすぐにrotaciona_dir、プログラムがクラッシュします。

IDE/コンパイラについては、Ubuntu 16.04 LTS システムで Code-Blocks IDE 13.12 を使用しています。

また、コードの改善や一般的なプログラミングのヒントも歓迎します。私自身は C プログラマーではありません (Python が私のメイン言語です) ので、これに対する答えは非常に単純かもしれません。

次のバイナリ ツリーがあり、最小数のツリー ローテーションを使用してターゲット バイナリ ツリー (投稿の 2 番目のツリー) に変換しようとしています。このツリーの理論上の最小回転数は 5 ですが、把握できる最小値は 6 回転です。回転もコピーしました。何が欠けているのでしょうか?

木： 1 \ \ 3 / \ / \ 2 5 / \ / \ 4 7 / \ / \ 6 11 / \ / \ 9 12 / \ 8 10

ターゲット ツリー: 1 \ \ 11 / \ / \ 9 12 / \ / \ 3 10 / \ / \ 2 5 / \ / \ 4 7 / \ 6 8

これまでに試した回転 (すべて 6 回の回転が必要):

注文1: Rotate left with root 7 and pivot 11 Rotate left with root 5 and pivot 11 Rotate left with root 3 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 9 注文2: Rotate left with root 7 and pivot 11 Rotate left with root 5 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 3 and pivot 11 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 9

注文 3: Rotate left with root 7 and pivot 11 Rotate left with root 5 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 11 Rotate left with root 3 and pivot 9

注文 4: Rotate left with root 7 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 5 and pivot 11 Rotate left with root 3 and pivot 11 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 9

注文5: Rotate left with root 7 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 5 and pivot 11 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 11 Rotate left with root 3 and pivot 9