|
'''
이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' |
|||||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" |
<colbgcolor=#aa3366> 이론 | ||||
| 기본 대상 | 수학기초론{ 수리논리학( 논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학( 그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 기계 · 람다 대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신( 폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^ 고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임( 그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축( 무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어( 함수형 언어 · 객체 지향 프로그래밍) · 메타 프로그래밍 · 형식언어 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^ 벡터^ · 리스트^ 연결 리스트^ · 셋(set)^ 레드-블랙 트리, B-트리^ · 우선순위 큐^ 힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시( MD5 · 암호화폐 · 사전 공격( 레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘( AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘( 타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^ BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제 대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
1. 개요
Red-black tree(위키백과)레드-블랙 트리는 자가 균형 이진 탐색 트리의 일종으로, 노드가 블랙 또는 레드의 색깔을 갖는 트리이다.
삽입과 삭제 시 경우에 따라 노드의 색 변환 또는 트리 회전[1]이 필요하며 구현은 꽤나 복잡하지만 실 사용에선 매우 효율적인 모습을 보인다. C++ STL의 set, map이 이 레드블랙 트리를 이용하여 구현되었다.[2]
또한 2-3-4 트리와 매우 유사하며 모든 레드-블랙 트리는 일대일 대응하는 2-3-4 트리가 있다( 역도 참이다). 2-3-4 트리에는 노드 하나에 1~3개의 데이터가 들어간다. 이 중 가운데의 데이터를 검은색으로, 좌, 우의 데이터를 붉은색으로 표기하면 레드-블랙 트리와 같아진다.
2. 특성
구현의 용이성을 위해 자식이 없는 곳에는 가상의 블랙 NIL 노드가 있다고 생각한다. 따라서 모든 리프 노드의 자리에는 NIL이 위치하고 있다.트리가 균형을 유지하도록 하기 위해서 이진 탐색 트리에 다음의 제약 조건이 추가되었다.
- 모든 노드는 레드 아니면 블랙이다.
- 루트 노드는 블랙이다.
- 모든 NIL 노드는 블랙이다.
- 레드 노드는 레드 노드를 자식으로 가질 수 없다. 따라서...
- 모든 레드 노드의 부모는 블랙이다.
- 레드 노드는 연속으로 존재(Double red)할 수 없다.
- 임의의 한 노드에서 NIL 노드까지 도달하는 모든 경로에는 항상 같은 수의 블랙 노드가 있다.
조건 4와 5에 따라서, 어떤 트리에서 루트로부터 리프까지 가는 경로 중 가장 짧은 것은 블랙 노드가 [math(N)]개 있는 것이고, 가장 긴 것은 [math(N)]개의 블랙 노드 사이사이에 레드 노드가 있는 것(블랙-레드-블랙-...-블랙)으로 [math(2N-1)]이다. 따라서 가장 긴 경로가 가장 짧은 경로의 2배를 넘지 않는다. 이러한 성질에 대해 개략적으로 균형이 잡혀 있다고 표현한다.
3. 시간 복잡도
삽입, 탐색, 삭제 모두 최악의 경우 [math(O(\log N))]의 시간 복잡도를 갖는다.기존 이진 탐색 트리가 삽입과 삭제에서 최악의 경우 [math(O(N))]의 시간 복잡도를 갖는 것을 보완하기 위해 AVL 트리가 만들어지고, 그 AVL 트리를 더 보완하기 위해 레드-블랙 트리가 개발되었다.
4. 삽입
새 노드(N)을 레드로 칠하고, 일반적인 이진 탐색 트리에 삽입하는 과정을 따라 리프 위치에 삽입한다.이때 N의 부모가 레드이면 레드 노드가 연속으로 존재할 수 없다는 제약 조건을 위반하게 되므로, 이를 해결하는 과정이 필요하다.
주변 노드의 색상에 따라 다른 과정을 수행한다.
4.1. N이 루트
N이 루트 노드인 경우이다.조건 2[A]를 만족시키기 위해 N을 검은색으로 칠한다.
N이 루트 노드이므로 루트로부터 리프 노드까지의 모든 경로에 블랙 노드가 하나 추가되어, 조건 5[B]가 유지된다. 종료한다.
4.2. N의 부모가 블랙
부모가 레드가 아니므로 레드가 연속으로 존재할 수 없다는 조건을 위반하지 않는다. 종료한다.4.3. N의 부모가 레드
N의 부모 노드의 형제를 삼촌 노드라고 하자. 삼촌 노드의 색에 따라 다른 과정을 거친다.4.3.1. N의 삼촌이 레드
N의 부모가 레드이므로 N의 조부모는 블랙이다.N의 부모와 삼촌을 블랙으로 바꾸고, 조부모를 레드로 바꾼다. 이때 N의 조부모에서 리프로 가는 모든 경로의 블랙 노드 수는 변하지 않는다.
N의 조부모가 블랙에서 레드가 되었으므로 트리 조건을 위반할 가능성이 있다. 따라서 조부모에 대해 해결 과정을 다시 시작한다.
4.3.2. N의 삼촌이 블랙
4.3.2.1. N이 안쪽 자손임
N이 안쪽 자손이란 말은, 부모 P가 조부모의 왼쪽(오른쪽) 자식이고, N이 P의 오른쪽(왼쪽) 자식이라는 것을 의미한다. 이때 P를 기준으로 왼쪽(오른쪽) 회전을 하면 P가 조부모의 바깥쪽 자손이 된다. 그러면 바깥쪽 자손이 된 P를 N으로 설정하고 다음 과정을 진행한다.4.3.2.2. N이 바깥쪽 자손임
N이 왼쪽(오른쪽) 바깥쪽 자손이라고 하자. N의 부모를 블랙, 조부모를 레드로 칠하고, 조부모를 기준으로 오른쪽(왼쪽) 회전을 한다. 연산을 완료했을 때 N의 부모에서 리프로 가는 모든 경로의 블랙 노드 수는 변하지 않는다. 회전으로 인해 조부모의 위치를 대신한 부모가 블랙이므로 레드가 연속으로 존재할 수 없다는 조건을 위반하지 않는다. 종료한다.5. 삭제
[1]
최대 3회
[2]
언어 자체에서 연관 배열(associative array)을 지원하는 경우 대부분 레드블랙 트리로 구현되어 있다.
[A]
루트 노드는 블랙이다.
[B]
어떤 노드에서 리프 노드까지의 모든 경로에는 같은 수의 블랙 노드가 있다.