[sw정글] RB트리 INSERT pseudo-code 정리 - sentinel node

RB트리 시물레이션 사이트 - 이 사이트를 사용하면서 삽입을 구현하면 조금 더 쉬울 것이다.

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

Red/Black Tree Visualization

RB트리 삽입

RB트리의 insert는 BST의 insert와 매우 유사하다.

다만 RB트리의 특성을 유지하기 위해 몇 가지 작업이 더 들어가게 된다.

insert를 하기 위해서 아래와 같은 함수들이 필요하다.

• insert(T, z)  - 이진트리의 insert와 유사
• left_rotate(T, x) - x를 중심으로 왼쪽 회전
• right_rotate(T,x) - x를 중심으로 오른쪽 회전
• insert_fixup(T,z) - 각 경우에 따라 색상 변경과 회전을 하여 특성을 복구하는 함수

RB 트리 INSERT(T, z) - 의사 코드

이진 검색 트리의 삽입에서 약간 변형해서 사용함

x : z가 삽입될 위치

y : z가 삽입될 위치의 부모

z : 삽입될 새로운 노드

RB-insert(T, key)

y = T.nil
x = T.root
z = new Node
z.key = key
while x!= T.nil         // z가 삽입될 위치를 찾는다.
	y = x
	if z.key < x.key
		x = x.left
	else
		x = x.right
z.p = y
if y == T.nil
	T.root = z
else if z.key < y.key
	y.left = z
else
	y.right = z
z.left = T.nil
z.right = T.nil
z.color = RED          //RB 트리에서 삽입되는 새로운 노드의 색은 RED이다

RB_INSERT_FIXUP(T, z)  // 삽입으로 인해 까진 RB트리의 특성을 맞추기 위한 함수

RB 트리 LEFT_Rotate(T, x) - 의사 코드

T : rb트리 구조체

x : 회전의 중심이 되는 구조체

p: 노드의 parent이다

결과: y는 서브 트리의 새로운 루트가 되고 x는 y의 왼쪽 자식이 되고, y의 왼쪽 자식은 x의 오른쪽 자식이 됨

left_rotate(T, x)

y = x.right            // y 설정
x.right = y.left       // y의 왼쪽 서브트리 -> x의 오른쪽 서브트리로 이동
if y.left != T.nil     
	y.left.p = x
y.p = x.p
if x.p == T.nil
	T.root = y
else if x == x.p.left
	x.p.left = y
else
	x.p.right = y
y.left = x
x.p = y

RB 트리 RIGHT_Rotate(T, x) - 의사 코드

왼쪽 회전에서 left → right로 right → left로 바꿔주면 된다.

결과: y는 서브 트리의 새로운 루트가 되고 x는 y의 오른쪽 자식이 되고, y의 오른쪽 자식은 x의 왼쪽 자식이 된다.

right_rotate(T, x)

y = x.left
x.left = y.right
if y.right !- T.nil
	y.right.p = x
y.p = x.p

if x.p == T.nil
	T.root = y
else if x == x.p.right
	x.p.right = y
else
	x.p.left = y
y.right = x
x.p = y

RB_insert_fixup(T, z) - 의사 코드

삽입 후 깨진 RB트리의 특성을 복구하는 함수이다.

z : 새로 추가되는 노드

y : z 노드의 삼촌 노드

insert는 3가지의 경우가 생긴다.

case 1: 삼촌 노드(y)가 빨간색일 때

• z의 부모와 삼촌의 색을 BLACK으로 변경하고 z의 조부모의 색을 빨강으로 변경한다.
• z의 포인터를 2단계 올려 z의 조부모를 가리키게 한다. → z의 조 부모가 새로운 z가 되어 fixup을 돈다.

case 2: z 노드가 부모의 오른쪽 자식일 때

• z를 중심으로 좌회전(left rotate) 한다.

csse 3: z 노드가 부모의 왼쪽 자식일 때

• z 부모의 색을 BLACK으로 z의 조부모의 색을 RED로 변경한다.
• z의 조부모를 기준으로 우회전(right_rotate) 한다.

RB_insert_fixup(T, z)

while z.p.color == RED
	// z의 부모가 조부모의 왼쪽 노드 일 때
	if z.p == z.p.p.left
		y = z.p.p.left
		// case 1: 삼촌 노드가 빨간색일 때
		if y.color == RED
			z.p.color = BLACK
			y.color = BLACK
			z.p.p.color = RED
			z = z.p.p
		else // 삼촌이 검정일 때
			// case 2: z 노드가 부모의 오른쪽자식 일 때
			if z == z.p.right
				z = z.p
				left_rotate(T, z)
			// case 3: z 노드가 부모의 왼쪽자식 일 때
			z.p.color = BLACK
			z.p.p.color = RED
			right_rotate(T, z.p.p)
	else
   //z의 부모가 조부모의 오른쪽 노드 일 때
	 //이 경우에는 왼쪽 노드 일때에서 left -> right로 right ->left로 모두 변경하면된다.
   // 알아서 해보길 바란다.

T.root.color = BLACK

이진 검색 트리에서 노드를 삽입하는 것 까지는 똑같지만 삽입 후 RB트리의 특성을 맞추기 위해서 해주어야 할 코드가 늘었다.

노드를 색을 변경하고 회전하는 부분이 조금 어려울 것이다.

위 3가지 경우를 직접 그리면서 색 칠하고 회전하면 이해가 더 잘 될 것이다.

삭제는 삽입보다 매우 많이 어려우니 더 열심히 해보자