모각코 6일차 결과 (2. 12)

인프런에서 권오흠 교수님의 알고리즘 강좌를 듣고 필기한 내용이다.

수강한 파트는 Red-black Tree이다.

강의 분량이 많아서 Delete 부분은 다음에 수강할 예정이다.

BST의 일종

Balanced BST -> 높이가 O(logn)

Search, Insert, Delete 연산을 최악의 경우에도 O(logn) 시간에 지원

-----------------------------------------------------------------------------

각 노드 -> key, left, right, parent 의 주소를 저장

자식노드가 존재하지 않을 경우, NIL 노드라고 부르는 특수한 노드가 있다고 가정

따라서 모든 리프노드는 NIL 노드

루트의 부모도 NIL노드라고 가정

노드들은 내부노드와 NIL 노드로 분류

NIL 노드 -> 실제로 구현하는 노드는 아님

-----------------------------------------------------------------------------

레드-블랙 트리의 정의 

다음 조건들을 만족하는 BST

1. 각 노드는 red 또는 black

2. 루트노드는 black

3. 모든 리프노드(즉, NIL노드)는 black

4. red노드의 자식노드들은 전부 black이고(즉, red노드는 연속되어 등장하지 않음)

5. 모든 노드에 대해서 그 노드로부터 자손인 리프노드에 이르는

    모든 경로에는 동일한 개수의 black노드가 존재한다.

-----------------------------------------------------------------------------

노드 x의 높이 h(x)는 자신으로부터 리프노드까지의 가장 긴 경로에 포함된 에지의 개수이다.

노드 x의 블랙-높이 bh(x)는 x로부터 리프노드까지의 경로상의 블랙노드의 개수이다(노드 x 자신은 불포함, NIL노드 포함)

-----------------------------------------------------------------------------

search 연산 -> BST와 동일

-----------------------------------------------------------------------------

left and right rotation

시간 복잡도 O(1)

BST의 특성을 유지

-----------------------------------------------------------------------------

insert 연산

1. 보통의 BST에서처럼 노드를 insert한다.

2. 새로운 노드 z를 red 노드로 한다.

3. RB-INSERT-FIXUP을 호출한다. (red red violation에 대한 처리)

위반될 가능성이 있는 조건들

1. OK

2. 만약 z가 루트노드라면 위반, 아니라면 OK

3. OK

4. z의 부모 parent(z)가 red이면 위반 (red red violation)

5. OK 

-----------------------------------------------------------------------------

RB-INSERT-FIXUP

Loop Invariant:

z는 red노드

오직 하나의 위반만이 존재한다:

  조건 2 : z가 루트노드이면서 red이거나, 또는

  조건 4 : z와 그 부모 parent(z)가 둘 다 red이거나

종료 조건:

  부모노드 parent(z)가 black이 되면 종료한다. 조건 2가 위반일 경우 z를 블랙으로 바꿔주고 종료한다.

Case 1~6까지 있음

Case 1, 2, 3 -> parent(z)가 grandparent(z)의 left child

Case 1 : z의 uncle이 red

parent(z) -> black으로

uncle(z) -> black으로

grandparent(z) -> red로

z = grandparent(z)로      

(z와 z의 parent 사이에 red-red violation 발생 가능) -> z에 대해 RB-INSERT-FIXUP함수 재수행 (recursive 또는 iterative)

Case 2, 3 : z의 uncle이 black

Case 2 : z가 오른쪽 자식인 경우 <left right>

parent(z)에 대해서 left-rotation

z = parent(z)

case 3로

case 3 : z가 왼쪽 자식인 경우 <left left>

parent(z)를 black, grandparent(z)를 red로 바꿈

grandparent(z)에 대해서 right-rotation

(red-red violation 발생 안함)

Case 4, 5, 6 -> parent(z)가 grandparent(z)의 right child  <Case 1, 2, 3과 대칭적임>

-----------------------------------------------------------------------------

Insert의 시간 복잡도

BST에서의 INSERT : O(logn) <참고로 로그의 밑은 2임>

RB-INSERT-FIXUP:

Case1에 해당할 경우 z가 2레벨씩 상승 O(logn)

Case 2,3에 해당할 경우 O(1)

따라서 트리의 높이에 비례하는 시간

즉, INSERT의 시간복잡도는 O(logn) <로그의 밑은 2!>

-----------------------------------------------------------------------------