mir.pe (일반/어두운 화면)
최근 수정 시각 : 2024-09-25 16:00:07

레드-블랙 트리


''' 이론 컴퓨터 과학
{{{#!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=#a36> 이론
기본 대상 수학기초론{ 수리논리학( 논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학( 그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학
다루는 대상과 주요 토픽
계산 가능성 이론 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버
오토마타 이론 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. 개요2. 특성3. 시간 복잡도4. 삽입
4.1. N이 루트4.2. N의 부모가 블랙4.3. N의 부모가 레드
4.3.1. N의 삼촌이 레드4.3.2. N의 삼촌이 블랙
4.3.2.1. N이 안쪽 자손임4.3.2.2. N이 바깥쪽 자손임
5. 삭제

1. 개요

Red-black tree(위키백과)

레드-블랙 트리는 자가 균형 이진 탐색 트리로, 각 노드가 블랙 또는 레드의 색상을 갖는다. 자가 균형 특성 덕분에 탐색, 삽입, 삭제 등의 연산이 효율적으로 이루어지며, 이로 인해 많은 프로그래밍 언어의 라이브러리에서 활용된다. 예를 들어, C++의 set, map뿐만 아니라 Java의 TreeMap, TreeSet 등도 레드-블랙 트리를 기반으로 한다.

삽입과 삭제 시 경우에 따라 노드의 색 변환 또는 트리 회전[1]이 필요하며 구현은 꽤나 복잡하지만, 실사용에서 매우 효율적인 모습을 보인다. 대부분의 프로그래밍 언어가 연관 배열(associative array)을 지원하는 경우, 이를 레드-블랙 트리로 구현하는 것이 일반적이다.

레드-블랙 트리는 2-3-4 트리와 매우 유사하며, 모든 레드-블랙 트리는 일대일 대응하는 2-3-4 트리가 있다( 역도 참이다). 2-3-4 트리에서 하나의 노드는 1~3개의 데이터를 가질 수 있으며, 이를 레드-블랙 트리로 변환할 때는 가운데 데이터를 블랙으로, 양옆 데이터를 레드로 표기하게 된다.

2. 특성

레드-블랙 트리에서는 자식이 없는 모든 노드의 위치에 블랙 NIL 노드를 명시적으로 추가하여 트리의 균형을 유지한다. 트리가 균형을 유지하도록 하기 위해 이진 탐색 트리에 다음의 제약 조건이 추가되었다:
  1. 모든 노드는 레드 아니면 블랙이다.
  2. 루트 노드는 블랙이다.
  3. 모든 NIL 노드는 블랙이다.
  4. 레드 노드는 레드 노드를 자식으로 가질 수 없다. 따라서...

      5. - 모든 레드 노드의 부모는 블랙이다.
      - 레드 노드는 연속으로 존재할 수 없다(Double red).
  5. 임의의 한 노드에서 NIL 노드까지 도달하는 모든 경로에는 항상 같은 수의 블랙 노드가 있다.
조건 4와 5에 따라서, 어떤 트리에서 루트로부터 리프까지 가는 경로 중 가장 짧은 경로는 블랙 노드가 [math(N)]개인 경로이며, 가장 긴 경로는 [math(N)]개의 블랙 노드 사이사이에 레드 노드가 있는 경로(블랙-레드-블랙-...-블랙)로 [math(2N-1)]개의 노드로 구성된다. 따라서 가장 긴 경로가 가장 짧은 경로의 2배를 넘지 않는다. 이러한 성질 덕분에 레드-블랙 트리는 균형을 유지한다고 말할 수 있다.

3. 시간 복잡도

삽입, 탐색, 삭제 모두 최악의 경우 [math(O(\log N))]의 시간 복잡도를 갖는다. 기존 이진 탐색 트리가 삽입과 삭제에서 최악의 경우 [math(O(N))]의 시간 복잡도를 갖는 것을 보완하기 위해 AVL 트리가 만들어졌고, AVL 트리를 더 보완하여 레드-블랙 트리가 개발되었다.

레드-블랙 트리는 삽입과 삭제 시의 균형을 맞추기 위한 연산의 수가 AVL 트리에 비해 적기 때문에, 삽입과 삭제 연산이 빈번한 환경에서 더 적합하다. 반면 AVL 트리는 더 엄격하게 균형을 유지하기 때문에 탐색 성능이 조금 더 우수하다.

4. 삽입

새 노드(N)를 레드로 설정한 후, 이진 탐색 트리 규칙에 따라 리프 위치에 삽입한다. 이때 삽입된 노드의 부모가 레드이면 레드 노드가 연속으로 존재할 수 없다는 제약 조건을 위반하게 되므로, 이를 해결하는 추가 작업이 필요하다. 주변 노드의 색상에 따라 다른 과정을 수행한다.

4.1. N이 루트

N이 루트 노드라면 조건 2[2]를 만족시키기 위해 N을 블랙으로 칠한다. N이 루트 노드이므로 루트에서 리프까지의 경로에 블랙 노드가 하나 추가되며, 조건 5[3]도 유지된다. 이 경우 작업은 종료된다.

4.2. N의 부모가 블랙

N의 부모가 블랙이므로 레드 노드가 연속으로 존재할 수 없다는 조건을 위반하지 않는다. 따라서 별도의 작업 없이 삽입을 종료한다.

4.3. N의 부모가 레드

N의 부모 노드의 형제를 삼촌 노드라고 하자. 삼촌 노드의 색에 따라 다른 과정을 수행한다.

4.3.1. N의 삼촌이 레드

N의 부모와 삼촌이 모두 레드라면, 조부모는 블랙이다. N의 부모와 삼촌을 블랙으로 변경하고, 조부모를 레드로 바꾼다. 이때 N의 조부모에서 리프로 가는 모든 경로의 블랙 노드 수는 변하지 않는다. 그러나 조부모가 레드로 변했기 때문에 조건 위반 가능성이 생겨, 조부모에 대해 해결 과정을 다시 시작한다.

4.3.2. N의 삼촌이 블랙

삼촌이 블랙인 경우에는 N이 부모의 안쪽 자손인지, 바깥쪽 자손인지에 따라 처리가 달라진다.
4.3.2.1. N이 안쪽 자손임
N이 부모의 안쪽 자손이라면(부모가 조부모의 왼쪽 자식이고 N이 부모의 오른쪽 자식인 경우 등), 부모를 기준으로 회전하여 N을 바깥쪽 자손으로 만든다. 이후 N의 부모를 기준으로 처리한다.
4.3.2.2. N이 바깥쪽 자손임
N이 부모의 바깥쪽 자손이라면, N의 부모를 블랙으로, 조부모를 레드로 설정하고, 조부모를 기준으로 회전을 수행한다. 이로써 트리의 균형이 유지되고, 연속된 레드 노드가 없도록 조정된다.

5. 삭제

레드-블랙 트리에서 노드를 삭제할 때는 이진 탐색 트리와 동일하게 처리하지만, 삭제 후 트리의 균형을 유지하기 위한 추가 작업이 필요하다. 특히, 삭제된 노드가 블랙일 경우, 트리의 색상 규칙을 위반하게 될 가능성이 있기 때문에 다양한 경우에 맞춰 처리해야 한다.
  1. 삭제된 노드가 레드인 경우, 단순 삭제로 충분하다.
  2. 삭제된 노드가 블랙인 경우, 형제 노드와 부모 노드의 색상 조정과 회전 작업을 통해 균형을 회복시켜야 한다. 형제 노드의 색상이 레드인지 블랙인지에 따라 다르게 처리하며, 이 과정은 트리의 다른 노드에도 영향을 미칠 수 있다.
[1] 최대 3회 [2] 루트 노드는 블랙이다. [3] 어떤 노드에서 리프 노드까지의 모든 경로에는 같은 수의 블랙 노드가 있다.

분류