[자료구조] 이진 탐색 트리 (BST; Binary Search Tree)

 

이진 탐색 트리

이진 탐색 트리는 이진 트리를 기반으로 한 탐색을 위해 만들어진 자료 구조입니다.

기존의 이진 트리 정의를 지키면서 탐색에 용이하게 왼쪽 노드에는 루트 노드보다 작은 키의 노드를, 오른쪽 노드에는 루트 노드보다 큰 키의 노드를 삽입해줍니다.

 

이진 탐색 트리의 정의

• 모든 원소의 키는 유일한 키를 가진다.
• 왼쪽 서브 트리 키들은 루트 키보다 작다.
• 오른쪽 서브 트리의 키들은 루트의 키보다 크다.
• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

찾고자 하는 키 값이 이진 트리의 루트 노드 키 값과 비교해 루트 노드보다 작으면 왼쪽 서브 트리에 있고 루트 노드보다 크면 오른쪽 서브 트리에 있는 성질을 이용하여 탐색을 쉽게 할 수 있습니다.

 

동작 방식은 아래와 같습니다.

 

비교한 결과가

• 같으면 → 탐색이 성공적으로 끝난다.
• 루트 노트의 값보다 작으면 → 탐색은 루트 노드의 왼쪽 자식을 기준으로 다시 시작하게 된다.
• 루트 노트의 값보다 크면 → 탐색은 루트 노드의 오른쪽 자식을 기준으로 다시 시작하게 된다.

 

재귀를 이용한 탐색 연산

// 재귀를 이용한 탐색 함수
TreeNode *search(TreeNode *node, int key) {
	if(node == NULL) return NULL;
	if(key == node->key) return node;
	else if (key < node->key) {
		return search(node->left, key);
	} else {
		return search(node->right, key);
	}
}

 

반복문을 이용한 탐색 연산

TreeNode *search(TreeNode *node, int key) {
	while(node != NULL) {
		if (key == node->key) return node;
		else if (key < node->key) {
			node = node->left;
		} else {
			node = node->right;
		}
	}
	return NULL; // 탐색에 실패했을 경우 NULL 반환
}

 

이진 탐색 트리에서 삽입 연산

이진 탐색 트리에서는 삽입 시 노드의 크기를 비교해서 위치가 정해지기 때문에 같은 값을 가지는 노드가 없어야 합니다. 그래서 삽입 전 탐색을 먼저 수행합니다. 탐색에 실패한 위치가 새로운 노드를 삽입하는 위치가 됩니다.

단말 노드를 발견할 때까지 루트에서 키를 검색하기 시작합니다. 단말 노드가 발견되면 새로운 노드가 단말 노드의 하위 노드로 추가됩니다.

 

이진 탐색 트리에서 삭제 연산

삭제 연산이 이진 트리에서의 연산 중 가장 복잡합니다. 노드를 탐색했으면 다음의 3가지 경우를 고려해야 합니다.

 

삭제하려는 노드가

1. 단말 노드인 경우 → 단말 노드만 지우면 됩니다.
2. 왼쪽이나 오른쪽 서브 트리 중 하나만 가지고 있는 경우 → 자기 노드는 삭제하고, 서브 트리는 자기 노드의 부모 노드에 붙여주면 됩니다.
3. 두 개의 서브 트리 모두 가지고 있는 경우 → 삭제되는 노드와 가장 값이 비슷한 노드를 정해야 다른 노드들을 이동시키지 않아도 이진 트리가 유지됩니다. 이는 지우려는 노드의 왼쪽 서브트리에서 가장 큰 값 or 오른쪽 서브트리에서 가장 작은 값이 됩니다. 둘 중 아무 값이나 와도 상관 없습니다.

// 이진 탐색 트리와 키가 주어지면 키가 저장된 노드를 삭제하고 새로운 루트 노드를 반환한다.
// 새로운 루트 노드를 반환한다.
TreeNode *delete_node(TreeNode *root, int key) {
	if (root == NULL) return root;
	
	// 만약 키가 루트보다 작으면 왼쪽 서브트리에 있는 것
	if (key < root -> key) {
		root -> left = delete_node(root -> left, key);
	}

	// 만약 키가 루트보다 크면 오른쪽 서브트리에 있는 것
	if (key > root -> key) {
		root -> right = delete_node(root -> right, key);
	}

	// 키가 루트와 같으면 이 노드를 삭제하면 됨
	else {
		if(root -> left == NULL) {
			TreeNode *temnp = root -> right;
			free(root);
			return temp;
		} else if (root -> right == NULL) {
			TreeNode *temp = root -> left;
			free(root);
			return temp;
		} 
		// 세 번째 경우
		TreeNode *temp = min_value_node(root -> right);

		// 중위 순회 시 후계 노드를 복사한다.
		root -> key = temp -> key;

		// 중위 순회 시 후계 노드를 삭제한다.
		root -> right = delete_node(root -> right, temp -> key);
	}
	return root;
}

TreeNode *min_value_node(TreeNode *node) {
	TreeNode * current = node;

	// 맨 왼쪽 단말 노드를 찾으러 내려감
	while (current -> left == NULL) {
		current = current -> left;
	}
	return current;
}

 

이진 탐색 트리의 분석

n개의 노드를 가지는 이진 탐색 트리의 경우, 일반적인 이진 트리의 높이는 $\lceil log_2n \rceil$이므로 이진 탐색 트리 연산의 평균적인 경우의 시간 복잡도는 $O(log_2h)$입니다.

 

최악의 경우에는 트리가 한쪽으로 치우치는 경우인데, 이렇게 되면 높이가 n이 됩니다. 따라서 탐색, 삭제, 삽입 시간이 $O(n)$으로 늘어납니다. 선형 탐색과 같아져 시간적으로 이득이 없기 때문에, 이런 경우를 방지하기 위해 트리를 균형지게 만드는 기법들(AVL 트리 등)이 많이 개발되었습니다.