[자료구조] 4-6. 레드-블랙트리의 삽입(Insertion in Red-Black Tree)

레드블랙트리의 삽입

 

레드-블랙트리의 삽입에서, 다음과 같은 과정을 거친다:

 

1.이진 탐색 트리와 같이 노드를 삽입하고, 삽입한 노드의 색은 빨간색으로 한다.

2.트리에 문제가 생기진 않는지 확인해주고, 문제가 있으면 고쳐준다.

 

레드블랙트리의 삽입에서의 문제 해결은 다음과 같은 경우들이 있다:

 

삽입되는 노드를 편의상 z라고 가정해보자.

 

 

1. z가 루트인 경우

z가 루트인 경우는 쉽다. 루트 노드의 색은 검정색이여야 하므로 빨간색을 검은색으로 칠해주면 된다.

이 경우를 제외한 나머지 경우는 모두 부모 노드가 빨간색이라 Double Red가 생긴 경우이다.

 

 

2. z의 삼촌이 빨간색인 경우

z의 삼촌이 빨간색일 땐, 조부모 노드(부모노드의 부모노드)의 색을 빨간색으로 칠해주고, 부모노드와 삼촌노드를 검은색으로 칠해준다.

트리의 검은색 균형도 맞추고, 이중 레드를 해결할 수 있다.

 

 

3. z의 삼촌이 검은색이고, 조부모 - 부모 - z의 위치가 삼각형을 만들 때(조부모노드보다 작고, 부모노드보다는 클 때, 또는 조부모노드보다 크로 부모노드보다는 작을 때)

z의 삼촌이 검은색이고, 조부모 - 부모 - z가 삼각형을 만들면, 

가. 조부모 < z < 부모인 경우 : 위 그림처럼 부모 노드를 우회전시킨다.

나. 부모 < z 조부모인 경우 : 위 그림과 반대로, 부모 노드를 좌회전시킨다.

 

부모 노드를 회전시킨 뒤, 아래 4번 케이스로 넘어간다.

 

4. z의 삼촌이 검은색이고, 조부모 - 부모 - z가 직선을 그릴 때(조부모 < 부모 < z 또는 z < 부모 < 조부모 인경우)

가. 조부모 < 부모 < z인 경우, 위 그림처럼 조부모를 좌회전시킨다.

나. z < 부모 < 조부모인 경우, 위 그림과 반대로 조부모를 우회전시킨다. 

 

조부모를 회전 시킨 뒤, 조부모와 부모의 색을 바꿔준다.

위 그림에서 검은 색 노드의 균형이 깨지는 것 같아 보일 수 있지만, 애초에 위 그림은 예시를 들기 위한 상황이고, 실제로 저런 상황이 나올일이 없다.  

 

 

다음은 레드-블랙 트리의 슈도코드이다:

_insert(T, z):
	node = Node(key, val)
    if T.root == NIL // 1번
    	T.root = node
        node.color = black
        return
    
    current = T.root
    
    while True:
    	if node.key < currnet.key:
        	if current.left == None:
        		current.left = node
                node.parent = current
                break
            current = current.left
        else:
            if current.right == None:
                current.right = right
                node.parent = current
                break
            current = current.right
    
    T._insert_fixup(node)
    
_insert_fixup(T, node):
	while node.parent.color == red:
		if node.parent == node.parent.parent.left:
          uncle = node.parent.parent.right
          if uncle.color == red: // 2번
            uncle.color = black
            node.parent.color = black
            node.parent.parent = red
          else:
            if node == node.parent.right: // 3번
              node = node.parent
              left_rotate(node)
            node.parent.color = black // 4번
            node.parent.parent.color = red
            right_rotate(node.parent.parent)
        else:
          //left와 right를 반대로 해주면 된다(생략)
          
    T.root.color = black