BinarySearchTree

BinarySearchTree.java

public class BinarySearchTree {
	public static Node root;

	public BinarySearchTree() {
		this.root = null;
	}

	/**
	 * tree 에서 key 로 node 를 탐색합니다.
	 * @param id
	 * @return
	 */
	public boolean find(int id) {
		Node current = root;
		while (current != null) {
			if (current.data == id) {
				return true;
			} else if (current.data > id) {
				current = current.left;
			} else {
				current = current.right;
			}
		}
		return false;
	}

	/**
	 * tree 에서 key 를 찾아서 node 를 삭제합니다.
	 * @param id
	 * @return
	 */
	public boolean delete(int id) {
		Node parent = root;
		Node current = root;
		boolean isLeftChild = false;
		while (current.data != id) {
			parent = current;
			if (current.data > id) {
				isLeftChild = true;
				current = current.left;
			} else {
				isLeftChild = false;
				current = current.right;
			}
			if (current == null) {
				return false;
			}
		}
		// if i am here that means we have found the node
		// Case 1: if node to be deleted has no children
		if (current.left == null && current.right == null) {
			if (current == root) {
				root = null;
			}
			if (isLeftChild == true) {
				parent.left = null;
			} else {
				parent.right = null;
			}
		}
		// Case 2 : if node to be deleted has only one child
		else if (current.right == null) {
			if (current == root) {
				root = current.left;
			} else if (isLeftChild) {
				parent.left = current.left;
			} else {
				parent.right = current.left;
			}
		} else if (current.left == null) {
			if (current == root) {
				root = current.right;
			} else if (isLeftChild) {
				parent.left = current.right;
			} else {
				parent.right = current.right;
			}
		} else if (current.left != null && current.right != null) {

			// now we have found the minimum element in the right sub tree
			Node successor = getSuccessor(current);
			if (current == root) {
				root = successor;
			} else if (isLeftChild) {
				parent.left = successor;
			} else {
				parent.right = successor;
			}
			successor.left = current.left;
		}
		return true;
	}

	/**
	 * node 를 삭제할때 좌측 우측 sub 가 있는 경우 parameter node 의 right sub tree 에서 가장 최소 key 를 가진 node 를 반환합니다. 
	 * @param deleleNode
	 * @return 
	 */
	public Node getSuccessor(Node deleleNode) {
		Node successsor = null; // current 의 부모 node 를 pointer 로 사용
		Node successsorParent = null; // current 의 조부모 node 를 pointer 로 사용
		Node current = deleleNode.right; // 삭제 할노드의 우측 자식 노드 주소를 current pointer 에 저장
		while (current != null) { // current 값이 없을때까지 반복
			successsorParent = successsor; // current 의 조부모
			successsor = current; // current 의 부모
			current = current.left; // 좌측의 node 주소를 계속 찾음.
		}
		// check if successor has the right child, it cannot have left child for sure
		// if it does have the right child, add it to the left of successorParent.
		// successsorParent
		if (successsor != deleleNode.right) { // successsor 가  삭제 노드의 우측 자식 노드 가 아닐경우 
			successsorParent.left = successsor.right; // successsor의 우측 자식 노드를 sucessor 의 자리를 대체한다.  
			successsor.right = deleleNode.right; // successsor 의 우측 자식 노드 pointer 는 삭제될 node 의 우측 자식노드의 주소를 가르킨다.  
		}
		return successsor;
	}

	/**
	 * 이진 탐색 트리에 key 삽입합니다.
	 * @param id
	 */
	public void insert(int id) {
		Node newNode = new Node(id);
		if (root == null) {
			root = newNode;
			return;
		}
		Node current = root;
		Node parent = null;
		while (true) {
			parent = current;
			if (id < current.data) {
				current = current.left;
				if (current == null) {
					parent.left = newNode;
					return;
				}
			} else {
				current = current.right;
				if (current == null) {
					parent.right = newNode;
					return;
				}
			}
		}
	}

	/**
	 * parameter 로 전달된 node 하위의 sub tree 를 중위 순회(left-root-right)하여 print 합니다.  
	 * @param root
	 */
	public void display(Node root) {
		if (root != null) {
			display(root.left);
			System.out.print(" " + root.data);
			display(root.right);
		}
	}
}

class Node {
	int data; 
	Node left; 
	Node right;

	// constructor
	public Node(int data) {
		this.data = data;
		left = null;
		right = null;
	}
}