[자료구조] 레드-블랙 트리(Red-Black Tree)란?

✅자료구조와 트리(Tree)란?

자료구조란?

CS에서 데이터를 다룰 때 접근과 수정을 조금 더 효과적으로 할 수 있는 함수, 혹은 명령을 뜻한다. 

Array, Stack, Queue, List etc..

우리가 쓰는 모든 소프트웨어는 알고리즘과 자료구조로 이루어져 있고, 자료구조의 아래항목을 파악하고 있어야 한다.

• 정의
• 어떻게 구현할지
• 사용처
• 탐색 알고리즘

 

 

트리(Tree)란?

그래프를 기반으로 방향성이 존재하는 비순환 자료구조 중 하나이다. 가계도와 같은 계층적인 구조를 표현할 때 사용된다.

일반적인 트리 구조에서는 삽입할 데이터 n이 있을 때 부모 노드부터 탐색하면서 삽입한 데이터보다 n이 해당 노드보다 작으면 왼쪽 노드에, 해당 노드보다 크면 오른쪽 노드에 저장한다.

ex) RDBMS에서 인덱스의 알고리즘이 B+Tree

 

트리

 

 

트리관련용어

• 루트 노드(root node): 부모가 없는 최상위 노드(A)
• 단말 노드(leaf node): 자식이 없는 노드 (H, I, E, G, J)
• 크기(size): 트리에 포함된 모든 노드의 개수 
• 깊이(depth): 루트 노드로부터의 거리
• 높이(height): 깊이 중 최댓값
• 차수(degree): 각 노드의 간선 개수 (A에서 B와 C로 나눠지니까 A의 차수는 2가 되며, E에서는 단말 노드이므로 차수는0), 기본적으로 트리의 크기가 N일때 전체 간선의 개수는 N-1개 

 

✅레드-블랙 트리(Red-Black Tree)란?

*NIL: 리프노드

---

자가균형이진탐색트리 (Self-Balancing Binary Search Tree)

이진탐색트리는 효율적인 검색을 위해 데이터를 정렬된 상태로 저장하는 자료구조이나, 데이터의 삽입, 삭제 과정에서 트리의 균형이 꺠지면 탐색 기능이 저하될 수 있다. 레드 블랙 트리는 이러한 문제를 해결하기 위해 고안된 자료구조.

 

레드-블랙트리(Red-Black Tree)의 조건?

1. 모든 노드는 red 혹은 black

2. 루트 노드는 black

3. 모든 nil(leaf)노드는 black

4. red의 자녀들은 black == red가 연속적으로 존재할 수 없다. 

5. 각 노드에서 자손 nil 노드들 까지 가는 경로들의 black 수는 같다. (자기 자신은 카운트에서 제외)

ex) 25에서 nil까지 가는 경로는 4개이고 black노드 갯수는 2, 마찬가지로 13에서 모든 nil지 가는 경로는 11개지만 black 노드 갯수는 모두 2, 즉 13의 blacke hight, bh(13)=2 이다. 같은 원리로 bh(17)=2. 

---

 

 

 

**노드 x의 black height, 노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서의 black수

**NIL 노드란? 

레드블랙 트리에만 존재하는 특수한 노드 

• 1. 존재하지 않음을 의미하는 노드 (1번 노드의 왼쪽은 자녀가 없다)
• 2. 자녀가 없을때 자녀를 nil 노드로 표기
• 3. 값이 있는 노드와 동등하게 취급
• 4. RB트리에서 leaf노드(자녀가 없는 노드) = nil 노드

**레드-블랙트리의 속성과 삽입, 삭제 등 참고한 강의

 

 

✅레드블랙 트리를 사용하는 이유?

위 조건들을 만족하게 되면, 레드블랙 트리는 가장 중요한 특성을 나타내게 된다. 루트 노드부터 가장 먼 경로까지의 거리가, 가장 가까운 경로까지의 거리의 두 배보다 항상 작다. 다시 말해 레드블랙 트리는 개략적으로 균형이 잡혀있다. 따라서, 삽입, 삭제, 검색 시 최악의 경우(worst-case)에서의 시간복잡도가 트리의 높이(깊이)에 따라 결정되기 때문에 보통의 이진검색 트리에 비해 효율적이다.

 

예시)

일반적인 트리구조에서는 삽입할 데이터 n이 있을때 부모 노드부터 탐색하면서,

삽입한 데이터보다 n이 해당 노드보다 작으면 왼쪽 노드에, 크면 오른쪽 노드에 저장한다. 

그럼 데이터 1,2,4,8이 저장되면 어떻게 될까?

 

위와 같이 편향 이진트리가 되며 배열로 표현시 공간도 많이 소모될 뿐만 아니라 탐색하는데 시간 복잡도 O(n)이 소모된다. 

 

이러한 현상을 막으려면 중간중간에 재배열을 해서 위와같이 시간 복잡도가 O(log n)인 균형 이진트리로 만들어줘야한다. 

스스로 재배열을 해서 균형 이진 트리 형태를 유지하는 자료구조를 자가 균형 이진트리 라고 한다. 

 

즉 레드-블랙 트리는 자가 균형 이진트리의 일종!

 

**대체 O(log n)이 뭔데..?

O(log n): 로그 시간 복잡도,  입력크기가 증가할 수록 실행 시간이 상대적으로 느리게 증가한다. 매우 효율적이며, 대부분의 경우 많은 데이터에 대해 빠른 실행 시간을 제공한다.

O(1): 상수 시간 복잡도, 입력 크기에 상관없이 항상 일정한 실행 시간을 갖는다. 즉, 알고리즘의 실행 시간이 입력크기에 무관하다. 

O(n): 선형 시간 복잡도, 입력 크기에 비례하여 실행 시간이 선형적으로 증가함, 즉 입력 크기가 2배로 증가하면 실행 시간도 2배(배열의 모든 요소를 순회하며 처리하는 경우 O(n)시간이 걸린다)

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/

[알고리즘] Time Complexity (시간 복잡도) - 하나몬

 

✅레드블랙 트리 구현 예시

1. Red Black Tree Animation

2. 균형을 유지하기 위해 두가지 연산인 Restructuring, Recoloring이 사용된다.

루트 노드가 있다.

노드를 두 개 삽입하면 위의 상태가 된다. (삽입되는 노드는 무조건 Red이다.)

여기서 3을 삽입해보자.

이러면 위의 3번 조건에 어긋나게 된다. (빨간색 노드의 자식이 빨간색

위와 같이 삽입, 삭제로 인해서 위의 조건에서 어긋날 때 아래의 과정 중 하나를 거친다.

• Restructuring
• Recoloring

각 과정을 선택하는 기준은 이러하다.

• 3을 기준으로 볼 때 2(부모의 형제)가 검정(Black)일 땐 Restructuring을 수행한다.
• 3를 기준으로 볼 때 2(부모의 형제)가 빨강(Red)일 땐 Recoloring을 수행한다.

 

 

Restructuring

한쪽으로 데이터가 쏠리지 않게 재정렬 하는 작업이라고 생각하면 쉽다.

"두 개의 연속된 레드노드"를 해결하기 위한 연산. 

 

1. 리프 노드의 부모와 조부를 재정렬한 후
2. 부모 노드를 검정(Black)으로 만들고 자식을 Red로 만든다.
3. 기존의 자식을 추가해주면 된다.

Restructuring은 수행 전과 수행 후 Black Depth가 동일하므로 다른 서브트리에 영향을 끼치지 않는다.

Restructuring은 O(1)의 시간복잡도를 가진다.

 

Recoloring

Recoloring은 노드의 배치는 그대로 두고 색상만 변경해서 위배한 조건을 만족할 수 있도록 처리되는 작업이다.

"두 개의 레드노드의 자식이 레드인 경우"를 해결하기 위한 연산

 

Recoloring은 다음의 과정을 수행한다.

• 부모와 그 형제를 검정(Black)으로 하고, 조부모를 빨강(Red)로 한다.
• (조부모가 Root가 아닐 시 3번 조건을 불만족할 수 있다.)

이때 변경된 트리가 서브트리라면 조부모 노드가 빨간색이므로 3번 조건에 또 위배될 가능성이 있다.

그때는 조건을 만족할 때까지 거슬러 올라가면서 Recoloring을 수행하게 된다.

 

(운이 안좋으면 루트까지 올라간다.)

서브 트리의 조부모 노드가 루트 노드라면 블랙(Black)으로 바꿔주면 된다.

Recoloring은 시간 복잡도 O(log N)을 가진다.

✅레드-블랙트리(Red-Black Tree)의 장/단점?

장점

• 구현하기가 쉽다
• 트리의 높이가 대수가 되도록 보장하여 효율적인 작업을 보장한다. (속성 5)
• 최악의 경우에도 우수한 성능을 나타낸다. 
• 자체 균형 속성은 루트에서 리프까지의 경로가 다른 경로보다 훨씬 길지 않도록 보장한다.

단점

• 다른 데이터 구조보다 복잡하다. 
• 트리에서 최소 또는 최대 요소 찾기와 같은 특정 작업의 경우 다른 데이터 구조보다 느릴 수 있다.

 

결론

레드-블랙 트리는 효율적인 맵 또는 집합 데이터 구조 구현, 데이터베이스의 인덱싱, 효율적인 조회 및 저장을 위한 일부 프로그래밍 언어 구현 등 다양한 애플리케이션에서 기본 데이터 구조로 일반적으로 사용된다.