ローテーションの実装

アンバランスなツリーは、適切な回転操作を実行することでバランスがとれます。 「ツリーの再バランス」セクションでは、ノードで回転を実行する方法を説明しました。以下の図に示すように、以下のコードは LL 回転のアルゴリズムを提供します。

1 BalanceLL(TreeNode A, TreeNodeparentOfA) {
2 B を A の左の子とします。
3
4 if (A がルート)
5 B を新しいルートとします
その他 6 {
7 if (A はparentOfA の左の子です)
8 B をparentOfA の左の子とします。
他9個
10 B をparentOfA の右側の子とします。
11 }
12
13 B.right を A.left に代入して、T2 を A の左サブツリーにします。
14 A を B.right;
に代入して、A を B の正しい子にします。 15 ノード A とノード B の高さを更新します;
16 } // メソッドの終了

ノード A と B の高さは変更できますが、ツリー内の他のノードの高さは変更されないことに注意してください。 RR、LR、RL の回転も同様の方法で実装できます。

以上がローテーションの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。