[Red-Black 트리] 소개

레드 블랙 트리를 소개할 것이지만 먼저 이진검색 트리를 알아보도록 하겠습니다.

 

이진검색트리

---

1. 단순히 정렬되거나 정렬된 이진트리
2. 각 노드는 두개의 서브 트리를 가질 수 있습니다.
3. 특정 노드의 왼쪽에 있는 항목은 더 작고 오른쪽에 있는 노드가 더 큽니다.

이것은 매우 간단하지만 다음과 같은 경우에는

 한쪽으로 편향되었을때 삽입,삭제,검색 시 시간복잡도가 O(n)입니다. 이 말은 최악의 경우 노드를 하나 찾으려면 모든 노드를 방문해야하는 합니다. 이 단점을 개선하기 위해 편향된 구조가 되지 않도록 하는 레드블랙 트리가 등장.

 

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

---

📌레드블랙 트리 개념

• 이진탐색트리의 한종류 
• 스스로 균형을 잡는 트리
• BST의 단점을 개선
• 모든 노드는 red 혹은 black

 

💡nil 노드란?

• 존재하지 않음을 의미하는 노드
• 자녀가 없을때 자녀를 nii 노드로 표기
• 같이 있는 노드와 동등하게 취급
• RB트리에서 leaf 노드는 nil 노드

 

📌레드블랙 트리의 다섯가지 속성

1. 모든 노드는 red 혹은 black
2. 루트 노드는 black
3. 모든 nil노드는 black
4. red의 자녀들은 반드시 black == red가 연속적으로 존재할 수 없다.
5. 임의의 노드에서 자손 nii 노드들까지 가는 경로들의 black 수는 같다 (자기 자신은 카운트에서 제외)

 

💡노드 x의 black height

• 노드 x에서의 임의의 자손 nil노드까지 내려가는 경로에서의 black수 (자기 자신은 카운트에서 제외)
• #5 속성을 만족해야 성립하는 개념

 

💡색을 바꾸면서도 #5속성 유지하기

• RB트리가 #5 속성을 만족하고 있고 두 자녀가 같은 색을 가질 때 부모와 두 자녀의 색을 바꿔줘도 #5속성은 여전히 만족한다.
• #5 : 임의의 노드에서 자손 nil 노드들 까지 가는 경로들의 black수는 같다.

 

💡RB트리는 어떻게 균형을 잡는가?

• 삽입/삭제시 주로 #4,#5를 위반하여 이들을 해결하려고 구조를 바꾸다 보면 자연스럽게 트리의 균형이 잡히게 된다.