二分探索木ノードの検索

二分探索木にはインデックスがないため、二分探索木の検索操作として、ここで contain メソッドを定義し、二分探索木が特定の要素を含むかどうかを判定して、ブール型変数を返します。この検索操作も再帰的なプロセスであり、具体的なコード実装は以下の通りです。

...
// 再帰アルゴリズムを使用して、node を根とする二分探索木にキー値が key のノードが含まれているかを確認する
private boolean contain(Node node, Key key){

    if( node == null )
        return false;

    if( key.compareTo(node.key) == 0 )
        return true;
    else if( key.compareTo(node.key) < 0 )
        return contain( node.left , key );
    else // key > node->key
        return contain( node.right , key );
}
...

以下の例では、二分探索木の中で要素 43 を探します。

(1)要素 43 はルートノード 42 より大きいため、右の子ノードで比較を続ける必要があります。

(2)要素 43 は 59 より小さいため、左の子ノードで比較を続ける必要があります。

(3)要素 43 は 51 より小さいため、左の子ノードで比較を続ける必要があります。

(4)51 の左の子ノード 43 を探し、ちょうど等しいので終了します。

key に対応する value を検索する必要がある場合、コードは次のようになります。

...
// node を根とする二分探索木で key に対応する value を検索する再帰アルゴリズム
// value が存在しない場合は NULL を返す
private Value search(Node node, Key key){

    if( node == null )
        return null;

    if( key.compareTo(node.key) == 0 )
        return node.value;
    else if( key.compareTo(node.key) < 0 )
        return search( node.left , key );
    else // key > node->key
        return search( node.right, key );
}
...

Java サンプルコード

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

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

package サンプル.binary;

/**
* 二分探索木の検索
 */

public class BinarySearchTreeSearch<Key extends Comparable<Key>, Value> {
    // ツリー内のノードはプライベートなクラスであり、外部は二分探索木ノードの具体的な実装を理解する必要はありません
    private class Node {
        private Key key;
        private Value value;
        private Node left, right;

        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
            left = right = null;
        }
    }
    // ルートノード
    private Node root;
    // ツリー内のノード数
    private int count;

    // コンストラクタ、デフォルトで空の二分探索木を構築します
    public BinarySearchTreeSearch() {
        root = null;
        count = 0;
    }

    // 二分探索木のノード数を返す
    public int size() {
        return count;
    }

    // 二分探索木が空かどうかを返す
    public boolean isEmpty() {
        return count == 0;
    }

    // 二分探索木に新しい (key, value) データペアを挿入する
    public void insert(Key key, Value value){
        root = insert(root, key, value);
    }

    // 二分探索木にキー key が存在するかどうかを確認する
    public boolean contain(Key key){
        return contain(root, key);
    }

    // 二分探索木でキー key に対応する値を検索します。この値が存在しない場合は null を返します
    public Value search(Key key){
        return search( root , key );
    }


    //********************
    //* 二分探索木の補助関数
    //********************

    // 再帰アルゴリズムを使用して、node を根とする二分探索木にノード (key, value) を挿入する
    // 新しいノードを挿入した後の二分探索木の根を返す
    private Node insert(Node node, Key key, Value value){

        if( node == null ){
            count ++;
            return new Node(key, value);
        }

        if( key.compareTo(node.key) == 0 )
            node.value = value;
        else if( key.compareTo(node.key) < 0 )
            node.left = insert( node.left , key, value);
        else    // key > node->key
            node.right = insert( node.right, key, value);

        return node;
    }

    // 再帰アルゴリズムを使用して、node を根とする二分探索木にキー値が key のノードが含まれているかを確認する
    private boolean contain(Node node, Key key){

        if( node == null )
            return false;

        if( key.compareTo(node.key) == 0 )
            return true;
        else if( key.compareTo(node.key) < 0 )
            return contain( node.left , key );
        else // key > node->key
            return contain( node.right , key );
    }

    // node を根とする二分探索木で key に対応する value を検索する再帰アルゴリズム
    // value が存在しない場合は NULL を返す
    private Value search(Node node, Key key){

        if( node == null )
            return null;

        if( key.compareTo(node.key) == 0 )
            return node.value;
        else if( key.compareTo(node.key) < 0 )
            return search( node.left , key );
        else // key > node->key
            return search( node.right, key );
    }
}
その他の拡張