二分探索木ノードの検索
二分探索木にはインデックスがないため、二分探索木の検索操作として、ここで 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 );
}
...
// 再帰アルゴリズムを使用して、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 より小さいため、左の子ノードで比較を続ける必要があります。


(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 );
}
...
// 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 );
}
}
/**
* 二分探索木の検索
*/
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 );
}
}