【Java】２分探索木

この記事は、「新・明解Javaで学ぶアルゴリズムとデータ構造」を読んで学んだことを、個人的な備忘録目的でまとめています。

ただし、本を参考にして自分なりに構成やコードを変更しているためご注意ください。
アルゴリズムの詳細や解説は是非参考書をお手に取って読まれてください。

【リンク紹介】
・Javaで学ぶアルゴリズムとデータ構造
・これまで書いたシリーズ記事一覧

２分探索木

package chap09;

import java.util.Comparator;

// ２分木探索木
public class BinTree<K, V> {
	
	//--- ノード ---//
	static class Node<K, V> {
		private K          key;      // キー値
		private V          data;     // データ
		private Node<K, V> left;     // 左ポインタ（左子ノードへの参照）
		private Node<K, V> right;    // 右ポインタ（右子ノードへの参照）
		
		//--- コンストラクタ ---//
		Node(K key, V data, Node<K, V> left, Node<K, V> right) {
			this.key   = key;
			this.data  = data;
			this.left  = left;
			this.right = right;
		}
		
		//--- キー値を返す ---//
		K getKey() {
			return key;
		}
		
		//--- データを返す ---//
		V getValue() {
			return data;
		}
		
		//--- データの表示 ---//
		void print() {
			System.out.println(data);
		}
	}
	
	private Node<K, V> root;                          // 根
	private Comparator<? super K> comparator = null;  // コンパレータ
	
	//--- コンストラクタ ---//
	public BinTree() {
		root = null;
	}
	
	//--- コンストラクタ ---//
	public BinTree(Comparator<? super K> c) {
		this();
		comparator = c;
	}
	
	//--- 二つのキー値を比較 ---//
	private int comp(K key1, K key2) {
		return (comparator == null) ? ((Comparable<K>) key1).compareTo(key2)
				                    : comparator.compare(key1, key2);
	}
	
	//--- キーによる探索 ---//
	public V search(K key) {
		Node<K, V> p = root;              // 根に着目
		
		while (true) {
			if (p == null) {
				return null;
			}
			
			int cond = comp(key, p.getKey());
			
			if (cond == 0) {
				return p.getValue();
			} else if (cond < 0) {
				p = p.left;
			} else {
				p = p.right;
			}
		}
	}
}

学習内容まとめ

eclipse操作時に役立つショートカットまとめ
https://qiita.com/toshi0383/items/1d2a990392998789062c

$\bf{\textcolor{red}{記事が役に立った方は「いいね」を押していただけると、すごく喜びます \ 笑}}$
ご協力のほどよろしくお願いします。