+ 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다.
탐색 트리 문제의 정의
집합을 표현하는 자료 구조
- 문제를 풀기 위해서 수학의 집합의 개념을 이용할 수 있다.
(집합이란 어떤 답이 '있다', '없다'를 알 수 있어야 한다.)
- 집합을 어떻게 표현할 것인가?
집합에 대한 연산
1. membership query => O(n)
- 어떤 원소가 집합에 존재하는지를 판별할 수 있는 연산
2. insertion (삽입) => O(1)
- 배열 맨 뒤에 삽입
3. deletion (삭제) => O(n)
탐색 트리
레코드
= 개체에 대한 모든 정보를 묶은 저장 단위
ex) 주민등록번호, 이름
키
= 각 레코드를 대표할 수 있는 값
+ 정수로 가정한다. (같은 키를 같는 노드는 없다.)
탐색 트리
= 각 노드마다 하나의 키를 가지는 트리
+ 해당 레코드가 저장된 위치를 찾을 수 있다.
이진 탐색 트리
= 각 노드가 최대 두 개의 자식을 갖는 탐색 트리
+ 왼쪽 자식은 부모보다 키가 작고, 오른쪽 자식은 부모보다 키가 크다.
ex) {8, 3, 10, 1, 6, 14, 4, 7, 13}
서브 트리
= 특정 노드와 그 이하의 노드로만 이루어진 트리 (재귀적 구조)
이진 탐색 트리는 유일하지 않다.
1. 어떤 키 값이 자주 접근될지 모른다면, 균형잡힌 트리가 유리하다. (보통 유리)
=> n개의 노드가 존재할 때, 가장 낮은 높이(log n)의 이진 탐색 트리
높이: 루트부터 가장 먼 노드까지 edge의 개수
2. 어떤 키 값이 자주 접근될지 알 수 있다면, 균형이 잡히지 않은 트리가 유리하다.
ex) {1, 2, 3, 4}
이진 탐색 트리에서 검색
이진 탐색 트리에 원하는 값 k가 들어 있는가?
=> 재귀적으로 구현한다.
1. 트리가 비어 있다면 k는 트리에 있을 수 없다.
루트부터 아래 과정을 반복한다.
2 - 1. 만약 해당 값이 원하는 값 k라면, 해당 값을 반환한다.
2 - 2. 만약 해당 값이 k보다 크다면, 해당 값은 루트의 왼쪽 서브 트리에 존재한다.
2 - 3. 만약 해당 값이 k보다 작다면, 해당 값은 루트의 오른쪽 서브 트리에 존재한다.
이진 탐색 트리에서 삭제
삽입에 비해 삭제는 상대적으로 어렵다.
이진 탐색 트리에 한 키를 삽입하면 확실히 그 결과가 이진 탐색 트리이다.
but, 한 노드를 삭제하면, 그 결과가 이진 탐색 트리가 아닐 수도 있다.
< 이진 탐색 트리에서 가장 간단한 삭제 >
1. 이진 탐색 트리를 순회하면서 저장되어 있는 모든 값을 하나씩 읽는다.
2 - 1. 읽은 값이 삭제할 값이 아니라면, 새로운 이진 탐색 트리에 하나씩 삽입한다.
2 - 2. 읽은 값이 삭제할 값이라면, 건너뛴다.
=> 시간 복잡도, 공간 복잡도: O(n)
< 이진 탐색 트리에서 더 효율적인 삭제 >
삭제할 노드가 무엇인가에 따라서 세 가지 경우가 존재한다.
+ 최대한 트리의 모양을 바꾸지 않는 것이 좋다.
1. 삭제할 노드가 리프일 경우 (자식이 없다.)
=> 그냥 지우면 된다.
2. 삭제할 노드가 자식 하나인 경우
=> 노드를 지우고, 자식을 원래 노드의 위치로 옮긴다.
3. 삭제할 노드가 자식 둘인 경우
1. 노드의 키 값보다 바로 앞에 있거나, 바로 뒤에 있는 노드를 찾는다.
+ 바로 앞에 있는 노드: 삭제할 노드의 왼쪽 서브트리의 가장 오른쪽 노드
+ 바로 뒤에 있는 노드: 삭제할 노드의 오른쪽 서브트리의 가장 왼쪽 노드
2. 찾은 노드가 삭제할 노드의 위치로 오고, 다시 이 노드를 지우는 과정을 반복한다. (재귀: 1, 2번 경우)
+ 찾은 노드는 반드시 자식이 하나인 노드이다. 그렇지 않으면 삭제할 노드와 가장 가까운 노드가 아니다.
레드 블랙 트리 (Red Black Tree)
이진 탐색 트리의 경우, 한 쪽으로 노드들이 쏠릴 수 있다.
- 어떻게 하면 노드들이 자동으로 균형이 잡힐 것인가?
- 트리의 삽입, 삭제, 검색 연산은 모두 트리의 높이 h에 비례하는 시간이 걸린다.
=> h = O(log n)을 만족하도록 할 수 있는가?
< 레드 블랙 트리의 특성 >
=> 이진 탐색 트리에 추가적인 성질이 있다.
1. 각 노드는 Red 또는 Black 둘 중 한 가지 색을 갖는다.
2. 루트는 Black이다.
3. 노드의 색이 Red이면, 자식의 색이 Red일 수 없다.
+ 나머지 3가지 경우는 모두 가능하다.
4. 루트부터 NULL까지 모든 경로에서 만나는 Black 노드의 수는 항상 일정한다. (Black Height)
레드 블랙 트리에서 삽입
이진 탐색 트리에서 삽입과 동일하나, 색 때문에 추가적인 절차가 들어간다.
+ 검색은 색을 제외하고 이진 탐색 트리와 방법이 같다.
1. 일단, 새로 삽입된 노드는 Red이다. (default, 처음 삽입은 Black Node)
=> Black Height를 맞추는데 유리하다. (4번 조건을 위해)
2. 삽입된 노드의 부모의 색이 Red라면 2가지 경우로 나눠서 처리한다.
+ 삽입된 노드의 부모의 부모의 색은 무조건 Black이다.
2 - 1. 삽입된 노드의 부모의 부모의 두 자식 중 하나만 Red인 경우 (또는 자식이 하나인 경우)
=> 4가지 경우의 수 모두 1가지 경우의 수로 수정할 수 있다.
2 - 2. 삽입된 노드의 부모의 부모의 두 자식이 모두 Red인 경우
=> 색을 반전시키킨다.
+ Special Case: 만약 C가 루트라면, C를 Black으로 바꾼다. (규칙을 어기지 않는다.)
+ C의 부모가 Red라면, 다시 2 - 1 or 2 - 2 방법으로 해결한다.
< 시간 분석 >
루트에서 리프까지 거리 (Black Height)는 가장 긴 경우에도 가장 짧은 경우의 2배 이하이다.
+ 가장 짧은 경우: 모두 Black Node인 경우+ 가장 긴 경우: Black Node와 Red Node가 번갈아 있을 경우
트리의 노드 개수가 n일 때, Black Height를 bh라고 하면,
=> 4^bh - 1 (Black Height가 가장 긴 경우) ≥ n ≥ 2^bh - 1 (Black Height가 가장 짧은 경우)
=> 계산하면, log(n+1) ≥ bh ≥ (1 / 2) × log(n + 1)
트리의 높이 h는 bh ≤ h ≤ 2bh 이므로, 삽입, 탐색 모두 최대 2 × log(n + 1) 시간 내에 수행할 수 있다.
B - Tree
지금까지 데이터는 메인 메모리에 저장되어 O(1) 시간에 접근할 수 있다고 가정했다.
그러나, 실제 대용량 데이터는 HDD, SSD 등에 저장된다.
- SSD는 회전 문제는 없지만 상대적으로 메인 메모리에 비해 접근 속도가 느린 것은 동일하다.
Seek Time: 헤드를 원하는 데이터가 있는 섹터로 이동하는데 걸리는 시간
- 운이 좋으면, 현재 헤드 밑에 원하는 섹터가 있는 경우이다.
- 운이 나쁘면, 현재 헤드 바로 앞에 원하는 섹터가 있는 경우이다. (한 바퀴를 돌려야 한다.)
데이터를 블럭 단위로 저장한다.
+ 블럭 하나 당 100개의 키를 넣을 수 있다.
=> 한 번 데이터에 접근하는 시간이 많이 걸리고 어짜피 블럭 단위로 저장된다면, 노드에 많은 정보를 넣고, 트리의 높이를 줄이는 것이 좋다.
즉, HHD, SSD 등의 접근을 줄이는 균형 잡힌 다진 검색 트리인 B - Tree를 이용한다.
< B - Tree 특징 >
1. 한 노드에 하나 이상의 키 값이 들어올 수 있다.
- t개의 키 값이 저장되어 있다면, 이 노드의 자식은 t + 1개이다.
ex) {1, 2, 3} 노드의 자식: {-∞ ~ 1}, {1 ~ 2}, {2 ~ 3}, {3 ~ ∞}
2. 루트를 제외한 모든 노드는 k / 2 ~ k개의 키를 갖는다.
3. 모든 리프 노드는 루트에서부터 거리가 같다.
B - Tree에서 탐색과 삽입
한 노드에 둘 이상의 키가 저장될 수 있기 때문에 복잡하게 진행된다.
< 탐색 >
루트부터 아래 과정을 반복한다.
1 - 1. 찾고자 하는 키가 현재 노드에 포함되어 있다면 현재 노드가 답이다.
1 - 2. 포함되어 있지 않다면, 범위를 보고 다음에 방문할 노드를 결정한다,
- 한 노드가 최대 k개의 키를 저장하기 때문에 여러 값과 비교한다.
ex) 33은 25와 34 사이에 존재하므로 4번째 노드에 방문한다.
키가 저장될 노드를 찾았을 때,
1. 찾은 노드에 키를 저장할 수 있다면 저장한다.
2. 이미 k개의 키를 저장하고 있기 때문에 불가능하다면, 이 노드의 형제 노드에게 키를 넘길 수 있는지 확인한다.
3. 만약 형제 노드에게 키를 넘길 수 없다면, 중간 값을 기준으로 키들을 두 그룹으로 나누고 중간 값은 부모에게 전달한다.
4. 부모에게도 재귀적으로 진행한다.
ex) 한 노드에 키 값을 최소 2개, 최대 5개까지 저장할 수 있는 B - Tree의 삽입 예시
1) 31을 삽입한다.
- 31의 범위에 해당하는 노드안의 키 개수가 4개이므로 1개 더 삽입할 수 있다.
2) 5를 삽입한다.
- 5의 범위에 해당하는 노드안의 키 개수가 5개이므로 1개 더 삽입할 수 없다.
- 가까운 형제 노드의 키 개수를 확인한다. 3개이므로 형제 노드에 키 1개를 더 추가할 수 있다.
- 6이 바로 형제 노드로 이동한다면 B - Tree의 성질이 깨지므로, 6을 부모 노드로 이동시키고, 7을 형제 노드로 이동시킨다.
- 5를 범위에 해당하는 노드에 삽입한다.
3) 39를 삽입한다.
- 39의 범위에 해당하는 노드안의 키 개수가 5개이므로 1개 더 삽입할 수 없다.
- 가까운 형제 노드의 키 개수를 확인한다. 5개이므로 형제 노드에 키 1개를 더 추가할 수 없다.
- 범위에 해당하는 키를 두 그룹으로 나누고 중간값인 40을 부모에게 전달한다.
4) 32를 삽입한다.
- 32의 범위에 해당하는 노드안의 키 개수가 5개이므로 1개 더 삽입할 수 없다.
- 가까운 두 형제 노드 모두 키가 이미 5개이므로 형제 노드에 키 1개를 더 추가할 수 없다.
- 범위에 해당하는 키를 두 그룹으로 나누고 중간값인 31을 부모 노드로 전달한다.
- 그러나 부모 노드 역시 키가 이미 5개이므로 추가 과정이 필요하다.
- 루트 노드는 형제 노드가 없으므로, 형제 노드에 키를 추가 할 수 없다.
- 루트 노드의 키들을 두 그룹으로 나누고 중간 값인 31을 부모 노드로 전달한다.
(즉, 새로운 루트가 생성되고, 1개의 노드가 추가된다.)
B - Tree에서 삭제
삽입의 반대과정이다.
1. 지워질 키 값이 리프 노드로 이동한다.
1 - 1. 지워질 키가 속한 노드가 리프 노드라면 해당 노드에서 키 값을 제거한다.
1 - 2. 리프 노드가 아니라면, 지워질 키의 바로 다음 값이 저장된 리프 노드를 찾고 값을 서로 바꾼다.
+ 지워질 키 값이 리프 노드로 이동한다.
+ 지워질 키의 바로 다음 값: 지워질 키 값과 가장 가까운 값을 가진 키 값
2. 리프 노드에서 키 값을 제거한다.
2 - 1. 키 값을 제거했을 때, k / 2개 미만의 키가 남는다면, 키 값을 넘겨줄 수 있는 형제 노드를 찾는다.
2 - 2. 키 값을 넘겨줄 수 있는 형제 노드가 없다면, 형제 노드와 지워질 키 가 속한 리프 노드를 합병한다.
+ 노드를 합병하면 부모 노드의 키가 줄기 때문에 이 과정이 반복된다.
ex) 한 노드에 키 값을 최소 2개, 최대 5개까지 저장할 수 있는 B - Tree의 삭제 예시
1) 7을 삭제한다.
- 7이 해당한 노드가 리프 노드이고, 3개의 키 값을 갖고 있으므로 그냥 삭제해도 문제가 생기지 않는다.
2) 4를 삭제한다.
- 4가 있는 노드는 리프 노드가 아니므로 4를 삭제하기 위해 바로 다음 값인 5가 저장된 리프 노드를 찾고 5와 위치를 변경한다
- 위치를 변경한 리프 노드에서 4를 삭제한다.
- 각 노드는 최소 2개 이상의 키 값을 가져야 하므로 형제 노드에서 값을 하나 빌린다.
- 왼쪽에 있는 형제 노드가 3개의 키 값을 갖고 있으므로 그 중 가장 큰 키 값 3을 빌린다.
- 삽입과 마찬가지로, 3이 삭제한 노드로 이동한다면 B - Tree의 성질이 깨지므로, 3을 부모 노드로 이동시키고, 5를 삭제한 노드로 이동시킨다.
3) 9를 삭제한다.
- 각 노드는 최소 2개 이상의 키 값을 가져야 하므로 형제 노드에서 값을 하나 빌려야 한다.
- 그러나 두 형제 노드 역시 2개의 키 값을 갖고 있으므로 빌릴 수 없다.
- 삭제할 노드와 형제 노드 1개를 2개 이상의 키 값을 갖는 노드 하나로 병합한다.
- 그러나 이 과정에서 B - Tree의 조건을 만족하기 위해 부모 노드에 있는 키 값 한 개가 병합되어야 하고, 부모 노드의 키 값이 2개 미만이 된다.
- 다시 형제 노드, 부모 노드로 병합하여 4개의 키값을 갖는 1개의 노드를 생성한다.
Red - Black Tree 와 B - Tree의 관계
2-3-4 Tree: 한 노드에 최대 4개의 자식이 올 수 있는 B-Tree이다.
+ 키는 1개 or 2개 or 3개, 자식은 2개, 3개, 4개
Red - Black Tree는 2-3-4 Tree를 이진 트리로 표현한 것이다.
위 그림의 노드로 Red-Black Tree를 구성하면 Red-Black Tree의 조건을 모두 만족할 수 있다.
+ Red Node는 Black Node의 자식이므로 Black Node가 B - Tree의 Node 하나라고 생각하면, B - Tree를 Red - Black - Tree로 변환하더라도 B - Tree였던 Node를 구분할 수 있다.
'Study > Algorithm Study' 카테고리의 다른 글
| BIT (Binary Indexed Tree) (2) | 2024.04.03 |
|---|---|
| [Algorithm] 해시 테이블 (1) | 2023.11.12 |
| [Algorithm] 정렬: 계수 정렬, 선택 문제 (1) | 2023.10.05 |
| [Algorithm] 정렬: 버킷 정렬, 기수 정렬 (0) | 2023.09.24 |
| [Algorithm] 정렬: 힙 정렬 (1) | 2023.09.24 |
