[게임 프로그래머 입문 올인원] 트리 자료구조 : 레드 블랙 트리 (72강)

A. 트리 자료구조

3. 레드 블랙 트리

a. 레드 블랙 트리란?

🌟 각 노드가 레드 또는 블랙의 색상을 가지며 특정한 규칙을 따르는 트리 구조

 

균형 이진 탐색 트리의 일종

 

b. 레드 블랙 트리의 규칙

1. 각 노드는 레드 또는 블랙
2. 루트 노드, 모든 리프 노드(NIL)는 블랙
3. 레드 노드의 자식 노드는 모두 블랙
4. 어떤 노드로부터 리프 노드까지의 모든 경로에는 리프 노드를 제외하고 같은 개수의 블랙 노드가 있어야 함 = 블랙 높이

 

👉 위 내용만 잘 알고있으면 됨

 

 

c. 레드 블랙 트리의 특징

위 규칙을 통해 트리가 균형을 유지해 연산의 효율이 높아져

➡ 탐색, 삽입, 삭제 연산을 O(log n)의 시간복잡도로 보장

 

레드-블랙 트리는 데이터베이스, 맵 등의 자료구조로 널리 사용

 

d. 레드 블랙 트리 추가

1) 이상적인 상황

 

 

2) 이상적이지 않은 상황

 

 

u는 엉클, 위와 같은 규칙을 따름

 

위로 쭉 올라감

 

 

언젠간 턴을해서 이렇게 규칙을 맞춰줌

 

즉, 삼촌이 누군가에 따라서 규칙이 달라짐

 

e. 레드 블랙 트리 삭제

삭제 케이스 4가지

 

1) Case 1

 

그냥 삭제하면 끝

 

숫자가 안맞아짐

 

2) Case 2

 

루트를 제거하기

 

 

3) Case 3

 

 

4) Case 4

 

 

5) Case 5

 

 

6) Case 6

 

 

 

---

출처 : https://www.inflearn.com/course/%EA%B2%8C%EC%9E%84-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8-%EC%9E%85%EB%AC%B8-%EC%98%AC%EC%9D%B8%EC%9B%90-rookiss#curriculum

[게임 프로그래머 입문 올인원] C++ & 자료구조/알고리즘 & STL & 게임 수학 & Windows API & 게임 서버