コンピュータ

COMPUTER

公開：2024-05-19

2分探索木とは？意味をわかりやすく簡単に解説

text: XEXEQ編集部

2分探索木とは

2分探索木はデータ構造の一種であり、効率的な要素の検索やソートに用いられるツリー構造です。各ノードが最大で2つの子ノードを持ち、左の子ノードの値は親ノードの値より小さく、右の子ノードの値は親ノードの値より大きくなるように構成されています。

2分探索木の特徴として、平衡が保たれている場合、要素の検索、挿入、削除の平均計算量がO(log n)となり、非常に高速に処理できます。一方、偏ったツリーになってしまうと、最悪の場合O(n)の計算量になってしまうため、適切なバランシングが重要となります。

2分探索木を用いることで、大量のデータの中から目的の要素を高速に見つけ出すことができます。また、要素を昇順や降順に並べ替えるソートにも活用できるため、データ処理の様々な場面で重宝されています。

2分探索木の操作には探索、挿入、削除などがあります。探索ではツリーのルートノードから始まり、目的の値と比較しながら子ノードを辿っていきます。挿入では新しいノードを適切な位置に追加し、削除では対象のノードを取り除き、ツリーの構造を調整します。

2分探索木を実装する際は各ノードがキーと値のペアを持ち、左右の子ノードへのポインタを保持する必要があります。再帰的なアルゴリズムを用いることで、シンプルかつ効率的に操作を行うことができます。

2分探索木の基本操作

2分探索木の基本操作に関して、以下3つを簡単に解説していきます。

• 2分探索木での要素の探索
• 2分探索木へのノードの挿入
• 2分探索木からのノードの削除

2分探索木での要素の探索

2分探索木で目的の要素を探索する際はルートノードから始めます。探索したい値とルートノードの値を比較し、小さければ左の子ノードへ、大きければ右の子ノードへと移動します。この比較と移動を、目的の値が見つかるか、nullに到達するまで繰り返します。

探索の計算量はツリーの高さに比例します。平衡が取れた2分探索木の場合、高さはおよそlog nとなるため、探索の平均計算量はO(log n)になります。一方、偏ったツリーの場合、最悪でO(n)の計算量になることがあります。

2分探索木の探索は二分探索と同様の原理で動作するため、大量のデータの中から目的の要素を高速に見つけ出すことができます。この特性を活かし、様々なアプリケーションで利用されています。

2分探索木へのノードの挿入

2分探索木に新しいノードを挿入する際はまず探索と同様に、挿入する値とノードの値を比較しながら適切な位置を探します。nullに到達したら、その位置に新しいノードを作成し、親ノードとの関係を設定します。

挿入の計算量も、探索と同様にツリーの高さに比例します。平衡が取れている場合はO(log n)の計算量で挿入できます。しかし、挿入によってツリーが偏ってしまう可能性があるため、必要に応じてバランシングを行う必要があります。

2分探索木へのノードの挿入はデータの追加や更新に使用されます。適切に実装することで、効率的にデータを管理することができます。ただし、偏ったツリーにならないよう注意が必要です。

2分探索木からのノードの削除

2分探索木からノードを削除する際は削除対象のノードの子ノードの数に応じて、異なる処理を行います。子ノードがない場合は単純にノードを削除します。子ノードが1つの場合は子ノードを削除対象ノードの位置に移動させます。

削除対象ノードに2つの子ノードがある場合は右部分木の最小値を持つノードを探し、削除対象ノードと置き換えます。その後、置き換えたノードを削除します。この一連の操作により、2分探索木の性質を維持しつつ、ノードを削除することができます。

ノードの削除も、平均的にはO(log n)の計算量で行えますが、偏ったツリーの場合はO(n)になることがあります。削除後のツリーが偏らないよう、必要に応じてバランシングを行うことが重要です。

2分探索木のバランシング

2分探索木のバランシングに関して、以下3つを簡単に解説していきます。

• 2分探索木の偏りとパフォーマンスの関係
• AVL木によるバランシング
• 赤黒木によるバランシング

2分探索木の偏りとパフォーマンスの関係

2分探索木が偏ってしまうと、探索、挿入、削除の計算量が最悪でO(n)になってしまい、パフォーマンスが著しく低下します。偏りが大きくなるほど、ツリーの高さが増加し、各操作に必要な比較の回数が増えるためです。

偏りを防ぐにはツリーのバランスを保つ必要があります。バランスの取れた2分探索木ではツリーの高さがおよそlog nになるため、各操作の平均計算量をO(log n)に抑えることができます。バランシングには様々な手法が存在します。

AVL木によるバランシング

AVL木は2分探索木の一種で、厳密なバランスを保つことで高いパフォーマンスを実現します。AVL木では各ノードの左右の部分木の高さの差が1以下になるよう制約を設けています。

挿入や削除の際に、この制約が満たされなくなった場合、回転操作を行ってツリーのバランスを修正します。回転には単回転と双回転の2種類があり、ツリーの形状に応じて適切に選択します。

AVL木を用いることで、常にバランスの取れた2分探索木を維持できるため、各操作の最悪計算量をO(log n)に抑えることができます。ただし、厳密なバランスを保つために、挿入や削除の際にオーバーヘッドが発生します。

赤黒木によるバランシング

赤黒木は2分探索木のバランスを保つもう一つの手法です。各ノードに「赤」または「黒」の色を割り当て、一定の規則に従ってツリーを構成します。赤黒木ではルートノードから任意の葉ノードまでの経路に含まれる黒ノードの数が等しくなるよう制約を設けています。

挿入や削除の際に、この制約が満たされなくなった場合、ノードの色を変更したり、回転操作を行ったりしてバランスを修正します。AVL木と比べると、赤黒木はやや緩やかなバランスを保つため、挿入や削除のオーバーヘッドが小さくなる傾向があります。

赤黒木を用いることで、2分探索木のバランスを維持しつつ、効率的な操作が可能になります。各操作の平均計算量はAVL木と同様にO(log n)です。赤黒木はC++のSTLやJavaのTreeMapなど、多くのライブラリで使用されています。

2分探索木の応用例

2分探索木の応用例に関して、以下3つを簡単に解説していきます。

• 2分探索木を用いたソート
• 2分探索木を用いた集合の実装
• 2分探索木を用いた関連付け配列の実装

2分探索木を用いたソート

2分探索木を用いることで、要素を昇順や降順に並べ替えるソートを効率的に行うことができます。まず、与えられた要素を2分探索木に挿入します。その後、2分探索木を中順走査(In-order traversal)することで、昇順に並んだ要素を得ることができます。

この手法はツリーソートと呼ばれます。ツリーソートの計算量は要素の挿入にかかる時間とツリーの走査にかかる時間の合計になります。バランスの取れた2分探索木を用いた場合、ソートの平均計算量はO(n log n)になります。

2分探索木を用いた集合の実装

2分探索木を用いることで、集合(Set)を効率的に実装できます。集合は重複のない要素の集まりで、要素の追加、削除、検索などの操作をサポートします。2分探索木では各ノードのキーを要素とみなすことで、集合を表現できます。

要素の追加や削除は2分探索木のノードの挿入や削除と同様に行います。要素の検索は2分探索木の探索操作を用いて行います。これらの操作の平均計算量はいずれもO(log n)になります。

C++のSTLやJavaのTreeSetなど、多くのライブラリでは2分探索木を用いて集合が実装されています。2分探索木を用いることで、集合操作を効率的に行うことができます。

2分探索木を用いた関連付け配列の実装

2分探索木を用いることで、関連付け配列(Associative array)や辞書(Dictionary)を効率的に実装できます。関連付け配列はキーと値のペアを格納し、キーを用いて値を高速に検索することができるデータ構造です。

2分探索木では各ノードがキーと値のペアを保持します。キーを用いて2分探索木を探索することで、対応する値を効率的に取得できます。挿入、削除、検索の平均計算量はいずれもO(log n)になります。

C++のSTLではmapやmultimap、JavaではTreeMapなど、2分探索木を用いた関連付け配列の実装が提供されています。これらのライブラリを使用することで、キーと値のマッピングを効率的に管理することができます。

※上記コンテンツはAIで確認しておりますが、間違い等ある場合はコメントよりご連絡いただけますと幸いです。

「コンピュータ」に関するコラム一覧「コンピュータ」に関するニュース一覧