Javaプログラミングにおいて、効率的なデータの検索と挿入は、システム全体のパフォーマンスに大きく影響します。特に大量のデータを扱う場合、単なる二分探索木ではデータが偏ってしまい、パフォーマンスが低下することがあります。これを防ぐために用いられるのが、自己平衡機能を持つデータ構造であるAVLツリーです。本記事では、AVLツリーの仕組みと、そのJavaでの実装方法について、特に検索と挿入操作に焦点を当てて解説していきます。AVLツリーを理解することで、データの効率的な管理と操作が可能になり、より高度なアルゴリズム設計が実現できます。
AVLツリーとは
AVLツリーは、1962年にG.M. Adelson-VelskyとE.M. Landisによって提案された、自己平衡二分探索木の一種です。AVLツリーは、各ノードが保持する高さバランスを常に管理し、挿入や削除操作の際にツリーが左右どちらかに偏らないように調整します。この自己平衡機能により、最悪の場合でも木の高さがO(log n)に保たれ、効率的な検索、挿入、削除が可能です。
二分探索木ではノードが左子ノードよりも大きく、右子ノードよりも小さいという基本的なルールが適用されますが、AVLツリーではさらに、「任意のノードにおける左右の部分木の高さ差が1以内である」という追加の制約が課されます。この制約によって、データが均等に分散され、パフォーマンスの低下を防ぎます。
AVLツリーの自己平衡アルゴリズム
AVLツリーの最大の特徴は、挿入や削除操作のたびにツリーが自己平衡状態を保つことです。これは、各ノードに「高さバランス係数」（バランスファクター）を保持することで実現されます。バランスファクターとは、ノードの左部分木と右部分木の高さの差を指し、この差が1以上になるとツリーは不均衡と見なされます。AVLツリーでは、以下の条件を満たすことで自己平衡を保ちます。
バランスファクターのチェック
バランスファクターは、各ノードの左部分木の高さと右部分木の高さの差を計算して得られます。この差が-1、0、1の範囲内であれば、ツリーは平衡状態にあると言えます。しかし、差が2または-2となった場合、ツリーは不均衡と見なされ、修正が必要です。
回転操作によるバランス調整
バランスを失った際に、ツリーを再び平衡状態に戻すためには「回転操作」が使われます。回転操作には、次の4つの種類があります。
- 左回転（Single Left Rotation）: 右部分木が高くなりすぎた場合に適用される操作です。
- 右回転（Single Right Rotation）: 左部分木が高くなりすぎた場合に適用される操作です。
- 左-右回転（Double Left-Right Rotation）: 左部分木の右部分木が高い場合に適用される複合操作です。
- 右-左回転（Double Right-Left Rotation）: 右部分木の左部分木が高い場合に適用される複合操作です。
これらの回転操作により、ツリーは効率的に平衡状態を取り戻します。回転後、各ノードのバランスファクターが再計算され、平衡が保たれます。
JavaでのAVLツリーの実装
JavaでのAVLツリーの実装は、基本的な二分探索木の構造に回転操作やバランスチェック機能を追加したものです。各ノードには、データ、左右の子ノードへの参照、そしてバランスを管理するための高さを保持します。ここでは、簡単なAVLツリーのクラス構造を例として紹介します。
基本的なノードクラスの定義
まず、AVLツリーの各ノードを定義するクラスを作成します。各ノードはデータ、左子ノード、右子ノード、およびそのノードの高さを保持します。
class Node {
int key, height;
Node left, right;
Node(int key) {
this.key = key;
this.height = 1; // 新規ノードの初期高さは1
}
}AVLツリーのメインクラスの定義
次に、AVLツリー全体を管理するクラスを作成します。このクラスには、ノードの挿入、削除、バランス調整などの主要なメソッドが含まれます。
class AVLTree {
Node root;
// ノードの高さを取得するヘルパーメソッド
int height(Node N) {
return (N == null) ? 0 : N.height;
}
// 右回転操作
Node rightRotate(Node y) {
Node x = y.left;
Node T2 = x.right;
// 回転操作
x.right = y;
y.left = T2;
// 高さを更新
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
return x;
}
// 左回転操作
Node leftRotate(Node x) {
Node y = x.right;
Node T2 = y.left;
// 回転操作
y.left = x;
x.right = T2;
// 高さを更新
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
return y;
}
// バランスファクターを取得するメソッド
int getBalance(Node N) {
return (N == null) ? 0 : height(N.left) - height(N.right);
}
}挿入操作の基本構造
このメインクラスに、ノードを挿入するメソッドを追加します。挿入後、バランスが崩れていれば、必要に応じて回転操作を実行します。
Node insert(Node node, int key) {
// 通常の二分探索木の挿入操作
if (node == null)
return new Node(key);
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
else
return node; // 重複キーは許可しない
// ノードの高さを更新
node.height = 1 + Math.max(height(node.left), height(node.right));
// バランスファクターを取得してバランスを確認
int balance = getBalance(node);
// バランスが崩れていれば、回転操作を適用
if (balance > 1 && key < node.left.key)
return rightRotate(node);
if (balance < -1 && key > node.right.key)
return leftRotate(node);
if (balance > 1 && key > node.left.key) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
if (balance < -1 && key < node.right.key) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}この実装により、挿入操作を行うたびにAVLツリーが自動的に平衡を保つことができます。
挿入操作のアルゴリズム
AVLツリーにおける挿入操作は、基本的な二分探索木の挿入操作に自己平衡の仕組みを加えたものです。挿入は通常の二分探索木のように、ルートノードから新しいノードを適切な位置に配置しますが、挿入後にツリーが不均衡になる可能性があるため、必要に応じてバランス調整（回転操作）を行います。
挿入の手順
- 通常の二分探索木の挿入
まず、挿入するキーがルートノードより小さい場合は左部分木に、大きい場合は右部分木に挿入します。この手順は通常の二分探索木と同様で、再帰的に進行します。 - ノードの高さの更新
挿入後、挿入されたノードを含む部分木の各ノードの高さが更新されます。これは、左右の部分木の高さを比較し、その最大値に1を加えたものが新しい高さとなります。 - バランスファクターの計算
各ノードのバランスファクター（左部分木の高さと右部分木の高さの差）を計算します。バランスファクターが-1、0、1の範囲内であれば平衡状態ですが、バランスファクターが2または-2となった場合、ツリーは不均衡です。
不均衡な場合の調整方法
不均衡が発生した場合、次の4つのケースに応じて適切な回転操作を適用します。
1. 左左（LL）ケース
バランスファクターが2で、挿入されたキーが左部分木の左部分にある場合は、右回転（Single Right Rotation）を行います。
例:
5
/
3
/
2 ← 新しく挿入されたノード この場合、ノード5を中心に右回転します。
2. 右右（RR）ケース
バランスファクターが-2で、挿入されたキーが右部分木の右部分にある場合は、左回転（Single Left Rotation）を行います。
例:
3
\
5
\
7 ← 新しく挿入されたノード この場合、ノード3を中心に左回転します。
3. 左右（LR）ケース
バランスファクターが2で、挿入されたキーが左部分木の右部分にある場合は、まず左回転を行い、続いて右回転を行う（Double Rotation）。
例:
5
/
2
\
3 ← 新しく挿入されたノード まずノード2を中心に左回転し、その後ノード5を中心に右回転します。
4. 右左（RL）ケース
バランスファクターが-2で、挿入されたキーが右部分木の左部分にある場合は、まず右回転を行い、続いて左回転を行います。
例:
3
\
7
/
5 ← 新しく挿入されたノード まずノード7を中心に右回転し、その後ノード3を中心に左回転します。
挿入操作後の再平衡
これらの回転操作によってツリーは再び平衡状態に戻り、挿入後も効率的な検索や挿入を保証します。挿入操作の時間計算量はO(log n)であり、大規模なデータに対しても高速に操作を行うことができます。
挿入後のバランス調整
AVLツリーでは、ノードを挿入した後にツリーのバランスが崩れてしまう場合があります。この不均衡を修正するために、バランス調整として「回転操作」を行います。挿入後のバランス調整は、ツリー全体の高さをできる限り低く保つために重要で、これにより検索や挿入操作が常にO(log n)の時間で実行されることが保証されます。
バランスファクターの確認
バランス調整の第一歩は、各ノードのバランスファクターを確認することです。バランスファクターは、左部分木の高さと右部分木の高さの差であり、この差が-1、0、1のいずれかであればバランスが取れています。しかし、差が2または-2の場合は、ツリーが不均衡であることを意味します。
不均衡が発生した場合、次の4つのケースに従って適切な回転操作が行われます。
回転操作の詳細
不均衡を修正するために行う回転操作は、以下の4つです。
1. 右回転（Single Right Rotation）
左部分木が高すぎる場合に適用される回転です。
バランスファクターが2で、左部分木の左側に新しいノードが挿入された場合に行います。この操作により、ツリーの高さが低くなりバランスが取れます。
例:
5
/
3
/
2 ← 新規挿入この場合、ノード5を中心に右回転することでバランスを取り戻します。
2. 左回転（Single Left Rotation）
右部分木が高すぎる場合に適用される回転です。
バランスファクターが-2で、右部分木の右側に新しいノードが挿入された場合に行います。この回転により、右に偏ったツリーの高さが低くなります。
例:
3
\
6
\
8 ← 新規挿入この場合、ノード3を中心に左回転を行います。
3. 左右回転（Double Left-Right Rotation）
バランスファクターが2で、左部分木の右側に新しいノードが挿入された場合に行う複合操作です。まず左回転を行い、その後右回転を行います。
例:
5
/
2
\
3 ← 新規挿入まずノード2を中心に左回転を行い、その後ノード5を中心に右回転を行います。
4. 右左回転（Double Right-Left Rotation）
バランスファクターが-2で、右部分木の左側に新しいノードが挿入された場合に行う複合操作です。まず右回転を行い、その後左回転を行います。
例:
3
\
8
/
6 ← 新規挿入まずノード8を中心に右回転を行い、その後ノード3を中心に左回転を行います。
回転操作後の効果
回転操作によってツリーは再び平衡を保ち、挿入前の効率的な状態に戻ります。これにより、後続の検索や挿入、削除操作も効率的に行うことができます。
左右回転とその効果
AVLツリーにおけるバランス調整には、単回転と複回転の2種類があります。単回転は1回の回転操作でバランスを修正する方法で、左右どちらかに偏ったツリーを単純に回転させて調整します。一方、複回転は、2回の回転操作を連続して行うことで、より複雑な不均衡を解消します。左右回転の適用方法と効果について詳しく見ていきます。
単回転（Single Rotation）
単回転には、左回転と右回転の2つがあります。ツリーが特定の方向に偏っている場合、1回の回転操作でバランスを取ることが可能です。
右回転（Single Right Rotation）
右回転は、左部分木が高すぎる場合に適用します。新しく挿入されたノードが左部分木の左側にある場合に使用されます。この操作により、左部分木が減少し、ツリーが平衡を保つようになります。
例:
5
/
3
/
2 ← 新しく挿入されたノード右回転の結果:
3
/ \
2 5左回転（Single Left Rotation）
左回転は、右部分木が高すぎる場合に適用します。新しく挿入されたノードが右部分木の右側にある場合に使用され、ツリーの右側の高さを減少させます。
例:
3
\
6
\
8 ← 新しく挿入されたノード左回転の結果:
6
/ \
3 8複回転（Double Rotation）
複回転は、単回転では解消できない複雑な不均衡を解消するために使用します。複回転には、左-右回転（Left-Right Rotation）と右-左回転（Right-Left Rotation）の2種類があります。
左-右回転（Double Left-Right Rotation）
左部分木の右側に新しいノードが挿入された場合に適用されます。まず左部分木で左回転を行い、その後右回転を実行します。
例:
5
/
2
\
3 ← 新しく挿入されたノードまずノード2を中心に左回転し、その後ノード5を中心に右回転します。
結果:
3
/ \
2 5右-左回転（Double Right-Left Rotation）
右部分木の左側に新しいノードが挿入された場合に適用されます。まず右部分木で右回転を行い、その後左回転を実行します。
例:
3
\
8
/
6 ← 新しく挿入されたノードまずノード8を中心に右回転し、その後ノード3を中心に左回転します。
結果:
6
/ \
3 8回転操作の効果
回転操作を適用することで、AVLツリーは常に平衡状態を保ち、挿入や検索操作の効率が保証されます。これにより、最悪の場合でもO(log n)の計算量を維持し、大規模なデータセットでも高速な操作が可能になります。
二分探索木における検索操作
AVLツリーは、二分探索木の特徴を持ちながら、常に自己平衡状態を保つことで検索操作の効率を保証します。通常の二分探索木では、データが一方向に偏ると最悪の場合O(n)の時間がかかることがありますが、AVLツリーではそのような偏りが発生しないため、検索操作の時間計算量が常にO(log n)に保たれます。ここでは、AVLツリーでの検索操作の流れとそのメリットについて解説します。
AVLツリーにおける検索の基本操作
検索操作は、通常の二分探索木と同じ方法で行われます。ルートノードから始め、次の手順で進行します。
- ルートノードのキーと検索対象のキーを比較
- 検索対象のキーが現在のノードのキーより小さい場合、左部分木に進みます。
- 検索対象のキーが現在のノードのキーより大きい場合、右部分木に進みます。
- 部分木の探索
進んだ部分木に対して同様の操作を再帰的に繰り返します。キーが一致するまでこの操作を続け、キーが一致したノードが見つかれば、そのノードの値を返します。 - キーが見つからない場合
探索を進めていき、部分木が存在しない場所に到達した場合、検索対象のキーはツリー内に存在しないことが確定します。
例として、次のAVLツリーに対してキー「6」を検索する場合の流れを考えます。
8
/ \
4 10
/ \
2 6- ルートノード8と検索キー6を比較します。6は8より小さいため、左部分木に進みます。
- 次にノード4と6を比較します。6は4より大きいため、右部分木に進みます。
- ノード6に到達し、キーが一致したため検索が成功します。
検索操作の計算量
通常の二分探索木では、データが偏っているとツリーの高さがデータ数に比例して増加し、最悪の場合O(n)の時間がかかります。しかし、AVLツリーでは各ノードが自己平衡を保つため、ツリーの高さは常にO(log n)に抑えられます。このため、検索操作の時間計算量もO(log n)となり、効率的な検索が可能です。
AVLツリーの検索操作のメリット
AVLツリーを用いることで、以下のような利点があります。
- 最適なパフォーマンス
平衡が保たれているため、データの検索にかかる時間が常に一定の範囲内に収まり、パフォーマンスが安定します。 - 効率的なデータ操作
データがランダムに挿入されてもツリーの構造が均等に保たれるため、大規模データを扱う際にも検索操作が効率的です。 - 汎用性の高いデータ構造
AVLツリーは、検索の効率性を要求されるあらゆるシステムやアプリケーションに適用でき、データベースや検索エンジンなどの基盤技術にも応用されています。
AVLツリーによる検索操作は、データの規模にかかわらず高速かつ安定して実行できるため、アルゴリズム設計において非常に有用です。
挿入と検索の計算量
AVLツリーの大きな利点は、挿入と検索操作の計算量が常にO(log n)に保たれることです。これは、ツリーが常に自己平衡を保つため、ツリーの高さがn（ノード数）の対数オーダーに収束するためです。ここでは、AVLツリーの挿入と検索の計算量について詳しく見ていき、他のデータ構造との比較も行います。
挿入操作の計算量
AVLツリーでの挿入操作は、以下の3つのステップに分けられます。
- 通常の二分探索木と同様に挿入場所を決定する
挿入するノードの位置を見つけるために、ルートノードから再帰的にツリーを下りていきます。このステップの計算量は、ツリーの高さに依存し、最悪でもO(log n)です。 - ノードの挿入
挿入自体はO(1)の計算量で行われます。 - 挿入後のバランス調整
挿入後、ツリーが不均衡になった場合、回転操作を行ってバランスを取ります。回転操作は1回の回転に対してO(1)の時間で実行され、最大でも2回の回転が必要です。バランスファクターの再計算は各ノードで1回行われるため、全体のバランス調整にかかる時間もO(log n)です。
したがって、挿入操作全体の計算量は、O(log n) です。
検索操作の計算量
検索操作は、通常の二分探索木と同じように、ルートノードから検索対象のノードを再帰的に探索します。AVLツリーは常に平衡状態を保つため、ツリーの高さはO(log n)に抑えられています。これにより、検索操作の計算量はO(log n) となり、大規模なデータに対しても効率的な検索が可能です。
他のデータ構造との比較
AVLツリーの挿入と検索の計算量を、他の一般的なデータ構造と比較してみましょう。
| データ構造 | 挿入の計算量 | 検索の計算量 |
|---|---|---|
| AVLツリー | O(log n) | O(log n) |
| 二分探索木（BST） | O(n)（最悪） | O(n)（最悪） |
| ヒープ | O(log n) | O(n) |
| ハッシュテーブル | O(1)（平均） | O(1)（平均） |
- 二分探索木（BST）
二分探索木では、データの挿入順序によりツリーが片側に偏ることがあり、その結果、最悪の場合O(n)の計算量になることがあります。一方、AVLツリーでは常に平衡状態が保たれるため、この問題が回避されます。 - ヒープ
ヒープは挿入にO(log n)の計算量がかかりますが、検索にはO(n)の時間がかかるため、頻繁に検索が必要な場合にはAVLツリーの方が有利です。 - ハッシュテーブル
ハッシュテーブルは、平均してO(1)の計算量で挿入や検索が行えますが、衝突が発生する場合にはそのパフォーマンスが低下する可能性があります。また、ハッシュテーブルは要素間の順序が保持されないため、順序付きのデータ操作が必要な場合にはAVLツリーが適しています。
AVLツリーの計算量のメリット
AVLツリーは、挿入や検索の際に常にO(log n)の計算量を保証します。これにより、大規模データの管理や高速な検索が必要なシステムで特に有用です。二分探索木に比べて若干のメモリオーバーヘッドがありますが、その分、パフォーマンスの安定性が得られるため、パフォーマンスが重要なアプリケーションで頻繁に使用されます。
応用例：AVLツリーの実際の使用場面
AVLツリーは、効率的にデータを検索、挿入、削除する機能を持つため、さまざまな分野で実用的なデータ構造として活用されています。特に、大規模なデータを効率的に管理する必要があるシステムや、常にデータのバランスを保つ必要があるアプリケーションにおいて、その強力なアルゴリズムが重宝されています。ここでは、AVLツリーが実際にどのような場面で使用されるか、いくつかの具体例を紹介します。
1. データベースのインデックス構造
データベースシステムでは、膨大なデータから効率よくレコードを検索するためにインデックスが使用されます。AVLツリーは、その安定したO(log n)の検索時間が保証されるため、B木やB+木と並んでインデックス構造として利用されることがあります。特に、動的にデータが追加され、かつ検索が頻繁に行われる場合に有効です。データが均等に分散されることで、インデックスの更新や検索が高速に行われます。
2. コンパイラのシンボルテーブル管理
コンパイラは、プログラムのソースコードを解析してシンボルテーブルを作成し、変数や関数の名前を対応するメモリアドレスと関連付けます。AVLツリーを使用することで、シンボルテーブル内の検索や挿入が高速に行われ、プログラムのコンパイル時間が短縮されます。特に、大規模なプログラムでは、シンボルが大量に存在するため、AVLツリーの平衡機能が効果的に働きます。
3. ルーティングテーブルの管理
ネットワークルーティングプロトコルにおいて、ルーターはデータパケットの送信先を決定するためにルーティングテーブルを管理します。このルーティングテーブルでは、送信先IPアドレスを検索して最適なルートを見つける必要があります。AVLツリーを使用することで、ルーティングテーブルの検索効率を向上させ、ネットワーク全体の通信速度を最適化することができます。
4. ゲーム開発におけるオブジェクト管理
ゲーム開発では、ゲーム内のキャラクターやオブジェクトの状態を効率的に管理する必要があります。AVLツリーを使用すると、ゲーム内のオブジェクトの位置情報や状態を常に効率よく検索、更新することが可能です。例えば、大規模なMMORPGでは、数千ものプレイヤーやオブジェクトをリアルタイムで管理するため、AVLツリーによって負荷を分散し、サーバーのパフォーマンスを向上させることができます。
5. メモリ管理システム
メモリ管理システムでは、空きメモリ領域を効率的に追跡し、適切なサイズのメモリを割り当てる必要があります。AVLツリーは、空き領域を管理するためのデータ構造として使用されることがあります。メモリの断片化を防ぎつつ、メモリの割り当てや解放の操作を高速に行うためにAVLツリーの平衡性が活かされます。
6. 辞書型データの管理
AVLツリーは、辞書型データの管理にも適しています。辞書型データは、キーと値のペアで構成され、キーに基づいて値を検索します。AVLツリーを使用することで、辞書型データの挿入、削除、検索が効率よく行えます。大規模な辞書データを管理する自然言語処理システムや検索エンジンなどで使用されています。
7. 時系列データの管理
金融システムやIoTアプリケーションでは、時間に基づくデータを効率的に管理する必要があります。AVLツリーは、時系列データの挿入や検索に使用され、リアルタイムでデータを追跡することができます。データのバランスが崩れにくいため、時系列データが偏らず、効率的に操作できる点が大きなメリットです。
応用例のまとめ
AVLツリーは、データのバランスを保ちながら高速な挿入、検索、削除を実現するため、様々なシステムで応用されています。特に、データ量が大きくなり、動的な更新が頻繁に行われるシステムにおいて、その効果が顕著です。高いパフォーマンスを要求されるプロジェクトでは、AVLツリーの導入が非常に有効です。
演習問題：AVLツリーの実装と挿入
これまでの内容を理解し、実際に自分でAVLツリーを実装してみることで、知識を深めましょう。以下の演習問題に取り組むことで、AVLツリーの動作とそのアルゴリズムの詳細を確認できます。コードを実行し、正しく動作するかどうかを確認してみてください。
演習問題 1: AVLツリーの基本実装
まず、以下の要件に基づいて、AVLツリーの基本的な挿入操作と回転操作を実装してください。
- 要件:
- ノードを表すクラス
Nodeを作成し、キー、左右の子ノード、ノードの高さを保持する。 - AVLツリーのバランスを保つために、必要に応じて右回転、左回転、左右回転、右左回転を実装する。
- 新しいキーを挿入し、ツリーが正しくバランスを保つように回転操作を適用する。
コードテンプレート:
class Node {
int key, height;
Node left, right;
Node(int d) {
key = d;
height = 1;
}
}
class AVLTree {
Node root;
// ノードの高さを取得
int height(Node N) {
return (N == null) ? 0 : N.height;
}
// バランスファクターを計算
int getBalance(Node N) {
return (N == null) ? 0 : height(N.left) - height(N.right);
}
// 右回転
Node rightRotate(Node y) {
Node x = y.left;
Node T2 = x.right;
x.right = y;
y.left = T2;
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
return x;
}
// 左回転
Node leftRotate(Node x) {
Node y = x.right;
Node T2 = y.left;
y.left = x;
x.right = T2;
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
return y;
}
// ノードの挿入操作
Node insert(Node node, int key) {
// 通常の二分探索木の挿入操作
if (node == null)
return new Node(key);
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
else
return node;
// ノードの高さを更新
node.height = Math.max(height(node.left), height(node.right)) + 1;
// バランスファクターを計算
int balance = getBalance(node);
// 回転操作の適用
if (balance > 1 && key < node.left.key)
return rightRotate(node);
if (balance < -1 && key > node.right.key)
return leftRotate(node);
if (balance > 1 && key > node.left.key) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
if (balance < -1 && key < node.right.key) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
// ツリーをInorderで表示
void inorder(Node node) {
if (node != null) {
inorder(node.left);
System.out.print(node.key + " ");
inorder(node.right);
}
}
// メインメソッドでツリーをテスト
public static void main(String[] args) {
AVLTree tree = new AVLTree();
tree.root = tree.insert(tree.root, 10);
tree.root = tree.insert(tree.root, 20);
tree.root = tree.insert(tree.root, 30);
tree.root = tree.insert(tree.root, 40);
tree.root = tree.insert(tree.root, 50);
tree.root = tree.insert(tree.root, 25);
System.out.println("Inorder traversal of constructed AVL tree is : ");
tree.inorder(tree.root);
}
}演習問題 2: 挿入後のツリーのバランスを確認する
上記のコードを実行し、キーを挿入した後にツリーが正しくバランスを保っているかどうかを確認してください。
- 挿入キーの順序: 10, 20, 30, 40, 50, 25
- 出力結果: 挿入後にツリーがバランスされているかを確認するため、Inorder traversalの結果が次のように表示されるか確認してください。
10 20 25 30 40 50この演習では、AVLツリーが正しく実装され、挿入後もツリーが自己平衡を保っていることを確認します。
まとめ
本記事では、AVLツリーの基本概念から、検索と挿入のアルゴリズム、Javaでの実装、さらに応用例や演習問題を通じて、その利点を理解しました。AVLツリーは、常に平衡を保つことにより、効率的な検索、挿入、削除操作を実現する強力なデータ構造です。特に、大規模データや動的に更新が頻繁なシステムでのパフォーマンス向上に有効です。
コメント