레드 블랙 트리

레드 블랙 트리

트리의 높이가 커지면 커질 수록 검색 속도가 느려진다. (=연결리스트와 비슷)

트리가 균형을 이루도록 고안된 검색 트리 구조

최악의 경우 O($log_n$)

이진탐색트리

루트를 기준으로 왼쪽은 작은 값, 오른쪽은 큰 값이 오는 트리 구조의 자료구조

레드 블랙 트리 특성

1. 각 노드당 추가 기억 공간을 가짐 (노드의 색깔)
2. 루트에서 리프까지 경로의 나타나는 노드의 색깔을 제한함
3. 트리의 필드: color, key, left, right, p
4. 한 노드의 자식 또는 부모가 존재하지 않으면 NIL 값으로 채워진다.

NIL

c언어의 NULL과 다르게 실제 노드의 포인터이다.

typedef struct Node {
    int key;
    char color; // 'R' or 'B'
    struct Node *left, *right, *parent;
} Node;

Node sentinel = {0, 'B', NULL, NULL, NULL}; // 전역 NIL 노드
Node *NIL = &sentinel;

// 사용 예
Node *root = NIL;  // root 초기값

T.nil

• 싱글톤 방식
• 경계 노드

레드 블랙 트리 핵심적 특성

1. 모든 노드는 레드이거나 블랙이다
2. 루트는 블랙이다
3. 모든 리프(NIL)는 블랙이다
4. 노드가 레드이면 그 노드의 자식은 모두 블랙이다 (=노드 레드가 연속적일 수 없다)
5. 각 노드로부터 그 노드의 자손인 리프로 가능 경로들은 모두 같은 수의 블랙 노드를 포함한다. (자기자신을 제외한 모든 경로의 리프노드(NIL 포함) 블랙 노드의 개수가 같다)

• RB트리가 5번 속성을 만족하고 있고 두 자녀가 가튼 색을 가질 때 부모와 두 자녀의 색을 바꿔줘도 5번 속성은 여전히 만족한다.

레드 블랙 트리에서 관심 대상은 키값을 가지는 내부 노드이다.

블랙 높이 (black height)

• 한 노드 $x$에서 리프까지의 경로에 있는 모든 블랙 노드의 개수 = bh($x$)
• 레드 블랙 트리 핵심적 특성 5번 속성을 만족해야함

회전

트리 내의 일부 노드들의 색깔과 포인터를 변경해야한다.

포인터를 변경하기 위해 회전을 사용한다.

1. 좌회전
2. 우회전

삽입

1. case1: 부모노드와 삼촌노드가 RED노드 일 경우
   1. 부모노드와 삼촌노드의 색깔을 Black으로 변경 후 조상의 색깔을 RED로 변경
2. case2: 꺽여있는 경우
   1. 왼쪽으로 꺽여있는 경우 - 우회전 후 좌회전
   2. 오른쪽으로 꺽여있는 경우 - 좌회전 후 우회전
3. case3: 일직선상인 경우
   1. 왼쪽 일직선상인 경우 - 우회전
   2. 오른쪽 일직선상인 경우 - 좌회전