挿入メソッドのオーバーライド

AVL ツリーへの要素の挿入は、ツリーの再バランスが必要な場合がある点を除けば、BST への要素の挿入と同じです。新しい要素は常にリーフ ノードとして挿入されます。新しいノードを追加した結果、新しいリーフ ノードの祖先の高さが増加する可能性があります。新しいノードを挿入した後、新しいリーフ ノードからルートまでのパスに沿ったノードを確認します。アンバランスなノードが見つかった場合は、以下のコードのアルゴリズムを使用して適切な回転を実行します。

1 BalancePath(E e) {
2 要素 e を含むノードからルートまでのパスを取得します
図 26.9 に示すように 3;
ルート {
につながるパス内のノード A ごとに 4 5 A の高さを更新します;
6parentOfA を A の親とします
パス内の次のノードである 7、または A がルートの場合は null;
8
9 スイッチ (balanceFactor(A)) {
10 ケース -2: BalanceFactor(A.left) == -1 または 0
の場合 11 LL 回転を実行します。 // 図 26.2 を参照
他12個
13 LR 回転を実行します。 // 図 26.4 を参照
14 休憩;
15 case +2: BalanceFactor(A.right) == +1 または 0
の場合 16 RR ローテーションを実行します。 // 図 26.3 を参照
他17個
18 RL ローテーションを実行します。 // 図 26.5 を参照
19 } // スイッチの終了
20 } // for
の終わり 21 } // メソッドの終了

アルゴリズムは、新しいリーフ ノードからルートまでのパス内の各ノードを考慮します。パス上のノードの高さを更新します。ノードのバランスが取れている場合、アクションは必要ありません。ノードのバランスが取れていない場合は、適切な回転を実行します

以上が挿入メソッドのオーバーライドの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。