二分探索木（java版)

コードにバグが存在していました。
後日、修正したプログラムで再測定を行います。
申し訳ございませんでした。

以下の記述は多くが誤りとなりますので、ご理解のうえご覧ください。
まことに勝手ながら、諸事情により二分木についての解説を11/29に変更させていただきます。
以下、二分探索木のコードと挿入時間の計測結果。

public class BinarySearchTree {
	Node root;
	public BinarySearchTree(Node root) {
		this.root = root;
	}
	
	public Node search(Node root, Node key){
		if(root != null){
			int gap = root.compareTo(key);
			if(gap == 0)	return root;
			else if(gap > 0)return search(root.left, key);
			else if(gap < 0)return search(root.right, key);
			else return null;
		}else{
			return null;
		}
	}
	
	public Node insert(Node root, Node key) throws Exception{
		if(this.root == null){
			this.root = key;
			return key;
		}
		if(root != null){
			int gap = root.compareTo(key);
			if(gap == 0){
				throw new Exception();//ノードがすでに存在する場合は例外を投げる
			}else if(gap > 0){
				root.left = insert(root.left, key);
			}else if(gap < 0){
				root.right = insert(root.right, key);
			}
			return root;
		}else{
			return key;
		}	
	}
	
	public void clear(Node target){
		if(target != null){
			clear(target.left);
			clear(target.right);
			target.left = null;
			target.right = null;
			target = null;
		}
	}

	public void printTree(Node target){
		if(target != null){
			printTree(target.left);
			System.out.println(target.toString());
			printTree(target.right);
		}
	}
}

class Node implements Comparable<Node>{
	int data;
	Node left;
	Node right;
	public Node(int data) {
		this.data = data;
		this.left = null;
		this.right = null;
	}
	@Override
	public String toString(){
		StringBuffer buf = new StringBuffer();
		buf.append("data:" + data);
		return buf.toString();
	}
	@Override
	public int compareTo(Node o) {
		return this.data - o.data;
	}
}

もろもろで1時間40分ほどかかりました。テストは行っていません。
予定が遅れていますが、赤黒木の実装とAVL木・B木との比較までやります。

赤黒木との比較を視野に処理時間を以下のコードで計測しました。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BSTTest {
	static final int NUM = 10000;
	static final int TRY = 10000;
	
	
	public static void main(String[] args) throws Exception {
		test();
	}

	private static void test() throws Exception {
		BinarySearchTree tree;
		long[] result = new long[TRY];
		Node[] array = new Node[NUM];
		List<Integer> list = new ArrayList<Integer>();
		for(int i = 0; i < NUM; i++){
			list.add(i);
		}
		for (int tryTime = 0; tryTime < TRY; tryTime++) {
			Collections.shuffle(list);
			tree  = new BinarySearchTree(null);
			//ノード配列生成
			for (int i = 0; i < NUM; i++) {
				array[i] = new Node((Integer)list.get(i));
			}
			//挿入時間測定
			long startTime = System.currentTimeMillis();
			for (Node n : array) {
				tree.insert(tree.root, n);
			}
			long finishTime = System.currentTimeMillis();
			//結果を保存
			result[tryTime] = (finishTime - startTime);
		}
		//平均を算出して出力
		long avgTime = 0;
		for(long time : result){
			avgTime += time;
		}
		System.out.println("time:" + (double)avgTime / (double)TRY);
	}
}

ソート済み自然数とランダムな自然数集合の二分探索木への挿入を2万回行い平均の処理時間を求めました。
ソート済み自然数のリストへの追加は30万回行い平均の処理時間を求めました。

今回作成した二分探索木では二分探索木の特性が生かされないため、ソート済み集合の挿入がひどい結果になっています。
また、ランダムな場合も平衡にする処理を行っていないため、ソート済みの場合と同じく線形的、計算量はO(n)です。
赤黒木では平衡処理により、最短の枝と最長の枝の差がたかだか2倍となるため、計算量がO(log n)に改善されると予想されます。
要素の挿入については、行うべき処理が少ないリストが高速であるとわかります。