CodeGym /Javaコース /Python SELF JA /ツリーのバランシング: AVL木

ツリーのバランシング: AVL木

Python SELF JA

レベル 55 , レッスン 3

使用可能

4.1 バランスされていないツリーの問題

通常の（バランスされていない）ツリーでは、要素を追加するときに不愉快な結果になることがあります。

1. ツリーの高さの増加:

バランスされていないツリーでは、高さがn（nはノードの数）に達することがあり、パフォーマンスの劣化を引き起こします。

基本的な操作（検索、挿入、削除）の実行時間は、最悪の場合O(n)になります。

2. ノードの不均一な分布:

バランスされていないツリーでは、あるサブツリーが他よりも多くのノードを含むことがあり、メモリの非効率な使用と処理時間の増加を引き起こします。

3. 操作時間の悪化:

バランスされていないツリーでは、検索、挿入、削除の操作により多くの時間がかかります。これはツリーの高さが増加したためです。

バランスされていないツリーの例:

この例では、ツリーは実際にはリンクリストに変換され、操作の実行時間は線形になります。

AVL木（その発明者であるアデルソン＝ヴェルスキーとランドイスにちなんで名付けられた）は、任意のノードの左サブツリーと右サブツリーの高さの差が1を超えないようにした、バランスされたバイナリ検索ツリーです。

AVL木の特性:

1. バランス性:

任意のノードの左サブツリーと右サブツリーの高さの差は1を超えません。

これにより、ツリーの高さはO(log n)になり、nはノードの数であり、検索、挿入、削除の操作の効率的な実行が保証されます。

2. バイナリ検索ツリー:

AVL木は、バイナリ検索ツリーのすべての特性を持ちます：任意のノードにおいて、左サブツリーのすべてのキーはノードのキーより小さく、右サブツリーのすべてのキーはノードのキーより大きいです。

3. 自動バランス:

挿入または削除操作の後、ツリーをバランスを保つためにリバランスします。

回転は、ノードを挿入または削除した後にAVL木のバランスを回復するために行われる操作です。4つのタイプの回転があります：左回転、右回転、左-右回転、右-左回転。

1. 左回転 (Left Rotation):

左回転では、ノードxが上昇し、その右子ノードyがその親になります。yの左サブツリーがxの右サブツリーになります。

2. 右回転 (Right Rotation):

右回転では、ノードxが上昇し、その左子ノードyがその親になります。yの右サブツリーがxの左サブツリーになります。

3. 左-右回転 (Left-Right Rotation):

最初に左子ノードで左回転を行い、その後にノード自体で右回転を行います。

4. 右-左回転 (Right-Left Rotation):

最初に右子ノードで右回転を行い、その後にノード自体で左回転を行います。

AVL木での基本的な操作には、挿入、削除、検索が含まれます。

挿入 (Insertion)

新しいノードをAVL木に挿入し、必要に応じてバランスを取ります。

手順:

ノードの挿入:
- ツリーのルートから始め、新しいノードの正しい場所を見つけるために再帰的にその値を現在のノードと比較します。
- 新しいノードを見つけた場所に挿入します。これは通常のバイナリ検索ツリーと同様です。
高さの更新:
- 挿入後、新しいノードからルートまでのパスにあるすべてのノードの高さを更新します。
ツリーのバランス:
- 新しいノードからルートまでのパスにある各ノードのバランスをチェックします。
- もしノードのバランスが崩れている（左と右のサブツリーの高さの差が1を超えている）場合は、バランスを回復するために適切な回転を行います。