레드 블랙트리(red-black tree)

레드 블랙 트리

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

nil 노드란?

• 자녀가 없을 때 자녀를 nil노드로 표기
• 값이 있는 노드와 동등하게 취급하며 RB트리에서 leaf 노드는 nil 노드

Red-Black 트리 속성

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

4번과 5번을 쉽게 이해하기 위한 예시

노드 x의 black height

• 노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서의 black 수
• 트리 속성 5번을 만족해야 성립하는 개념

Red-black tree를 사용하는 이유

red-black tree는 이진 탐색 트리의 단점을 보완하기 위해서 쓰는 자료구조.

이 그림의 시간복잡도를 따진다면 O(n)이다. 하지만 이진 블랙트리를 사용할 경울 O(n logn)이므로 시간복잡도를 줄일 수 있다.

Red-black tree 삽입/ 삭제를 만들기 전에 알아두어야 할 것

Left and Right Rotation (회전)