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

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

1. 모든 노드는 블랙 노드이거나 레드노드이다
2. 루트는 블랙노드이다
3. 모든 리프 노드는 블랙노드이다 (*리프 노드 : child가 없는 노드)
4. 레드 노드의 child들은 모두 블랙 노드이다
5. 임의의 노드에 대해 그 노드부터 후손 리프 노드까지의 경로에는 같은 수의 블랙노드가 있다

레드 블랙 트리 예시

균형 이진 탐색 트리 => 탐색시간 O(log n)

키의 개수 n, 리프의 개수 L 이라고 하였을 때, 전체 노드의 수 = n + L  = 전체 edge 수 +1 = 2n +1

L= n+1 

 

레드 블랙 트리 평균 높이 : 원래 트리의 높이를 h, 새로운 트리의 높이를 h' 라 하면 h' >= h/2 

검색 연산들은 이진검색 트리와 동일. 삽입, 삭제는 Rotation을 이용하여 수행하다

 

회전(Rotation)

 

삽입(Insertion)

 

1. BST 와 동일한 알고리즘으로 새 노드 x를 추가한 뒤 레드노드로 만든다, 이 과정 수행시간 O(log n)

2. 4가지 경우로 나누어 조정, 이 과정 수행시간 O(1) => 총 수행시간 O(log n)

1. x 가 루트인 경우 => x의 색깔 black으로 바꿔줌
2. 부모(x)의 색 black 인 경우 => 아무 것도 안한다
3. 부모(x)의 색 red , 삼촌(x)의 색 red 인 경우 => 부모(부모(x)), 부모(x), 삼촌(x) 의 색 반전 (각각 red, black, black으로 변한다 

   

4. 부모(x)의 색 red , 삼촌(x)의 색 black 인 경우 =>
   1. x, 부모(x), 부모(부모(x)) 가 linear(선형) 한 경우 => 회전 후 색조정
   2. x, 부모(x), 부모(부모(x)) 가 triangle(삼각) 한 경우 => 최대 2번 회전 후 색조정

      

삭제(deletion)

기본적으로 이진탐색트리의 삭제에 기반하고

노드 삭제 후, 무너진 레드 블랙 트리의 규칙을 지키도록 수정하는 것이 핵심이다

기본적으로 삭제된 노드가

• red 인 경우는 추가 작업 필요X
• black 인 경우 자리를 대체하는 노드 검정색으로 변환 
  • red -> black 인 경우 수정 필요X
  • black -> black 인 경우 이중 흑색 노드

삭제한 노드가 black 이고, 이중 흑색 노드인 경우

• 삭제한 노드의 형제가 red인 경우 =>
  1. x 의 형제 black 으로 색 조정
  2. x의 부모 red 으로 색 조정
  3. x의 부모 기준으로 좌회전 
• x의 형제가 black, x의 형제 자식 모두 black =>
  1. x의 형제 red로 색 조정
  2. x의 black 1개를 x의 부모로 이동
  3. 이중 흑색 노드 root 도달시 끝
• x의 형제가 black, x의 형제 left 자식 red, right 자식 black =>
  1. x의 형제 red로 색 조정
  2. x의 왼쪽 자식 black 으로 색조정
  3. x형제 기준으로 오른쪽 회전
• x의 형제가 black, x의 형제 right 자식 red =>
  1. x의 부모의 색을 x을 형제에게 넘긴다
  2. x의 부모를 black 
  3. x 형제의 오른쪽 자식 black 
  4. x 부모 기준 왼쪽 회전