Red black Tree RBT

• 자가 균형 이진 탐색 트리
  • self balanced binary search tree
• 해결하는 문제
  • BST의 worst case의 단점을 개선
• 1972년 루톨프 바이어가 창안한 대칭형 이진 B-트리를 발전시켜 만듦
• 만족해야하는 조건
  1. 모든 노드는 빨간색 혹은 검은색
  2. 루트노드는 검은색
  3. 모든 NIL은 검은색
     • NIL: Null leaf 자료를 갖지 않고, 트리의 끝을 나타내는 리프노드
  4. 빨간색 노드의 자식은 반드시 검은 색
  5. NIL에서 루트 노드e까지 가는 경로에서 만나는 검은색의 노드의 개수가 같다.
• black height
  • 노드 x에서 임의의 자손 nil까지 내려가는 경로에서의 black 수
  • 5번 조건을 만족해야함
• RB 트리가 5번 속성을 만족하고 있고 두자녀가 같은 색을 가질 때 부모와 두자녀의 색을 바꿔줘도 5번 속성은 여전히 5번 속성을 만족함

How to balance itself

• 삽입되는 노드는 빨간색
  • 삽입 후에 5번 속성을 만족하기 위해
  • 삽입 후에도 부모 노드들이 5번 속성을 만족하게 하기 위함

삽입 속성 위반

case 1

• 예시) 20, 10, 50, insert(30)
• 해결 방법: 부모와 삼촌을 black으로 바꾸고, 할아버지를 red로 바꾼뒤 할아버지에서 다시 확인
  • 삽입된 red 노드의 부모도 red • 삼촌도 red

case2

• 예시) 50, 20, insert(40)
• 부모를 기준으로 왼쪽으로 회전한 뒤, case3 방식으로 해결
  • 삽입된 red 노드가 부모의 오른쪽 자녀
  • 부모도 red고 할아버지의 왼쪽 자녀
  • 삼촌은 black

case3

• 예시) 50, 20, insert(10)
• 삽입된 노드가 부모의 왼쪽 자녀, 부모도 red 할아버지 왼쪽 자녀, 삼촌은 black 이라면
• 부모와 할아버지의 색을 바꾼 후 할아버지 기준으로 오른쪽으로 회전

Recoloring

• 삽입될 노드의 부모 노드가 빨간색이고 삼촌 노드가 빨간색인 경우 Recoloring이 발생함

Restructing

Should know

• 색깔은 어떻게 정해지는거지?
  • 처음 노드가 들어올떄는 빨간색

참고

B+Tree는 디스크 접근을 최소화하기 위해 설계된 균형 트리 자료구조다