# 이진 탐색 트리 (BST)
정의
이진 탐색 트리는 노드의 오른쪽 하위 트리에는 '노드 값보다 큰 값'이 있는 노드만 포함되고, 왼쪽 하위 트리에는 '노드 값보다 작은 값'이 들어 있는 트리를 말합니다.
- 왼쪽 및 오른쪽 서브 트리도 해당 특성을 가집니다.
- 탐색의 시간 복잡도는 O(logN)이며, 최악의 경우 편향 트리가 되어 O(N)이 될 수도 있습니다.
- 이진 탐색 트리의 순회는 중위 순회(in order) 방식입니다.(왼쪽 - 루트 - 오른쪽)
- 값은 키값을 갖는 노드는 없습니다.
- 검색을 목적으로 하는 자료구조이기에, 중복이 많은 경우에 이 트리를 사용하도록 하여 검색 속도를 느리게 할 필요가 없습니다.
- 트리에 삽입하는 것보다 노드에 count를 가지게 하여 처리하는 것이 훨씬 효율적입니다.
# Successor와 Predecessor
# Successor
- 임의의 루트노드 x가 존재할 때 x보다 큰 값으로 이루어진 서브트리의 값 중 가장 작은 키 값을 의미합니다.
- right subtree의 최소값입니다.
# Predecessor
- 임의의 루트노드 x가 존재할 때 x보다 작은 값으로 이루어진 서브트리의 값 중 가장 큰 키 값을 의미합니다.
- left subtree의 최대값입니다.
# BST 생성하기
50, 15, 62, 80, 7, 54, 11
의 순서대로 BST를 생성해보자.
- 첫번째 요소를 트리의 루트로 트리에 삽입합니다.
- 다음 요소를 읽고 루트 노드 요소보다 작 으면 왼쪽 하위 트리의 루트로 삽입합니다.
- 그렇지 않으면 오른쪽 하위 트리의 오른쪽 루트로 삽입합니다.
구현하기
struct node {
int data;
struct node *left, *right;
};
// 새로운 BST node 생성
struct node* newNode (int key) {
struct node* temp = (struct *node)malloc(sizeof(struct node));
temp->data = key;
temp->left = NULL;
temp->right = NULL;
return temp;
}
# BST에서 탐색하기
아래의 트리에서 60
이라는 요소를 찾아봅시다.
- 루트에서 시작합니다.
- 검색 값을 루트와 비교합니다. 루트보다 작으면 왼쪽에 대해 재귀하고 크다면 오른쪽으로 재귀합니다.
- 일치하는 값을 찾을 때까지 절차를 반복합니다.
- 검색 값이 없으면 null을 반환합니다.
구현하기
struct node* search (struct node* root, int key)
{
// root값이 null이거나 key값과 같다면 종료한다.
if (root == NULL || root->data == key)
return root;
// key가 root->data 보다 작으면 왼쪽 서브트리로 재귀한다.
if (root->data > key)
return search(root->left, key)
// key가 root->data 보다 크면 오른쪽 서브트리로 재귀한다.
return search(root->left, key)
}
# BST에 요소를 삽입하기
아래의 트리에 10
이라는 요소를 삽입해봅시다.
- Root에서 시작합니다.
- 삽입 값을 루트와 비교합니다. 루트보다 작으면 왼쪽으로 재귀하고 크다면 오른쪽으로 재귀합니다.
- 리프 노드에 도달한 후 노드보다 크다면 오른쪽에 작다면 왼쪽에 삽입합니다.
구현하기
struct node* insert(struct node *root, int key) {
// 트리가 비어있다면 새로운 노드를 만든다.
if (root == NULL)
return newNode(key);
// 루트값보다 크면 오른쪽으로 재귀하고, 작다면 왼쪽으로 재귀한다.
if (key > root->data)
root->right = insert(root->right, key);
else if (key < root->data)
root->left = insert(root->left, key);
// 같은 값을 가지고 있는 경우 삽입을 하지 않는다.(중복 불가)
return root;
}
# BST의 값을 삭제하기
# 삭제할 노드가 리프 노드인 경우
아래의 트리에 1
이라는 요소를 삭제해봅시다.
- 그냥 단순히 말단 노드만 지우면 되기에 간편합니다.
# 삭제할 노드에 자식이 하나만 있는 경우
아래의 트리에서 30
이라는 요소를 삭제해봅시다.
- 해당 노드를 삭제하고 자식 노드를 삭제된 노드의 부모에 직접 연결합니다.
# 삭제할 노드에 자식이 둘이 있는 경우
아래의 트리에서 50
이라는 요소를 삭제해봅시다.
구현하기
// 노드의 최소값을 가져오는 함수
struct node* minValueNode (struct node* node){
struct node* current = node;
while(current && current->left != NULL)
current = current->left;
return current;
}
struct node* deleteNode (struct node* root, int key) {
// base case
if(root == NULL)
return root;
// 삭제할 노드를 찾는다.
if (key < root->data)
root->left = deleteNode(root->left,key);
else if (key > root->data)
root->right = deleteNode(root->right, key);
// 삭제할 노드를 찾은 경우
else {
struct node* temp;
// 노드에 자식이 하나 이거나 없는 경우
if (root->left == NULL) {
temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL) {
temp = root->left;
free(root);
return temp;
}
// 노드에 자식이 둘 있는 경우
// successor 노드를 찾는다.
temp = minValueNode(root->right);
// successor 노드 키와 삭제할 노드 키를 바꾼다.
root->key = temp->key;
// 노드를 삭제한다.
root->right = deleteNode(root->right, temp->key);
}
return root;
}
- 삭제할 노드를 찾습니다.
- 삭제할 노드의 successor 노드를 찾습니다.
- 삭제할 노드와 successor 노드의 값을 바꿉니다.
- successor 노드를 삭제합니다.
주의
편향된 트리는 시간 복잡도가 O(N) 이므로 트리를 사용할 이유가 존재하지 않게 됩니다.
이를 바로 잡도록 도와주고 개선된 트리는 AVL Tree, RedBlack Tree가 있습니다.
# 참고자료
- 주홍철.면접을 위한 CS 전공지식 노트.서울:길벗,2022.
- yoongrammer (opens new window)
- WooVictory (opens new window)
- HyeminNoh (opens new window)