BST - 이진 탐색 트리

Binary Search Tree

public class BinarySearchTree {
	
	Node root;
	// 맨 첫 번째 부모 노드를 포인팅하는 노드 포인터
	// LL이든 Tree든 맨 첫 번째 노드는 기본적으로는 포인팅을 앞에서 해주는 노드가 없어서
	// 이렇게 인위적으로 head, first, root 노드를 만들어서 포인팅 해주지 않으면
	// garbage collected 당하고 그 밑에 애들까지 다 줄줄이 딸려 가서 버려진다.
	
	class Node { // inner class
		int value;
		Node left;
		Node right;
		
		Node(int value) {
			this.value = value;
		}
	}
	
	/** 생성자 1 : 무조건 Tree 안에 Node 객체 넣어주는 생성자 **/
	public BinarySearchTree(int value) {
		Node newNode = new Node(value);
		root = newNode;
	}
	
	/** 생성자 2 : 안에 든 게 아무 것도 없는 Tree를 만드는 생성자, 
	 * null로 initialize **/
	public BinarySearchTree () {
		root = null;
	}
	
	
	/***** INSERT FUNCTION START *****/
	public boolean insert(int value) {
		Node newNode = new Node(value);
		
		// empty 트리인 경우 root = 추가할 노드 
		if (root == null) {
			root = newNode;
			return true;
		}
		
		// Tree를 iterate 할 변수를 새로 생성
		// 반복문 바깥에다 생성하는 것을 잊지 말 것 - 매번 객체 생성되는 낭패 방지 
		Node temp = root;
		
		// 트리는 LL과는 달리 몇 번 iterate 해야 하는지 불분명하므로
		// for 문이 아닌 while 문으로 iterate
		while(true) {
			// 트리 안에 이미 있는 value를 중복해서 넣을 수 없다
			if (newNode.value == temp.value) return false;
			
			// 노드랑 비교해서 크면 오른쪽 작으면 왼쪽으로 노드 방향을 트는 작업
			// BST는 Divide and Conquer Strategy : O(log n)
			// 둘 중 하나 선택해서 비교, 반으로 잘라서 비교...
			if(newNode.value < temp.value) {
				if(temp.left == null) {
					// 비어 있는 자리라면 거기다가 insert
					temp.left = newNode;
					return true;
				}
				// 왼쪽으로 방향 이동
				temp = temp.left;
			} else {
				// 방향만 다를 뿐 위와 같은 작업 
				if(temp.right == null) {
					temp.right = newNode;
					return true;
				}
				temp = temp.right;
			}
		}
	}
	/***** INSERT FUNCTION END *****/
		
	/***** CONTAINS FUNCTION START *****/
	// 어떤 숫자가 트리 안에 존재하는지 탐색하는 메서드 
	public boolean contains(int value) {
		if(root == null) return false;
		Node temp = root;
		while (temp != null) {
			if (value < temp.value) {
				temp = temp.left;
				// temp 포인터가 가리킨 곳보다 내가 찾고 싶은 값이 더 작으면
				// 왼쪽으로 가서 찾아보자 
			} else if (value > temp.value) {
				temp = temp.right;
				// temp 포인터가 가리킨 곳보다 내가 찾고 싶은 값이 더 크면 
				// 오른으로 가서 찾아보자 
			} else {
				return true;
				// 같은 경우를 찾았기에 true를 반환 
			}
		}
		
		// while이 다 끝나도록 못 찾았으니 찾는 값이 없음 
		return false;
	}
	/***** CONTAINS FUNCTION END *****/
}