이진탐색트리 BinarySearchTree에서 삭제(remove)의 경우는 3가지가 있다.
1. 삭제하려는 노드가 단말노드(터미널 노드)일 경우
2. 삭제하려는 노드가 왼쪽, 오른쪽 서브트리 중 한 방향만 가지고 있을 경우
3. 삭제하려는 노드가 왼쪽, 오른쪽 모두 서브트리를 가지고 있는 경우
### 1번 경우 ###
삭제하려는 노드가 단말노드일 경우 삭제하려는 노드의 부모노드(그림에서는 6)을 찾고 연결을 삭제하면 된다.
### 2번 경우 ###
삭제하려는 노드가 자신이 왼쪽, 오른쪽 중 한 방향으로만 서브트리를 갖는 노드일 경우 삭제할 노드(6번)을 삭제하고 그 노드의 서브트리를 부모노드에 붙인다.
### 3번 경우 ###
삭제하려는 노드(4번)이 왼쪽, 오른쪽 둘 방향 모두 서브트리를 가지고 있으면 삭제하려는 노드의 후계노드(5번)을 찾아서 후계노드의 값을 복사 받고, 후계노드와 부모노드 사이의 연결을 해제한 후 부모노드는 후계노드의 서브트리를 가르키게 (연결)한다.
후계노드를 찾는 방법은 삭제하려는 노드의 왼쪽 서브트리 중에서 제일 큰값을 고르거나 오른쪽 서브트리에서 제일 작은 값을 고른다. 이진탐색트리의 성질 (왼쪽 서브트리 < 루트(부모) < 오른쪽 서브트리) 때문에 삭제 연산이 자연스럽게 구현된다.
##### 코드 #####
parent : 삭제할 노드의 부모노드 >> 별도의 함수를 구현해서 parent 노드를 구한 후 매개변수로 입력
node : 삭제할 노드
### 1번 경우 ###
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
void remove(BinaryNode* parent, BinaryNode* node) {
if (node->isLeaf()) {
// 삭제할 노드가 단말노드일 경우
if (node == root) root = NULL;
// 삭제할 노드가 루트노드일 경우 root = NULL
else {
if (parent->getLeft() == node) parent->setLeft(NULL);
// 부모노드의 왼쪽에 삭제할 노드가 있다면 부모의 왼쪽을 NULL에 연결(왼쪽 삭제)
else
parent->setRight(NULL);
// 오른쪽에 있다면 부모의 오른쪽을 NULL에 연결(오른쪽 삭제)
}
}
|
cs |
### 2번 경우 ###
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
else if (node->getLeft() == NULL || node->getright() == NULL) {
// 삭제할 노드가 왼쪽, 오른쪽 둘 중 한 방향만 서브트리를 가지고 있는 경우
BinaryNode* chlid = (node->getLeft() != NULL) ? node->getLeft() : node->getright();
// 삭제할 노드의 자식노드(삭제할 노드의 위치로 들어갈 노드) 결정
// 삭제할 노드의 왼쪽이 NULL이 아니라면 왼쪽 노드가 자식노드
if (node == root) root = chlid;
// 삭제할 노드가 루트노드일 경우 루트 = child
else {
// 루트노드가 아닐 경우
if (parent->getLeft() == node) parent->setLeft(chlid);
// 부모노드의 왼쪽이 삭제할 노드라면 부모노드의 왼쪽을 chlid노드로 바꿈(왼쪽 삭제)
else
parent->setRight(chlid);
// 부모노드의 오른쪽이 삭제할 노드라면 부모노드의 오른쪽을 chlid노드로 바꿈(오른쪽 삭제)
}
}
|
cs |
### 3번 경우 ###
|
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
27
28
29
30
31
32
33
34
35
36
37
38
39
|
else {
// 삭제할 노드가 왼쪽, 오른쪽 두 방향 모두 서브트리를 가지고 있을 경우
BinaryNode* succp = node;
// succp : 후계노드의 부모노드, 삭제할 노드를 처음에 succp로 정한다.
BinaryNode* succ = node->getright();
// succ : 후계노드, 삭제할 노드의 오른쪽 노드를 처음에 후계노드로 정한다.
while (succ->getLeft() != NULL) {
// succ 의 왼쪽이 NULL이 아닐때까지(단말노드) while문 돌린다.
succp = succ;
succ = succ->getLeft();
// succ->getLeft()로 계속 왼쪽으로 NULL을 만날때 까지 탐색한다.
// 후계노드(오른쪽 서브트리중 가장 작은 값)을 찾기위한 방법
}
if (succp->getLeft() == succ) succp->setLeft(succ->getright());
// while문을 몇 번 수행이 된 경우(삭제할 노드 바로 오른쪽에 후계노드가 없었을 경우)
// 후계노드의 오른쪽 노드를 후계노드의 부모노드에 왼쪽에 연결시킨다.
else
// while문이 수행되지 않고 바로 넘어온 경우(삭제할 노드 바로 오른쪽에
// 후계노드가 있었을 경우)
succp->setRight(succ->getright());
// 후계노드의 부모노드(여기서는 삭제할 노드)의 오른쪽을 후계노드의
// 오른쪽 자식으로 연결시킨다.
node->setData(succ->getData());
// 삭제할노드의 데이터를 후계노드의 데이터로 초기화시킨다.
node = succ;
// 메모리 해제를 위함.
}
delete node;
// 삭제할 노드 메모리 해제
}
|
cs |
'자료구조' 카테고리의 다른 글
| [자료구조] 그래프 (0) | 2022.12.03 |
|---|---|
| [자료구조] 우선순위 큐, Heap (2) | 2022.11.30 |
| [자료구조] 이진탐색트리, BinarySearhTree 개념, 탐색, 삽입 (0) | 2022.11.15 |
| [자료구조] 수식 트리 (0) | 2022.11.11 |
| [자료구조] 이진트리 연산 (0) | 2022.11.11 |