Binary Search Tree 구현하기 (java)

1. Binary Search Tree란?

어떤 Node가 특정 값 value를 가질 때,
해당 Node의 왼쪽 서브 트리는 value보다 작은 값들로만 이루어져 있고,
해당 Node의 오른쪽 서브 트리는 value보다 큰 값들로만 이루어져 있는 Binary Tree를 뜻합니다.
이 때, 중복값은 허용되지 않습니다.

2. Constructor 만들기

class Node {
	public int value;
	public Node left;
	public Node right;

	Node(int value) {
		this.value = value;
	}
}

public class BST {

	private Node root;
	
	BST(int value) {
		Node newNode = new Node(value);
		root = newNode;
	}
}

3. Insert

1. Insert는 삽입하고자 하는 값(value)을 인자로 받고 삽입 여부를 return합니다.
2. root가 비어있는 경우 value를 root에 넣고 true를 return합니다.
3. root를 가리키는 임시변수를 만들어 value가 들어갈 곳을 찾습니다.
4. value가 temp가 가리키는 Node의 값보다 작으면 왼쪽, 크면 오른쪽으로 temp가 이동합니다.
5. temp의 값이 비어있을 때 value를 그 자리에 넣고 true를 return합니다.
6. 이미 BST에 존재하는 값은 삽입할 수 없으므로 temp가 가리키는 값과 value가 같은 경우 false를 return합니다.

	public boolean insert(int value) {
		Node newNode = new Node(value);
		if (root == null) {
			root = newNode;
			return true;
		}
		Node temp = root;
		while (true) {
			if (newNode.value == temp.value) {
				return false;
			}
			if (newNode.value < temp.value) {
				if (temp.left == null) {
					temp.left = newNode;
					return true;
				}
				temp = temp.left;
			} else {
				if (temp.right == null) {
					temp.right = newNode;
					return true;
				}
				temp = temp.right;
			}
		}
	}

4. Search

1. Search는 존재 유무를 확인하고자 하는 값(value)을 인자로 받고 존재 유무를 return합니다.
2. root가 비어있는 경우 value를 root에 넣고 true를 return합니다.
3. root를 가리키는 임시변수를 만들어 value를 찾습니다.
4. temp가 가리키는 노드의 값과 value가 같은 경우 true를 return합니다.
5. value가 temp가 가리키는 Node의 값보다 작으면 왼쪽, 크면 오른쪽으로 temp가 이동합니다.
6. 같은 값을 찾지 못하고 temp가 null을 가리키게 되면 value가 존재하지 않는 것이므로 false를 return합니다.

	public boolean search(int value) {
		if (root == null) {
			return false;
		}
		Node temp = root;
		while (temp != null) {
			if (value == temp.value) {
				return true;
			}
			if (value < temp.value) {
				temp = temp.left;
			} else {
				temp = temp.right;
			}
		}
		return false;
	}

5. Remove

1. Remove는 현재 기준이 되는 Tree의 root Node와 삭제하고자 하는 값 (value)을 인자로 받고, 삭제하고 나서의 Tree의 root Node를 return합니다.
2. root가 비어있는 경우 삭제할 수 있는 값이 없으므로, root를 그대로 return합니다.
3. value가 root의 값보다 작은 경우 root의 왼쪽 Node에서 remove 함수를 실행해줍니다.
4. value가 root의 값보다 큰 경우 root의 오른쪽 Node에서 remove 함수를 실행해줍니다.
5. 만약 value가 root의 값과 같으면, 해당 root를 삭제해주면 됩니다. 이 때, 세 가지 경우가 발생합니다.
   1 ) root의 왼쪽 Node가 null인 경우, 현재 root가 기준이 되는 Tree를 root의 오른쪽 Node가 root인 Tree로 덮어씌도록 root의 오른쪽 Node를 return합니다.
   2 ) root의 오른쪽 Node가 null인 경우 현재 root가 기준이 되는 Tree를 root의 왼쪽 Node가 root인 Tree로 덮어씌도록 root의 왼쪽 Node를 return합니다.
   3 ) root의 왼쪽과 오른쪽 Node가 모두 존재하는 경우, root의 현재 값을 root의 오른쪽 Tree 내에서 가장 작은 값으로 갱신하고, root의 오른쪽 Tree를 앞서 찾은 가장 작은 값을 remove한 Tree로 덮어씌웁니다.

	public Node remove(Node root, int value) {
		if (root == null) {
			return root;
		}
		if (value < root.value) {
			root.left = remove(root.left, value);
		} else if (value > root.value) {
			root.right = remove(root.right, value);
		} else {
			if (root.left == null) {
				return root.right;
			} else if (root.right == null) {
				return root.left;
			} else {
				root.value = findMinNode(root.right).value;
				root.right = remove(root.right, root.value);
            }
		}
		return root;
	}

	Node findMinNode(Node node) {
		while (node != null) {
			node = node.left;
		}
		return node;
	}

6. Binary Search Tree의 시간 복잡도

경우	최악	평균
숫자 insert하기	O(N)	O(logN)
숫자가 있는지 확인하기	O(N)	O(logN)
숫자 remove하기	O(N)	O(logN)