티스토리 뷰
<이진 탐색트리> 탐색, 삽입, 삭제 알고리즘 및 시간복잡도 분석
wisecow 2017. 7. 15. 23:05# 이진 탐색 트리란? // 이 글은 복붙 및 드래그가 불가하니 밑에 소스파일을 다운로드 해주세요.
이진 탐색 트리(binary search tree)는 이진 트리 기반의 탐색을 위한 자료 구조이다. 이진 탐색 트리의 조건에는 아래와 같이 4개의 조건이 있다.
- 모든 노드의 키는 유일하다. // 중복된 데이터를 갖는 노드가 없다는 뜻이다. 여기서 키의 의미는 노드 안에 들어 있는 데이터 값을 의미한다.
- 왼쪽 서브 트리의 키들은 루트의 키보다 작다. // 예를 들어 루트노드의 데이터가 5라고 하면, 왼쪽 서브트리에는 무조건 5보다 작은 값들만 존재해야 한다.
- 오른쪽 서브 트리의 키들은 루트의 키보다 크다. // 위와 같은 원리로 오른쪽에는 루트의 데이터 값보다 더 큰 값들만 존재한다.
- 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. // 순환적으로 정의되었다는 뜻이다. 즉 왼쪽 서브트리로 내려가든, 오른쪽 서브트리로 내려가든 동일한 법칙이 적용된다는 뜻이다.
개념을 정리하기 위해 이진 탐색 트리의 정의를 만족하는 그림으로 구체적인 예시를 확인해보도록 하자.
위에서 말한 것과 같이 왼쪽 서브트리에는 루트키(18)보다 작은 값들만 모아져 있으며, 오른쪽 서브트리에는 루트키(18)보다 큰 값들만 모아져 있다. 이러한 룰은 왼쪽 서브트리 자체에도 적용된다. 왼쪽 서브트리로 내려간 순간, 새로운 루트키(7)을 기준으로 왼쪽에는 7보다 작은 3이, 오른쪽에는 7보다 큰 12가 위치하고 있다. 이러한 조건을 만족하는 것이 이진 탐색 트리다.
# 이진 탐색 트리 <탐색 알고리즘>
이진 탐색 트리의 특징을 활용한 탐색 알고리즘을 생각해본다. 어떻게 알고리즘을 구성할 수 있을까? 이진 탐색 트리의 특징을 이용하면 아래와 같은 개념을 도출할 수 있다.
- 루트 노드의 키와 사용자가 찾고자하는 값을 비교한다. 비교해서 같다면, 탐색을 마친다. (성공적으로 이루어졌을 경우)
- 찾고자 하는 값이 루트 노드의 키 값보다 작으면, 탐색은 루트노드 기준으로 왼쪽 서브트리를 기준으로 다시 시작한다. // 루트의 키값보다 작은 값들은 왼쪽에만 존재하는 것이 이진 탐색 트리이기 때문이다.
- 찾고자 하는 값이 루트 노드의 키 값보다 크면, 탐색은 루트노드 기준으로 오른쪽 서브트리를 기준으로 다시 시작한다. // 다시 시작한다는 말의 의미는 동일한 룰을 오른쪽 서브트리에 적용하여 탐색을 하겠다는 의미다.
/*************************************************
** 2가지 버전의 이진탐색트리 탐색 알고리즘
*************************************************/
// 필요한 헤더파일은 포함되어 있다고 가정합니다.
typedef struct TreeNode {
int key;
struct TreeNode *left, *right;
} TreeNode;
// 순환 버전
TreeNode *search1(TreeNode *node, int key)
{
/* 찾고자 하는 값을 찾아봤는데 아예 없었을 경우
혹은 애초에 node 자체가 NULL이었을 경우 */
if (!node)
return NULL;
// 순환으로 탐색 중 원하는 값을 찾았을 때
if (key == node->key)
return node; // 해당 노드의 주소를 반환
// 찾는 값보다 루트키값이 작은 경우
else if (key > node->key)
search(node->right, key); // 오른쪽 서브트리로 이동
// 찾는 값보다 루트키값이 큰 경우
else
search(node->left, key); // 왼쪽 서브트리로 이동
}
// 반복 버전
TreeNode *search2(TreeNode *node, int key)
{
/* 찾고자 하는 값을 찾아봤는데 아예 없었을 경우
혹은 애초에 node 자체가 NULL이었을 경우 while문을
탈출하게 된다. */
while (node) // node가 NULL이 아니라면 일단 탐색을 계속한다.
{
// 원하는 키 값을 발견했을 경우
if (key == node->key)
return node; // 해당 노드의 주소 반환
// 찾고자 하는 값보다 루트키값이 더 큰 경우
else if (key < node->key)
node = node->left; // 왼쪽 서브트리로 이동
// 찾고자 하는 값보다 루트키값이 더 작은 경우
else
node = node->right; // 오른쪽 서브트리로 이동
}
return NULL;
}
/*************************************************
** End Line
*************************************************/
매개 변수로 넘어온 TreeNode *node 의 경우 원본의 복사본이므로, 변경하여도 원본에 영향이 가지는 않는다. 물론 node->key 값을 건드리는 건 절대 안된다. 그렇게 하면 원본에 영향이 가는 것이기 때문에. 여기서 변경해도 된다고 한 건 node가 가지고 있는 주소값 자체다. 애초에 탐색 알고리즘은 값을 쓰는 게 아니라 읽고 비교만 하는 것이기 때문에 node->key 값을 변경하는 일은 없을테지만 말이다.
# 이진 탐색 트리 <삽입 알고리즘>
삽입이란 특정 위치에 원하는 정보를 넣는 행위를 뜻한다. 그렇다. 특정 위치를 먼저 알아내야지만이 그 위치에 데이터를 삽입할 수 있다. 또한 내가 삽입하려는 데이터가 이미 존재하는 것일 수도 있기 때문에, 먼저 탐색을 해야만 한다. 결과적으로 탐색을 실패한 위치가 바로 새로운 노드를 삽입하는 위치가 된다.
왜 탐색이 실패한 위치가 새로운 노드를 삽입하는 위치가 되는지 구체적인 예시로 살펴보도록 하자.
9를 삽입하기 위해 먼저 9가 있나 탐색을 시작한다. 루트키인 18보다 9는 작으므로, 왼쪽 서브트리로 이동한다. 새로운 루트키인 7보다 9가 크므로 오른쪽 서브트리로 이동한다. 새로운 루트키인 12보다 9가 작으므로 왼쪽 서브트리로 이동한다. 왼쪽 서브트리는 NULL 이므로 탐색이 끝난다. 밑에 알고리즘을 코드로 보도록 하자.
/*************************************************
** 이진 탐색 트리 삽입 알고리즘
*************************************************/
// 필요한 헤더파일은 포함되어 있다고 가정합니다.
typedef struct TreeNode {
int key;
struct TreeNode *left, *right;
} TreeNode;
// key를 이진 탐색 트리 root에 삽입한다.
// key가 이미 root 안에 있으면 삽입되지 않는다.
void insert_node(TreeNode **root, int key)
{
// t는 탐색을 위한 포인터다.
TreeNode *p, *t; // p는 부모노드를 가리키는 포인터, t는 현재노드 포인터
TreeNode *n; // n은 새로운 노드
t = *root; // 처음 시작시 현재 노드는 root 그 자체다.
p = NULL; // root의 부모노드는 없다. root 자체가 시초
// 탐색을 먼저 수행한다.
while (t)
{
if (key == t->key) return;
p = t; // 부모 노드를 현재 노드로 설정한다. 새로운 루트노드.
// 서브트리의 새로운 루트노드가 등장하는 것과 같은 원리다.
if (key < p->key) // 부모의 키 값과 비교
t = p->left; // 현재 노드는 부모의 왼쪽 서브트리가 된다.
else
t = p->right; // 현재 노드는 부모의 오른쪽 서브트리가 된다.
}
// key가 트리 안에 없으므로 삽입이 가능하다.
// 새로 삽입될 노드를 생성한다.
n = (TreeNode *)malloc(sizeof(TreeNode));
if (!n) return; // 동적할당 실패했을 경우 return
// 데이터를 복사한다.
if (p) // 부모 노드가 존재할 경우
{
if (key < p->key)
p->left = n;
else
p->right = n;
}
else // 부모 노드가 없으니 새로 생긴 노드가 루트노드가 된다.
*root = n;
}
/*************************************************
** End Line
*************************************************/
다소 복잡해 보이긴 하지만, 탐색 알고리즘을 응용한 버전이라 생각하면 편하다. 여기서는 부모 노드와 현재 노드에 대한 포인터를 각각 p, t로 따로 주고 있다. 왜냐하면, 부모노드에 대한 포인터 없이 탐색을 해나가서 NULL 이 나왔다고 가정해면 여기다가 새로운 노드를 삽입할 방법이 없다. 새로운 노드를 생성해서 NULL에 붙인다는 건 말이 안된다. 무조건 그 전에 있던 부모에 대한 포인터를 알아야만 하기 때문에 이렇게 따로 둔 것이다.
# 이진 탐색 트리 <삭제 알고리즘>
대망의 삭제 알고리즘이다. 이진 탐색 트리 관련 알고리즘 중 가장 복잡하다. 삭제도 먼저 삽입과 마찬가지로 탐색을 먼저 해야한다. 삭제하길 원하는 키 값이 트리 안의 어디에 위치하는지를 알아야 삭제할 수 있기 때문이다. 노드를 탐색했다면, 아래의 3가지 경우를 고려해야 한다. 삭제시 발생할 수 있는 상황 3가지다.
- 삭제하려는 노드가 단말노드일 경우 (자식 노드가 없을 경우)
- 삭제하려는 노드가 하나의 서브트리만 가지는 경우 (왼쪽 혹은 오른쪽 둘 중 하나만)
- 삭제하려는 노드가 두 개의 서브트리를 모두 가지고 있는 경우
/************************************************* ** 이진 탐색 트리 삽입 알고리즘 *************************************************/ // 필요한 헤더파일 및 구조체는 포함되어 있다고 가정합니다. // 트리 구조체는 위의 소스코드들과 동일합니다. void delete_node(TreeNode **root, int key) { TreeNode *parent, *child, *suc, *suc_p, *t; // key를 갖는 노드 t를 탐색한다. parent는 t의 부모노드다. parent = NULL; // 시초가 되는 root의 부모는 없다. t = *root; // key를 갖는 노드 t를 탐색한다. while (t != NULL && t->key != key) { parent = t; // 부모를 t값과 동일하게 준 후 t를 통해 탐색한다. // t는 왼쪽이나 key값에 따라 왼쪽이나 오른쪽으로 내려간다. t = (key < parent->key) ? parent->left : parent->right; } // 탐색이 끝난 시점에서 만약 키 값이 트리에 없었다면 t는 NULL일 것이다. if (!t) { printf("key is not in the tree"); return; // 원하는 값이 없으므로 return 한다. } // 위에서 탐색을 못했을 경우를 다뤘기 때문에 이 아래부터는 탐색이 // 성공적으로 이루어졌다는 가정 하에 경우의 수를 따진다. // 첫 번째: 단말노드였을 경우 if (t->left == NULL && t->right == NULL) { if (parent) // 부모 노드가 NULL이 아닐 때, 즉 존재할 때 { if (parent->left == t) parent->left = NULL; else parent->right = NULL; } else // 부모 노드가 NULL 이라면, 삭제하려는 노드가 루트 노드다. *root = NULL; } // 두 번째: 하나의 서브트리만 가지는 경우 else if ((t->left == NULL) || (t->right == NULL)) { child = (t->left != NULL) ? t->left : t->right; if (parent) { if (parent->left == t) parent->left = child; else parent->right = child; } else // 부모 노드가 NULL이라면 삭제되는 노드가 루트노드다. *root = child; } // 세 번째: 두개의 서브트리를 모두 가지는 경우 else { // 오른쪽 서브트리에서 가장 작은 값을 찾는다. suc_p = t; suc = t->right; while (suc->left != NULL) { suc_p = suc; suc = suc->left; } // 후속자의 부모와 자식을 연결 if (suc_p->left == suc) suc_p->left = suc->right; // 왼쪽 끝까지 내려왔지만 그 끝에 오른쪽 서브트리가 있을 수도 있는데, // 이 경우를 대비해 suc->right 값을 대입하는 것이다. // 그림을 그려 보면 편하다. 포스팅에 그림을 첨부하겠다. else suc_p->right = suc->right; // 아래 두 개의 문장을 실행하는 이유는 무엇일까? // 포스팅에 자세히 풀어 설명해보았다. t->key = suc->key; t = suc; } free(t); } /************************************************* ** End Line *************************************************/
이 알고리즘에서 가장 헷갈리는 부분은 3번째 케이스일 것이다. 갑자기 변수를 3~4개씩이나 쓰고 코드 또한 그리 간단하지가 않다. 일단 첫 번째로, 세 번째 알고리즘을 가장 잘 이해할 수 있는 그림을 밑에 첨부했다. 밑에 그림의 빨간색 표시 부분이 현재 지워야할 부분 t라고 가정하고, 세 번째 알고리즘을 그대로 따라가 보도록 하자.
기존의 그림과 달라진 점은 맨 밑에 22노드 우측자식노드로 23이 추가됐다는 점이다. 이 그림을 토대로 3번째 케이스의 알고리즘 따라가보자. 따라가다 보면, 대체로 이해가 되지만 마지막 부분에서 막힐 수 있다. 블로그 주인장 또한 이해가 안되서 애먹던 부분이다.
- t->key = suc->key; | t = suc; // 파이프 기호는 두 개의 문장이 있다고 구분해주기 위해 썼을 뿐이다. 밑에도 동일
주인 장은 맨 아래 이 두 문장 때문에 매우 고민했다. 왜 이렇게 한 걸까? 생각을 해보면 이렇다. 우리가 현재 삭제하고 싶은 노드는 18노드다. 18노드를 삭제하고 우측 서브트리에서 제일 작은 값인 22를 그 자리에 대체하고 싶다. 이러한 상황에서 만약 t->key = suc->key; 문장을 써주지 않으면 어떤 일이 발생할까? 를 생각해보면 이해가 쉬울 것이다.
그렇다. suc->left = t->left; | suc->right = t->right; 작업을 해줘야 한다. 만약 이렇게 해줬을 경우 뒤에 따라 나오는 문장인 t = suc; 은 필요가 없다. suc을 있는 그대로 대체하고 싶다면, 삭제하고 싶은 노드가 원래 가지고 있던 왼쪽 링크필드와 오른쪽 링크 필드를 그대로 suc의 링크필드에 복사해야 한다. 하지만, 이 작업이 번거롭다고 판단한 나머지 그냥 기존에 있던 t를 버리지 않고, 키 값을 suc의 키값으로 대체한 것이다.
기존에 있던 suc는? 그렇다. 그냥 free로 메모리 반납해주면 된다. 하지만, 왜 굳이 또 t = suc; 이란 문장을 넣은 걸까? 이유는 간단하다. 우리는 3가지 케이스를 if 문으로 한 데 모아 다루고 있다. free(t) 부분이 if 문을 벗어난 맨 마지막에 있으므로, 세 번째 케이스 또한 어떻게든 free(t) 문을 그대로 이용할 필요가 있는 것이다. 그래야 중복된 코드 작성이 안되고 일관성이 있으니까. 그래서 t를 그대로 활용한 뒤, t가 가리키는 노드를 suc으로 대체한 후 반납하는 것이다. 마치 대리반납과 비슷한 느낌이다.
이진탐색트리 알고리즘.c# 이진 탐색 트리의 시간복잡도 분석
이진 탐색 트리에서의 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이를 $h$라고 했을 때 $O(h)$가 된다. 따라서 $n$개의 노드를 가지는 이진 탐색 트리의 경우, 균형 잡힌 이진 트리의 높이는 $\ulcorner$$log_2n$$\urcorner$이므로 이진 탐색 트리 연산의 평균적인 경우의 시간 복잡도는 $O(log_2n)$이다. // 참고로 $log_2n$ 양 옆에 붙어 있는 기호는 올림 기호이다. 반올림과 내림의 기호 또한 각각 따로 존재한다.
위 그래프의 경우 높이를 계산하면 높이 = $\ulcorner$$log_2n$$\urcorner = \ulcorner$$log_215$$\urcorner = 4$ 가 나온다. 그러나 이는 위와 같이 서브 트리가 균형을 이루고 있을 경우이고, 한쪽으로 치우치는 경사 이진 트리일 경우에는 $n$개의 노드를 가지는 트리의 높이가 $n$과 같게 되어 탐색, 삭제, 삽입 시간이 거의 선형 탐색과 같이 $O(n)$이 된다. 경사이진트리는 아래의 그림과 같다.
경사 이진 트리의 경우 선형 탐색에 비하여 전혀 시간적으로 이득이 없다. 이러한 최악의 경우를 방지하기 위해 트리의 높이를 $\ulcorner$$log_2n$$\urcorner$으로 한정시키는 균형 기법이 필요하다. 트리를 균형 있게 만드는 기법으로는 AVL 트리를 비롯한 여러 기법들이 존재한다. 균형 트리의 경우는 별도의 포스팅으로 다룰 예정이다.
# 포스팅 작성 후기
삭제 알고리즘을 공부하고 설명하는 것이 제일 까다로웠다. 그것 말고는 크게 포스팅에 어려움은 없었다. 아직 우선순위 큐, 정렬 알고리즘, 그래프, 해싱 등 해야할 공부가 많다. 차근차근 공부해서 어서 포스팅 하고 싶다. 자료구조 공부하시는 분들 모두 화이팅!
'Develop Story > Data Structure & Algorithm' 카테고리의 다른 글
| <뇌를 자극하는 알고리즘 #1>: 단일 연결 리스트(SLL) 퀴즈풀이 (0) | 2017.07.21 |
|---|---|
| <선택 정렬 및 이진 탐색 알고리즘> #Selection sort #Binary search (0) | 2017.07.18 |
| <스레드 이진트리> 기본개념과 알고리즘 (0) | 2017.07.15 |
| <포인터와 메모리 동적할당> #포인터 #힙(Heap) #동적할당 (0) | 2017.07.14 |
| <이진트리 기본 알고리즘> #후위순회 #트리의 높이 #(단말)노드 개수 구하는 알고리즘 (0) | 2017.07.13 |
- Total
- Today
- Yesterday
