이진 트리 기반의 탐색을 위한 자료 구조입니다.
여기서 탐색은 레코드 집합(자료 구조)에서 특정 레코드(자료)를 찾아내는 작업을 의미합니다.
레코드 마다 고유의 키(key)값을 가지고 있기 때문에 키 값을 가지고 탐색을 진행합니다.
정의 및 특징
이진 탐색 트리는 탐색을 위한 몇 가지 성질을 만족하는 트리를 의미합니다.
- 모든 원소(노드)의 키 값은 유일하다.
- 왼쪽 서브 트리의 키 값은 루트의 키 값 보다 작다.
- 오른쪽 서브 트리의 키 값은 루트의 키 값 보다 크다.
- 모든 서브 트리가 위와 같은 성질을 지닌다.
한마디로 표현하자면 한 노드는 왼쪽 자식 노드보다 큰 키 값을 가지고 오른쪽 자식 노드보다 작은 키 값을 가진다는 것입니다.
이진 탐색 트리에는 크게 탐색, 삽입, 삭제 세 가지 연산이 필요합니다.
- 탐색
- 루트부터 시작해서 key 값을 비교해가며 원하는 key이 더 작으면 왼쪽 서브트리로 더 크면 오른쪽 서브트리로 이동합니다.
- 두 갈래 중 하나를 선택해서 탐색하기 때문에 시간 복잡도는 O(logn) 입니다.
node* search(int key){
node* p = root;
while(p != NULL){
if(key < p->key){
p = p->left;
}
else if(key > p->key){
p = p->right;
}
else if(key == p-> key){
return p;
}
}
return p;
}
- 삽입
- 탐색 한 후 마지막으로 NULL인 자리에 새로운 노드를 생성한 후 key값을 설정해서 연결해주면 됩니다.
insert(int key){
node* new = new node;
new->key = key;
node* p = root;
node* r;
whlie(p != NULL){
r= p; // r은 p의 부모노드
if(key < p->key)
p = p->left;
else if(key > p->key)
p = p->right;
else
break;
}
if(key < r->key)
r->left = new;
else
r->right = new;
}
- 삭제
- 삭제 같은 경우가 가장 골치아픈 연산입니다.
- 세 가지 상황이 있습니다.
- 단말 노드(leaf node)를 삭제하는 경우
- 삭제하려는 노드가 한 쪽만 서브트리를 가지고 있는 경우
- 삭제하려는 노드가 두 쪽 모두 서브트리를 가지고 있는 경우
- 단말 노드일 경우 탐색하여 NULL로 만들어주면 됩니다.
- 하나의 서브트리만 가지고 있는 경우에는 그 서브트리의 루트를 대신 연결해주고 삭제를 진행하면 됩니다.
- 두 개의 서브트리를 가지고 있는 경우 새로 루트가 될 후보는 두 개의 노드입니다.
- 왼쪽 서브트리의 가장 큰 값(가장 오른쪽의 노드)
- 오른쪽 서브트리의 가장 작은 값(가장 왼쪽의 노드)
- 이 두가지 이외의 값으로 삭제를 진행한다면 서브트리를 재구성 해야합니다.
- 예를 들어, 오른쪽 서브트리에서 가장 큰 값을 새로운 루트로 지정한다면, 오른쪽 서브트리의 모든 노드들을 왼쪽 서브트리로 옮겨야 합니다.
- 두 방향의 깊이를 비교한다면 더 깊은 쪽의 노드를 선택하면 좀 더 균형을 맞출 수 있습니다.
delete_node(int key){
node* p = root;
node* r;
whlie(p != NULL){
r= p; // r은 p의 부모노드
if(key < p->key)
p = p->left;
else if(key > p->key)
p = p->right;
else
break;
}
if(p->left == NULL && p-> right == NULL){ // 단말 노드일 때
if(p->key == r->left->key)
r->left = NULL;
else if(p->key == r->right->key)
r->right = NULL:
}
else if(p->left == NULL || p-> right == NULL){ // 하나의 서브트리
node* nroot;
if(p->left == NULL)
nroot = p->right;
else
nroot = p->left;
if(nroot->key == r->left->key){
r->left = nroot;
}
else if(nroot->key == r->right->key){
r->right == nroot;
}
free(p);
}
else{ //양쪽에 서브트리, 오른쪽에서 후계자 찾기
node* r = p->right;
node* r_r; // 후계자의 부모노드 => 후계자가 단말노드이면 필요없지만 단말노드가 아닐 경우 필요합니다.
while(r -> left != NULL){
r_r = right;
r = r -> left;
}
if(r_r != NULL)
r_r->left = r->right;
p->key = r->key;
free(r);
}
이진 탐색 트리의 삽입 순서에 따라서 좌측 혹은 우측으로 치우치는 이진 탐색 트리가 될 수 있습니다.
이런 형태면 탐색 시간이 O(n)이 되기 때문에 균형적인 트리로 만들어 줄 필요가 있습니다.
이후에 AVL 트리 와 같은 균형을 맞추는 기법에 대해서도 소개하겠습니다.
의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!
'전체 > 자료구조' 카테고리의 다른 글
| 그래프(graph) (0) | 2019.04.23 |
|---|---|
| 트리(tree) (0) | 2019.04.22 |
| 큐(queue) (0) | 2019.04.21 |
| 스택(Stack) (0) | 2019.04.19 |
| 배열과 연결 리스트 (0) | 2019.04.18 |
