二分探索木

一、概念とその紹介

二分探索木(英語:Binary Search Tree)は、二叉探索木、二分検索木、順序付き二分木、またはソート済み二分木とも呼ばれます。以下のいくつかの条件を満たします:

  • 左の部分木が空でない場合、左の部分木のすべてのノードの値はそのルートノードより小さくなります。
  • 右の部分木が空でない場合、右の部分木のすべてのノードの値はそのルートノードより大きくなります。

その左および右の部分木もまた二分探索木です。

下図に示すとおりです:

二、適用説明

二分探索木は効率的な挿入、削除、検索操作を備えています。

平均時間の時間計算量はO(log n)、最悪の場合はO(n)。二分探索木はヒープと異なり、必ずしも完全二分木ではなく、基盤となる構造を配列で直接表現しにくいため、連結リストを用いて二分探索木を実装します。

 要素の検索要素の挿入要素の削除
通常の配列O(n)O(n)O(n)
順序配列O(logn)O(n)O(n)
二分探索木O(logn)O(logn)O(logn)

以下では、まず配列形式の二分探索法を考え方の参考として紹介し、その後で二分探索木の探索方法について紹介します。

三、二分探索法のプロセス図解

二分探索法の考え方は1946年に提唱されました。探索問題はコンピュータにおいて非常に重要な基礎的問題です。順序付けられた数列に対してのみ、二分探索法を使用できます。ある要素を探索する場合、まず配列の中央の値Vと探索対象データとの大小関係を確認し、次の3つのケースに分けます:

  • 1、探索対象のデータと等しい場合、直接見つかる
  • 2、Vより小さい場合、Vより小さい部分に分けて検索を続けます
  • 2、Vより大きい場合、Vより大きい部分に分けて検索を続けます

四、Javaサンプルコード

ソースコードパッケージのダウンロード:Download

src/サンプル/binary/BinarySearch.java ファイルのコード:

package サンプル.binarySearch;

/**
* 二分探索法
 */

public class BinarySearch {
    // 二分探索法、ソート済み配列arr内でtargetを探索する
    // targetが見つかった場合、対応するインデックスindexを返す
    // targetが見つからない場合、-1を返す
    public static int find(Comparable[] arr, Comparable target) {

        // arr[l...r]の範囲内でtargetを探索する
        int l = 0, r = arr.length-1;
        while( l <= r ){

            //int mid = (l + r)/2;
            // 極端な場合の整数オーバーフローを防ぐため、以下のロジックを使用してmidを求める
            int mid = l + (r-l)/2;

            if( arr[mid].compareTo(target) == 0 )
                return mid;

            if( arr[mid].compareTo(target) > 0 )
                r = mid - 1;
            else
                l = mid + 1;
        }

        return -1;
    }
}
その他の拡張