* 해당 포스트는 PC환경에 최적화 되어있습니다.
* 쉽게 배우는 알고리즘 개정판 교재로 공부했으며 학교에서 배운 내용과 섞어서 정리한 포스트입니다.
* 저작권 문제는 hjl3066@gmail.com으로 연락주시면 빠르게 조치하겠습니다.
- 이진 검색 트리 : 최대 2개의 자식 노드
- 다진 검색 트리 : 3개 이상의 자식 노드로 분기
- 일차원 검색 트리 : 검색키가 포함하는 필드가 하나
ex) 이진 검색, 다진 검색, B-트리, AVL-트리, 레드블랙트리, ... - 다차원 검색 트리 : 검색키가 포함하는 필드가 2개 이상
ex) KD 트리, KDB 트리, R-트리
이진 검색 트리
- 특징
① 모든 노드는 키 값이 존재, 각 노드의 키 값은 다르다.
② 최상위 레벨에 루트 노드, 각 노드는 최대 2개의 자식을 가짐.
③ 임의의 노드 키 값은 자신의 왼쪽 자식 노드의 키 값보다 크고,
자신의 오른쪽 자식 노드의 키 값보다 작다.
- 서브 트리
루트 노드 r을 기준으로 왼쪽 서브트리와 오른쪽 서브트리로 나뉜다.(아래 그림 참고)
이진 검색 트리의 검색 의사 코드
treeSearch(t, x) {
if (t = None or key[t]=x)
return t;
if (x < key[t]) //키 값이 작다.
return treeSearch(left[t], x);
else //키 값이 크다.
return treeSearch(right[t], x);
}treeSearch(t, x)에서 t는 트리의 루트 노드(r)이다. x는 검색할 키이다. (ex. 25)
return treeSearch로 재귀하여 검색한다.
검색 시간은 O(log n)이다.
이진 검색 트리의 삽입
1. 새로운 노드 r
2. 30을 루트 노드로, 삽입할 키 20이 루트 노드보다 작으므로 좌측 노드에 삽입
3. 루트 노드 30으로 설정, 자식 노드 20이 존재하므로 자식 노드 20을 루트 노드로 설정,
루트 노드 20이 삽입할 노드보다 작으므로 우측에 삽입
4. 루트 노드 30, 삽입할 키가 40으로 루트 노드보다 크므로 우측 노드에 삽입
5. 루트 노드 30, 삽입할 키인 10이 루트 노드보다 작으므로 좌측으로 이동,
좌측에 노드가 있으므로 루트 노드를 20으로 설정, 루트 노드가 삽입할 키보다 크므로 좌측으로 삽입
6. 설명 생략.
이진 검색 트리의 삽입 의사 코드
treeInsert(t, x) {
if (t = None) { // x를 키로 하는 노드를 t의 부모 밑에 매달고 return
key[r] ← x;
left[r] ← NIL;
right[r] ← NIL; // r : 새 노드
return r ;
}
if (x < key(t)) {
left[t] ← treeInsert(left[t], x);
return t;
}
else {
right[t] ← treeInsert(right[t], x);
return t;
}
}코드 진행이 앞서 설명한 것과 유사하므로 생략.
앞서 설명한 검색과 삽입은 간단하고 이해하기도 쉽다.
다만, 삭제는 약간 복잡할 수 있다.
삭제는 3가지의 경우로 나누어 진행된다.
이진 검색 트리의 삭제
이진 검색 트리에서 노드 r을 삭제하고자 할 때 다음 3가지 경우가 있다.
Case 1. r이 리프 노드인 경우 (가장 끝에 있는 노드)
Case 2. r의 자식 노드가 하나인 경우
Case 3. r의 자식 노드가 두 개인 경우 ← 복잡하다.
Case 1. r이 리프 노드인 경우
1. 이진 검색 트리의 검색을 먼저 진행한다.
삭제하고자 하는 노드 r이 자식이 없는 리프 노드라는 것을 알아냈다.
2. 해당 노드 r의 부모 노드인 28의 좌측 노드를 None으로 설정하여 노드 r을 삭제한다.
Case 2. r의 자식 노드가 하나인 경우
1. 이진 검색 트리의 검색을 먼저 진행한다.
삭제하고자 하는 노드 r의 자식이 하나라는 것을 알아냈다.
2. 해당 노드의 부모 노드인 28의 우측 노드를 None으로 설정하여 노드 r을 삭제한다.
3. 삭제한 노드 r의 자식 노드를 r의 자리에 놓는다.
(r의 부모 노드에서 r을 가리키고 있던 포인터를 r의 자식을 가리키도록 설정하면 된다.)
Case 3. r의 자식 노드가 두 개인 경우
Case 3를 진행하면서 생각할 것.
- r을 제거하면 r의 자식들과의 연결이 끊어짐
- r의 자식이 둘이므로 Case 2와 같이 할 수 없음
- r 주변의 구조는 유지해야함. r 자리에 옮겨 놓아도 이진 검색 트리의 성질을 깨지 않는 원소를 찾아야함
- 여기서 Case 3를 수행하는 방법이 나뉨. 여기서는 r의 직후 원소를 건드리는 방법을 사용함.
(직전 원소를 건드는 방법도 있음)
1. 삭제하고자 하는 노드 r의 직후 원소 s를 찾는다.
2. 노드 r을 삭제한다.
3. 직후 원소 s를 삭제한 노드 r의 자리와 바꾼다.
4. 자리가 빈 직후 원소 s의 부모 노드에 직후 원소의 자식을 연결한다.
이진 검색 트리의 삭제 의사 코드
treeDelete(t, r, p) { // t: 루트 노드, r: 삭제하려는 노드, p: r의 부모 노드
if (r = t)
root ← deleteNode(t); // r이 루트 노드인 경우
else if (r = left[p]) // r이 루트가 아닌 경우
left[p] ← deleteNode(r); // r이 p의 왼쪽 자식
else right[p] ← deleteNode(r); // r이 p의 오른쪽 자식
}
deleteNode(r) {
if (left[r] = right[r] = None)
return NIL; // Case 1
else if (left[r] = None and right[r] ≠ None)
return right[r]; // Case 2-1
else if (left[r] ≠ None and right[r] = None)
return left[r]; // Case 2-2
else { // Case 3
s ← right[r]; // 직후 원소 s
while (left[s] ≠ None) { // 직후 원소 찾기
parent ← s;
s ← left[s];
}
key[r] ← key[s];
if (s = right[r])
right[r] ← right[s];
else
left[parent] ← right[s];
return r;
}
}deleteNode의 if문으로 Case 1, 2, 3을 나누어 진행된다.
'공부 > 알고리즘' 카테고리의 다른 글
| 03. 점화식과 점근적 복잡도 분석 (0) | 2023.01.11 |
|---|---|
| 02. 알고리즘 설계와 분석 2 - 점근적 표기법 (0) | 2023.01.06 |
| 02. 알고리즘 설계와 분석 1 - 알고리즘의 분석 (0) | 2023.01.06 |
| 01. 알고리즘이란? (0) | 2023.01.05 |
| 06. 검색 트리 - 레드 블랙 트리(RB Tree) (0) | 2022.12.20 |
