오늘은 이진 탐색 트리(Binary Search Tree)에 대해 다루어 보도록 하겠습니다.
이진 탐색 트리는
트리 구조에서 자식이 항상 2개 이하인 Binary Tree 의 특성을 그대로 물려 받고
거기에 "탐색" 이라는 키워드가 추가되었다고 생각하시면 되겠습니다.
탐색을 용이하기 위해 한가지 규칙이 더 추가되었는데요
자식을 입력할 때 왼쪽 자식엔 현재 노드보다 작은 값을, 오른쪽 자식엔 현재 노드보다 큰 값을 넣는 규칙입니다.
그런 규칙을 갖게 되면, 현재 갖고있는 key를 찾을 때
개별 node에서 크기를 비교해서 왼쪽 child로 탐색할 지 오른쪽 child로 탐색할지를 파악할 수 있어
경로를 찾기에 매우 용이합니다.
Binary Search Tree의 예시인데요
Root node 인 8부터 살펴보면
그 왼쪽은 모두 8보다 작은 값, 그 오른쪽은 모두 8보다 큰 값들로 이루어져 있습니다.
Root node가 3인 서브트리에서도, 그 왼쪽은 더 작고, 오른쪽은 더 큰 값들로 이루어져 잇는 것을 확인할 수 있습니다.
개별 서브 트리가 구조가 동일하기 때문에 재귀적인 방법으로 문제를 해결할 수 있습니다.
Methods
이진 탐색 트리가 제공하는 메소드들은 다음과 같습니다.
- insert ( average : O(log(n)), Worst : O(n) )
- delete ( average : O(log(n)), Worst : O(n) )
- search ( average : O(log(n)), Worst : O(n) )
- traverse : O(n)
사실 이진 탐색 트리의 insert와 delete를 수행할 때 search하는 행위가 항상 포함이 되므로
시간복잡도는 search하는 작업에 의존적이라고 보시면 됩니다.
구현한 코드를 토대로 실제로 어떻게 작동하는지에 대해 알아보겠습니다.
Implementation
typedef struct node_t {
Element data;
struct node_t *left;
struct node_t *right;
struct node_t *parent;
} node;
typedef struct BST_t {
node *root;
int *size;
} BST;BST에 사용될 트리의 node와 BST 구조체를 선언합니다.
BST * createBST(){
BST * bst = (BST *)malloc(sizeof(BST));
if(bst==NULL){
printf("Error occured while malloc Memory on BST");
return NULL;
}
bst->root = NULL;
bst->size = 0;
return bst;
}
node * createNode(Element data){
node * newNode = (node *)malloc(sizeof(node));
if(newNode == NULL){
printf("Error occured while malloc Memory on newNode");
return NULL;
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
newNode->parent = NULL;
return newNode;
}BST와 node를 생성하고 그 포인터를 반환합니다.
search
node *search(node *now, Element data){
if(now->data == data) return now;
else if(now->data < data){
if(now->right == NULL) return NULL;
else return search(now->right, data);
}
else{
if(now->left == NULL) return NULL;
else return search(now->left, data);
}
}data를 찾는 과정입니다.
현재 node와 우선 동일한지를 비교하고
그게 아니라면, 현재 node의 값과 주어진 값을 비교해서
주어진 값이 더 크면 오른쪽으로 탐색, 그게 아니면 왼쪽으로 탐색합니다.
재귀적으로 구성되며, 해당 데이터의 가진 node를 반환합니다.
insert
bool findplace(node *now, Element data){
if(now->data == data){
// 중복된 key를 입력할 수 있게 하려면, 구조체에 count를 두는 방법이 더 효율적입니다.
printf("You cannot push %d since it already exists in the tree\n",data);
return false;
}
else if(now->data < data){
if(now->right == NULL) {
now->right = createNode(data);
now->right->parent = now;
return true;
}
else return findplace(now->right, data);
}
else{
if(now->left == NULL){
now->left = createNode(data);
now->left->parent = now;
return true;
}
else return findplace(now->left, data);
}
}
void insert(BST *bst, Element data){
if(bst->size == 0) bst->root = createNode(data);
else if(!findplace(bst->root, data)) return;
bst->size++;
}BST에 값을 넣는 과정입니다.
우선 root node에 넣는지 확인 하고, root가 아니면 탐색을 시작합니다.
어디에 넣어야 할지를 찾는건데, 찾는 과정에서 동일한 값이 나타나면 입력을 못하게 막습니다.
데이터가 unique하다는 가정인데요, 중복된 정보를 넣게 하고 싶으면 node의 정보에 해당 데이터의 갯수를 등록하게 하면 됩니다.
현재 값이 넣으려는 값보다 크면 오른쪽으로 탐색해야하는데
만약 right child 자리에 아무 노드도 없으면, 그 지점에 노드를 생성하고 붙여주어야 합니다.
근데 만약 right child 자리에 뭔가 있다, 그러면 그 지점으로 이동하여 탐색해야 합니다.
값이 작을 때도, left-child에 뭔가 있으면 가서 탐색하고, 없으면 그 자리에 채워줍니다.
getMax, getMin
node * getMax(node *now){
if(now->right == NULL) return now;
else return getMax(now->right);
}
node * getMin(node *now){
if(now->left == NULL) return now;
else return getMin(now->left);
}주어진 서브트리에서 가장 크거나 작은 값을 리턴하는 함수입니다.
방식은 단순합니다. 계속 오른쪽으로, 혹은 왼쪽으로 가면 됩니다.
delete
bst는 다른 것들보다 삭제가 복잡합니다. 부모 노드, left child, right child 간 크기 관계를 유지해야 하기 때문이죠
삭제되는 노드에 아무 child도 없다면 그냥 삭제하면 되지만
만약 left child만 있는 경우, left child를 삭제되는 노드 자리로 옮겨주면 됩니다.
right child가 있는 경우, right child의 서브 트리에서 가장 작은 값과 현재 노드의 값의 위치를 바꿔주고
가장 작은 값이 있었던 위치의 노드를 제거해줍니다.
그렇게 하면, 크기 관계를 유지할 수 있게 됩니다.
void delete(BST *bst, Element data){
node *target = search(bst->root, data);
if(target == NULL){
printf("There's no %d in your bst", data);
return;
}
node *leftchild = target->left;
node *rightchild = target->right;
if(rightchild != NULL){ // target has a rightchild
node *minofrightchild = getMin(rightchild);
target->data = minofrightchild->data;
if(minofrightchild == target->right){
if(minofrightchild->right != NULL){
target->right = minofrightchild->right;
target->right->parent = target;
}
else target->right = NULL;
}
else{
if(minofrightchild->right != NULL){
minofrightchild->parent->left = minofrightchild->right;
minofrightchild->right->parent = minofrightchild->parent;
}
else minofrightchild->parent->left = NULL;
}
free(minofrightchild);
}
else if(leftchild != NULL){ // target has only a leftchild
leftchild->parent = target->parent;
if(target->data < target->parent->data) target->parent->left = target->left;
else target->parent->right = target->left;
free(target);
}
else{ // target has no child
if(target->parent != NULL){
if(target->data < target->parent->data) target->parent->left = NULL;
else target->parent->right = NULL;
}
free(target);
}
bst->size--;
if(bst->size == 0) bst->root = NULL;
}bst에서 값을 삭제합니다.
우선 먼저 search를 이용하여 제거하려는 타겟을 가져옵니다.
만약 그 타겟의 right child가 있으면
우선 해당 right child가 루트인 서브트리에서 가장 작은 값으로 현재 target node 의 값을 변경해줍니다.
- 만약 내 right child가 해당 서브트리에서 제일 작은 값이라면
- right child만 제거하고 나머지 이어주면 됩니다.
- 이 분기가 없으면 minofrightchild의 right child가 target의 left로 대체되버릴 수 있어 target 위치의 기존 연결이 끊어지게 됩니다.
- 만약 내 right child가 해당 서브트리에서 제일 작은 값이 아니라면
이런 상황에선 자연스럽게 minofrightchild는 서브트리의 가장 왼쪽 아래 어딘가 있는 녀석일 것입니다.
그럼 당연히 left child가 없을 거에요. right child만 고민해주면 됩니다.
- 해당 "right child가 루트인 서브트리"에서 가장 작은 값을 갖는 node가 right child가 있다면
- 현재 right child의 parent를 자신의 parent child로 바꾸어줍니다.
- 그리고 가장 작은 값을 갖는 node를 제거해줍니다.
다음과 같은 로직으로 분기가 됩니다.
생각보다 복잡해 보여도, 상황을 가정하고 하나씩 고민하가보면 금세 이해가 될 것이라고 생각합니다.
Skewed BST
위와 같이, 한쪽으로 많이 쏠려있는 BST를 Skewed BST 라고 합니다.
이런 구조는 애초부터 정렬된 값을 순서대로 BST에 넣는 상황에 발생하는데요
이렇게 되면, 개별 값들을 search 할때 양쪽으로 갈라짐으로써 생기는 이점들이 사라지게 됩니다.
갈라질 수도 없으니, 빠르게 구분하는 능력도 떨어지게 되는 것이지요.
이와 같은 Worst case에서 시간 복잡도는 O(n)으로 떨어져
개별 요청에 대한 탐색이 느려져 시스템의 지연을 발생시키는 주요한 원인이 됩니다.
이런 문제를 해결하기 위해서 AVL Tree, B Tree, B+ Tree, Splay Tree 등이 등장하게 되었는데요
다른 트리구조에서는 어떤 방식으로 해결하는지를 다음번에 알아보도록 하겠습니다.
여담
bst와 bts를 헷갈려하는 분들이 되게 많아서 간략하게 소개를 드리겠습니다.
bst는 binary search tree 의 약자이고
bts는 Bang Tan Sonyeondan 의 약자입니다.
단어 순서 하나로 이렇게 많은 차이가 드러나는게
참으로도 신기하고 재밌네요~
읽어주셔서 감사하고 오늘도 즐거운 하루 되세요!
Reference
'자료구조 & 알고리즘 > 자료구조' 카테고리의 다른 글
| [6] Heap (0) | 2020.10.28 |
|---|---|
| [4] 큐 (0) | 2020.10.25 |
| [3] 스택 (2) | 2020.10.20 |
| [2] Segment Tree (Lazy Propagation) (0) | 2020.09.28 |
| [1] Segment Tree (2) | 2020.09.13 |
댓글