두 갈래 찾기 트 리 자바 구현

이 진 트 리 는 이 진 트 리 입 니 다. 특히 트 리 의 모든 노드 X 에 대해 왼쪽 트 리 의 모든 항목 의 값 은 X 의 항목 보다 작고 오른쪽 트 리 의 모든 항목 의 값 은 X 의 항목 보다 큽 니 다.
삽입 시퀀스 가 무 작위 라면 평균 깊이 는 O (logN) 입 니 다.
삽입 시퀀스 가 미리 정렬 되 어 있 으 면 링크 로 퇴화 됩 니 다.
AVL 트 리, 레 드 블랙 트 리 (red black tree) 와 같은 추가 균형 조건 이 있 는 솔 루 션 입 니 다.
다른 하 나 는 스 트 레 칭 트 리 (splay tree) 와 같은 규칙 을 사용 하여 균형 을 맞 추 는 것 이다.

/**
 *      
 * 
 *         O(logN)
 * 
 *     ： 
 * void insert(T x); 
 * void remove(T x); 
 * T findMin();
 * T findMax();
 * boolean contains(T x); 
 * void makeEmpty();
 * boolean isEmpty();
 * void printTree();
 */
public class BinarySearchTree<T extends Comparable<? super T>> {

	private BinaryNode<T> root; //             

	//    
	private static class BinaryNode<T> {

		private T element;
		private BinaryNode<T> left;
		private BinaryNode<T> right;

		BinaryNode(T theElement, BinaryNode<T> lt, BinaryNode<T> rt) {
			element = theElement;
			left = lt;
			right = rt;
		}
	}

	//    
	public BinarySearchTree() {
		root = null;
	}

	//   ，   general       
	public void insert(T x) {
		root = insert(x, root);
	}

	//   ，   general remove  
	public void remove(T x) {
		root = remove(x, root);
	}

	//    ，    null
	public T findMin() {
		if (isEmpty())
			return null;
		return findMin(root).element;
	}

	//    ，    null
	public T findMax() {
		if (isEmpty())
			return null;
		return findMax(root).element;
	}

	// contains
	public boolean contains(T x) {
		return contains(x, root);
	}

	//
	public void makeEmpty() {
		root = null;
	}

	//
	public boolean isEmpty() {
		return root == null;
	}

	//
	public void printTree() {
		if (isEmpty()) {
			System.out.println("Empty tree");
			return;
		} else
			printTree(root);
	}

	private BinaryNode<T> insert(T x, BinaryNode<T> t) {
		//      
		if (t == null)
			return new BinaryNode<>(x, null, null);

		int compareResult = x.compareTo(t.element);
		//          ，    ，   
		if (compareResult < 0)
			t.left = insert(x, t.left);
		else if (compareResult > 0)
			t.right = insert(x, t.right);

		return t;
	}
	
	private BinaryNode<T> remove(T x, BinaryNode<T> t) {
		if (t == null)
			return t; // Item not found; do nothing

		int compareResult = x.compareTo(t.element);

		if (compareResult < 0)
			t.left = remove(x, t.left);
		else if (compareResult > 0)
			t.right = remove(x, t.right);
		//      ，                ，         
		//        ，        ，
		//                        ，            
		else if (t.left != null && t.right != null) {
			//          ，        
			t.element = findMin(t.right).element;
			//          
			t.right = remove(t.element, t.right);
		} else
			t = (t.left != null) ? t.left : t.right;
		return t;
	}

	//       ，     ，         
	private BinaryNode<T> findMin(BinaryNode<T> t) {
		if (t == null)
			return null;
		else if (t.left == null)
			return t;
		return findMin(t.left);
	}

	//       ，     ，   while      
	private BinaryNode<T> findMax(BinaryNode<T> t) {
		if (t != null)
			while (t.right != null)
				t = t.right;
		return t;
	}

	private boolean contains(T x, BinaryNode<T> t) {

		if (t == null)
			return false;

		int compareResult = x.compareTo(t.element);
		//           while    
		if (compareResult < 0)
			return contains(x, t.left);
		else if (compareResult > 0)
			return contains(x, t.right);
		else
			return true; // Match
	}

	//     print，         
	private void printTree(BinaryNode<T> t) {
		if (t != null) {
			printTree(t.left);
			System.out.println(t.element);
			printTree(t.right);
		}
	}

	//      ，      
	private int height(BinaryNode<T> t) {
		if (t == null)
			return -1;
		else
			return 1 + Math.max(height(t.left), height(t.right));
	}

	//   
	public static void main(String[] args) {

		BinarySearchTree<Integer> t = new BinarySearchTree<>();

		for (int i = 0; i <= 100; i++) {
			t.insert(i);
		}

		t.printTree();
		System.out.println(t.findMax());
		System.out.println(t.findMin());
		System.out.println(t.contains(101));

	}

}