[Week05] C언어 - Red Black Tree

Red - Black Tree
레드 블랙 트리

 

https://ko.wikipedia.org/wiki/레드-블랙_트리

레드-블랙 트리 - 위키백과, 우리 모두의 백과사전

 

이진 탐색트리의 한 종류

BTS의 worst case의 단점을 개선 - 스스로 균형을 맞추며 편향된 트리가 되지않도록 한다.

최악의 경우에도 시간복잡도가 O(logN)

 

규칙

1. 레드와 블랙으로만 이루워진다.
2. 루트 노드는 블랙이다.
3. nil노드는 블랙이다.
4. 레드의 자식은 레드만 올수있다.
5. 임의의 노드에서 자손 nil 노드까지 가는 경로의 블랙 노드이 개수는 같다. (자기자신 제외)

 

균형을 맞춘 트리에서 두 자녀가 같은 색을 가질때 부모와 두 자녀의 색을 바꿔줘도 5번 속성을 유지한다.

 

Black height

임의의 노드에서 자손 nill노드까지 가는 경로의 블랙 노드의 개수

 

회전

회전을 하는 이유는 편향된 트리가 되지않게 하기위해 값을 넘기려는데 BST 특징 또한 유지하면서 넘기기 위해 회전을 사용한다.

 

삽입

• 일반적인 BST(이진탐색트리)와 동일하게 삽입

삽입하는 노드이 색상읜 항상 red로 한다.  >>  5번 규칙을 유지하기 위해

 

• 삽입 후 위반 여부 확인 후 균형 맞추기 - 4,2번 규칙 위반 가능

1. 4번 속성위반에 따른 3가지 case

 

case 3 : 삽입한 노드가 부모의 왼쪽 자녀일때 부모도 red이며 할아버지의 왼쪽 자녀 & 삼촌 노드가 black 일때

   부모와 할이버지의 색을 바꿔준 다음 할아버지 기준으로 오른쪽으로 화전

 

case 2 : 부모의 오른쪽 자녀이며(꺽인 부분), 부모도 red고 할아버지의 왼쪽 자녀이며 삼촌노드가 black 일때

  꺽인 부분을 펼친후(부모를 기준으로 왼쪽으로 회전) case3과 동일하게 해결한다.

case 1 : 삼촌이 black일때 (red가 한쪽으로 몰려있지않다.)

  자녀의 색이 둘다 같으면 부모의 색과 변경가능하다 - 트리의 규칙

 

 

2. 2번 속성위반시 루트 노드의 색을 black으로 변경

 

삭제

• 일반적인 BTS와 동일하게 삭제

삭제 노드의 자녀의 수에 따른 확인

 - 없거나 하나라면 삭제되는 노드 본인 색 삭제

 - 두명이면 삭제되는 successor(나보다 작은 수 중 제일 큰 수)의 색 삭제

• 삭제 후 위반 여부 확인 후 균형맞추기

어떤 색이 삭제되는지에 따라 위반여부 확인

1. 삭제되는 색이 red일 경우 어떤 속성도 위반하지 않는다.
2. 삭제되는 색이 Black일 경우 : 2,4,5 규칙 위반 가능

그 중 5번 속성을 항상 위반하게 된다.

5번 속성을 다시 만족시키기 위해서 대체노드에 extra black을 부여한다.

red and black의 경우 : black으로 바꿔준다. (4,5번 속성 모두 만족하게됨)

doubly black의 경우 : 노드의 형제의 색과 형제의 자식의 색에 따라 4가지 case

 

 

case 4 : 오른쪽 형제가 black이고, 그 형제의 오른쪽 자녀가 red일때

  해당 red를 doublely black위로 옮긴후에 extra black을 옮겨 red and black을 만들어 해결한다.

 

(1) 트리 규칙에 따라 C, E 와 D의 색을 바꿔 red를 D로 옯긴다. - C가 뭔지모르니까 C에게 extra black을 부여한다.

(2) B와 D(red)의 색을 바꿔준후 B를 기준으로 왼쪽으로 회전한다.

(3) A,C의 extra black을 B로 옯겨준다. B가 red and black의 되며 해결된다.

 

case 3 : 오른쪽 형제가 black이고, 그 왼쪽 자녀가 red / 오른쪽 자녀가 black 일때

  형제의 오른쪽 자녀를 red가 되게 만들어서 case4 적용한다.

(1) C와 D의 색을 바꾼후 D를 기준으로 오른쪽으로 회전한다.

(2) case4를 적용한다.

 

 

case 2 : 오른쪽 형제가 black이고, 형제의 두 자녀도 black일때

   doubly black과 그 형제를 black을 부모노드에게 extra black을 넘긴다.

   B의 노드가 doubly black이 됐다면 다시 반복

 

 

case 1 : 오른쪽 형제가 black인 경우

   부모와 형제의 색을 바꾸고 부모 기준으로 왼쪽으로 회전한뒤 case 중 하나로 해결

 

 

 

참고 자료

Introduction To Algorithms - 한빛아카데미 출판

신찬수 교수님 https://youtu.be/SHdYv41iCmE

쉬운코드 https://youtu.be/2MdsebfJOyM

 

코드

깃허브 https://github.com/youngjijang/rbtree-lab