이진 탐색 트리 (Binary Search Tree)

정의

이진 트리의 특수한 형태. 다음의 조건을 만족한다. (재귀적 정의)
(1) 각 노드의 값은 왼쪽 서브트리의 모든 값보다 크거나 같다.
(2) 각 노드의 값은 오른쪽 서브트리의 모든 값보다 작거나 같다.

특성

• 중위 순회 (Inorder traversal, left -> root -> right) 가 오름차순으로 진행된다.
• 최악의 경우에도 모든 검색, 삽입, 삭제 연산을 O(h) 시간 복잡도로 수행할 수 있다. 데이터를 순서대로 저장하고 검색, 삽입, 삭제 등 여러 연산을 동시에 수행해야 하는 경우 BST가 좋은 선택이 될 수 있다. ex) 배열의 k번째로 큰 요소 반환 (BST 안 쓴다면 O(n^2))

연산

검색 (Search)

1. 대상값이 노드값과 같으면 노드 반환
2. 대상값이 노드값보다 작으면 왼쪽 서브트리에서 검색 계속
3. 대상값이 노드값보다 크면 오른쪽 서브트리에서 검색 계속

// (1) recursive (시간복잡도: O(h), 공간복잡도: O(h))
// (h는 트리의 높이)
public TreeNode searchBST(TreeNode root, int target) {
	if (root == null || root.val == target) {
		return root;
	}
	if (target < root.val) {
		return searchBST(root.left, target);
	}
	return searchBST(root.right, target);
}

// (2) iterative (시간복잡도: O(h), 공간복잡도: O(1))
public TreeNode searchBST(TreeNode root, int target) {
	TreeNode cur = root;
	while (cur != null && cur.val != target) {
		if (target < cur.val) {
			cur = cur.left;
		} else {
			cur = cur.right;
		}
	}
	return cur;
}

삽입 (Insertion)

1. 대상값과 노드값에 따라 왼쪽 혹은 오른쪽 서브트리 검색
2. 외부 노드?에 도달할 때까지 1 반복
3. 왼쪽 자식이나 오른쪽 자식으로 새로운 노드 추가

public TreeNode insertIntoBST(TreeNode root, int val) {
	if (root == null) { // 기저 조건 (새 값 넣을 자리)
		return new TreeNode(val);   // return a new node if root is null
	}
	if (root.val < val) {           // insert to the right subtree if val > root->val
		root.right = insertIntoBST(root.right, val);
	} else {                        // insert to the left subtree if val <= root->val
		root.left = insertIntoBST(root.left, val);
	}
	return root; // 마지막에 원래 root 반환
}

삭제 (Deletion)

다양한 방법이 있지만 변경사항을 최소화하는 방법은 다음과 같다. 대상 노드를 적절한 자식 노드로 대체하는 것이다.

1. (삭제) 대상 노드에 자식 노드가 없으면 바로 삭제
2. 대상 노드에 자식 노드가 하나 있으면 자식 노드를 대상 노드로 대체
3. 대상 노드에 자식 노드 두 개 있으면 in-order 기준으로 직전값(왼쪽 서브트리의 가장 오른쪽 노드)이나 직후값(오른쪽 서브트리의 가장 왼쪽 노드)으로 대체한다.

/**
* In BST, succesor of root is the leftmost child in root's right subtree (in-order 직후값)
*/
private TreeNode findSuccessor(TreeNode root) {
	TreeNode cur = root.right;
	while (cur != null && cur.left != null) {
		cur = cur.left;
	}
	return cur;
}

public TreeNode deleteNode(TreeNode root, int key) {
	// return null if root is null
	if (root == null) { // 기저 조건
		return root;
	}

	// delete current node if root is the target node
	if (root.val == key) {
		// replace root with root->right if root->left is null	
		if (root.left == null) {
			return root.right;
		}

		// replace root with root->left if root->right is null
		if (root.right == null) {
			return root.left;
		}

		// replace root with its successor if root has two children
		TreeNode p = findSuccessor(root);
		root.val = p.val;
		root.right = deleteNode(root.right, p.val);
		return root;
	}
	if (root.val < key) {
		// find target in right subtree if root->val < key
		root.right = deleteNode(root.right, key);
	} else {
		// find target in left subtree if root->val > key
		root.left = deleteNode(root.left, key);
	}
	return root;
}