RBTree

이번 주차의 핵심 내용이다

RBTree

트리 중 상당히 상위권에 속하는 구조다

고효율이라는 점이다

트리에 n개의 원소가 있을 때
$O(log n)$의 시간 복잡도를 보장한다

RBTree 특성 (5개)

1. 모든노드는 RED/BLACK

2. 루트노드는 BLACK

3. 모든 NIL 노드는 BLACK

4. 노드가 RED면, 자식은 BLACK (RED는 연속할 수 없음)

5. 임의의 경로(자신을 제외)부터 자손 NIL까지 BLACK 개수는 동일

이 특성을 유지하기 위해 균형을 잡는다 한다

균형은 지켜져야만 한다

간단 단어 정리

• RED/BLACK:

  • 특징을 유지하고 구조를 나누기 위해 2분류로 나누는데 사용한다.

  • 딱히 색깔은 분류를 위해서라 의미 없다

• nil 노드:

  • 레드 블랙 트리에서 빈 자식을 대표하는 검은색 노드다 (하나만 만들고 공유한다)

  • NULL대신에 노드 객체 하나로 없음을 표현해 코드와 증명을 단순화한다

  • 루트의 부모(root->paret)도 보통 nil로 둔다

  • RB트리에서 leaf 노드는 nil 노드다

• black height:

  • RBTree 5번째 특성 만족할 떄 성립

  • 노드 x에서 임의의 자손 nil노드까지 내려가는 경로에서의 black 수 (자기자신 제외)

• extra black:

  • 5번 특성 맞추기 위한 임시 조치

• doubly black:

  • extra black이 부여된 black 노드

• red-and-black:

  • extra black이 부여된 red 노드

  • 나중에 blakc으로 바뀜

균형 유지 방법

삽입/삭제 시 특성이 위반되어 이를 지키고자 하면서 균형이 맞춰짐

삽입

1. 일반적 BST처럼 삽입

2. 삽입 후 RB 트리 위반 여부 확인

3. RB 트리 속성 위반시 재조정

4. 다시 한번 RB 트리 위반 여주 확인

삽입하는 노드는 항상 빨간색

-> 첫 삽입시 루트노드라 검정으로 변경

삽입시 RB 트리 위반했을때

이 경우 case 3개로 나눈다

case.3

1. 삽입된 red노드가 부모의 왼쪽* 자식 &
   부모도 red면서 할아버지의 왼쪽* 자식 &
   부모의 형제가 black일때

   • BST의 특징을 유지하면서 RB트리의 특징을 유지해야 하기에 회전시킨다

   • 부모와 할아버지의 색을 바꾼다

   • 이후 할아버지 기준으로 오른쪽*으로 회전한다

   • * 오른쪽 왼쪽 바꿔도 성립

case.2

1. 삽입된 red노드가 부모의 오른쪽* 자식 &
   부모도 red면서 할아버지의 왼쪽* 자식 &
   부모의 형제가 black일 때

   • 부모를 기준으로 왼쪽*으로 회전한다

   • 이후 case.3의 방식으로 해결

   • * 오른쪽 왼쪽 바꿔도 성립

case.1

1. 삽입된 red노드의 부모와 부모의 형제 모두 red일 떄

   • 부모와 부모 형제를 black으로 바꾼다

   • 할아버지를 red로 바꾼 뒤

   • 할아버지에서 다시 위반 여부 확인

삭제

삭제되는 색이 black일 떄 삭제되는 색이 있던 위치를 대체한 노드에 extra black을 부여

대체한 노드가 red-and-black이 됐다면 black으로 바꿔 해결

대체한 노드가 doubly black이 됐다면 케이스 4개 중 하나로 해결

doubly black 해결법

케이스 4개로 쪼개서 봐야 한다

case.4

1. doubly black의 오른쪽* 형제가 black &
   그 형제의 오른쪽* 자식이 red

   • 그 red를 doubly black 위로

   • 옮긴 red로 extra black 전달
     -> red-and-black으로 변환
     -> red-and-black을 black으로 변환

   • 과정 중략

   • 결과:

     • 오른쪽* 형제는 부모의 색으로, 오른쪽* 형제의 오른쪽* 자녀는 black으로,
       부모는 black으로 바꾼 후에 부모를 기준으로 왼쪽*으로 회전
   • * 오른쪽 왼쪽을 바꿔도 성립

case.3

1. doubly black의 오른쪽* 형제가 black &
   그 형제의 왼쪽* 자식이 red &
   그 형제의 오른쪽* 자식은 black

   • red를 형제인 black으로 바꾸면 첫번째의 상황과 동일

   • 즉, doubly black의 형제의 오른쪽* 자식를 red가 되게 만든 뒤에 case.4 적용해 해결

   • 오른쪽 자식 red로 바꾸기:

     • red 부모 노드로 이동후 red 부모 기준으로 오른쪽으로 회전

   • * 오른쪽 왼쪽 바꿔도 성립

case.2

1. doubly black의 형제가 black &
   그 형제의 두 자녀 모두 black일 때

   • doubly black인 노드와 그 형제의 black을 모아 부모에 전달

   • doubly black은 black이 되고 형제는 black에서 red가 된다

case.1

1. doubly black의 오른쪽* 형제가 red일 때

   • doubly black의 형제를 black으로 만든 후 case.2,3,4 중 하나로 해결

   • 형제 black으로 만들기:

     • red인 형제와 부모 색깔 변환

     • doubly black의 부모 기준으로 왼쪽*으로 회전

   • * 오른쪽 왼쪽 바꿔도 성립

개념 정리 완료다

코드 구현은…

오늘은 날이 아니다