이번 포스트에서는 이진트리 중 어떤 성질을 만족하는 이진트리인 이진 탐색 트리를 포스팅하겠습니다.
이진탐색트리
이진트리는 다음 4가지 성질을 만족하는 이진 트리로 정의됩니다.
- 모든 원소는 유일한 키(value)를 가진다.
- 왼쪽 서브트리 내 키들은 루트의 키보다 작다.
- 오른쪽 서브트리 내 키들은 루트의 키보다 크다.
- 왼쪽 서브트리와 오른쪽 서브트리도 이진탐색트리이다.
위 성질을 가진 이진탐색트리를 중위순회 하게 되면 오름차순 목록을 얻을 수 있습니다.
이진탐색트리의 구현
이진탐색트리의 연산중 먼저 삽입연산입니다. 이진탐색트리의 4가지 성질을 만족하게 끔, 입력받은 키값을 각 노드들과 비교하며 입력받은 키의 위치를 찾아 삽입합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
|
Node* createNode(int data) { //노드 생성
Node* p = (Node*)malloc(sizeof(Node));
p->data = data;
p->left = p->right = nullptr;
return p;
}
Node* insert(Node* root, int key) {
if(root == nullptr) return createNode(key); //이진탐색트리에 노드가 1개도 없을 경우.
if(key > root->data) p->right = insert(p->right, key); //입력받은 키값이 현재 노드보다 클경우, 오른쪽 노드로 방문하여 삽입연산 수행.
else if (key < root->data) p->left = insert(p->left, key); //입력받은 키값이 현재 노드보다 작을 경우, 왼쪽 노드로 방문하여 삽입연산 수행.
return p;
}
|
cs |
다음은 탐색연산입니다. 삽입연산과 마찬가지로 4가지 성질을 이용하여 찾고자 하는 키값을 찾습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
Node* search(Node* p, int key) { //재귀적 방식으로 키값을 탐색
if(p == nullptr) return nullptr; //찾고자 하는 키값이 없을 경우
if(key == p->data) return p; //키값을 찾은 경우
if(key > p->data) return search(p->right, key); //찾고자 하는 키값이 현재 노드의 값보다 큰경우, 오른쪽 자식노드에서 탐색을 수행
return search(p->left, key); //찾고자 하는 키값이 현재 노드의 값보다 작은경우, 왼쪽 자식노드에서 탐색을 수행
}
Node* search(Node* p, int key) { //반복문을 통해 키값을 탐색
while(p != nullptr) {
if(key == p->data) return p;
if(key > p->data) p = p->right;
else p = p->left;
}
return nullptr;
}
|
cs |
다음은 탐색 중에서 최소값과 최대값의 탐색입니다.
이진 탐색 트리의 규칙에 따라 최소값은 루트노드로 부터 왼쪽 자식노드로 더이상 다음 노드가 없을 때 까지 가면, 가리키는 노드가 최소값입니다. 왜냐하면, 모든 서브트리는 이진탐색트리를 이루기 때문에, 루트보다 작은 값은 항상 왼쪽에 배치됩니다. 따라서 최소값은 왼쪽으로 쭉 갔을 때 위치합니다.
최대값의 경우는 최소값 탐색의 반대를 수행하면 됩니다.
1
2
3
4
5
6
7
8
9
10
11
|
Node* min(Node* p) { //최소값 탐색
if(p == nullptr) return nullptr;
while(p->left != nullptr) p = p->left;
return p;
}
Node* max(Node* p) { //최대값 탐색
if(p == nullptr) return nullptr;
while(p->right != nullptr) p = p->right;
return p;
}
|
cs |
다음은 삭제연산입니다.
이진 탐색 트리의 삭제 연산은 다음 3가지 경우로 나뉩니다.
- 삭제 노드가 단말 노드인 경우
- 삭제 노드가 하나의 서브트리를 가지는 경우
- 삭제 노드가 두 개의 서브트리를 가지는 경우
1번의 경우, 삭제노드 x의 부모노드 p의 x로 가는 경로를 nullptr로 설정합니다.
2번의 경우, 삭제노드 x의 부모노드 p의 x로 가는 경로를 x의 자식 노드로 설정합니다.
3번의 경우, 이진탐색트리를 중위순회 했을 때, 삭제 노드의 선행 노드 혹은 후속 노드 y를 삭제 노드 x에 복사 후, x의 왼쪽 혹은 오른쪽 서브트리에서 y를 삭제합니다. (선행노드를 선택했을 경우, 왼쪽 서브트리에서 삭제. 후속노드를 선택했을 경우, 오른쪽 서브트리에서 삭제합니다.)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
Node* deleteP(Node* p, int key) {
if(p == nullptr) return nullptr; //노드가 없는경우
if(key > p->data) { //삭제하고자 하는 값을 탐색.
p->right = deleteP(p->right, key);
return p;
}
if(key < p->data) {
p->left = deleteP(p->left, key);
return p;
}
if(p->left == nullptr) { //삭제하고자 하는 노드의 왼쪽 자식노드가 없을때. 오른쪽 자식노드를 리턴함. 이때, 둘 다 없다면, nullptr을 주게 되므로, 단말 노드인 경우와 서브트리 1개를 가지는 경우 둘다 가능
Node* t = p->right;
free(p);
return t;
}
if(p->right == nullptr) { //위 코드와 동일
Node* t = p->left;
free(p);
return t;
}
Node* next = p->right; //두개의 서브트리를 가지는 경우, 삭제하고자 하는 노드의 후속노드를 선택. (선행 노드를 선택해도 무관하나 이 코드에서 수정해야함)
while(next->left != nullptr) next = next->left; //오른쪽 서브트리에서 왼쪽으로 쭉 탐색. (삭제하고자 하는 노드보다 큰 노드 중 최소값)
p->data = next->data; //해당 키값을 삭제하고자 하는 노드에 복사
p->right = delete(p->right, next->data); //복사당한
return p;
}
|
cs |
이렇게 이진탐색트리의 정의와 연산에 대해서 소개해드렸습니다.
하지만 이 경우, 이진트리에서 큰 값만 삽입 하거나 작은값만 삽입할때, 이진탐색트리의 높이가 한쪽으로 치우쳐, 시간복잡도가 O(N)이 걸리게 됩니다. 따라서, 이진탐색트리에서 양쪽 서브트리의 균형을 맞춰주는 연산이 필요합니다.
그러므로, 다음 포스트에서는 AVL 트리에 대해서 포스트하도록 하겠습니다.
'Computer Science > 자료구조' 카테고리의 다른 글
우선순위 큐의 구현 (이진 힙) (1) | 2023.09.07 |
---|---|
균형 탐색 트리 (AVL)에 대하여 (0) | 2023.09.05 |
비선형 자료구조 (트리) (0) | 2023.08.29 |
연결리스트와 선형 자료구조 (2) (0) | 2023.08.24 |
연결리스트와 선형 자료구조 (1) (0) | 2023.08.01 |