비선형 데이터구조, RedBlackTree #1 RedBlackTree의 규칙 및 수행과정

1. RedBlackTree의 규칙

1. 모든 노드는 Red 또는 Black
2. Root 노드는 언제나 Black
3. 새로 추가되는 노드는 항상 Red
4. Root 노드에서 Leaf 노드까지 가는 모든 경로에는 같은 수의 Black 노드가 있어야한다
5. 어떤 경로에서도 Red 노드 2개가 연속으로 있어서는 안된다
6. 모든 Null 노드는 Black이라고 가정한다

2. RedBlackTree 수행과정

2.1 Rebalance

RedBlackTree에 노드를 추가할 때, RedBlackTree의 규칙에 위반되면 트리의 균형을 맞추기 위해 Rebalance 연산을 수행합니다. RedBlackTree의 Rebalance 연산에는 Black Aunt Rotate, Red Aunt Colorflip 연산이 존재합니다.

• Black Aunt Rotate (BAR) : 추가된 노드(newNode)의 이모(Aunt) 노드의 색상이 Black인 경우 회전을 수행합니다. 그리고 색상을 변환합니다. 회전 이후 노드의 색상 변환은 다음과 같습니다.
  • Left / Right Rotate : 왼쪽 회전 또는 오른쪽 회전 이후 newNode는 자식 노드이기 때문에 newNode의 부모는 Black, newNode와 형제 노드는 Red로 변환합니다.
  • Left-Right Rotate / Right-Left Rotate : 회전 이후 newNode는 부모 노드가 되기 때문에 newNode는 Black, newNode의 왼쪽, 오른쪽 자식은 Red로 변환합니다.
• Red Aunt Colorflip (RAC): 추가된 노드의 이모(Aunt) 노드의 색상이 Red이면, 조부모 노드의 색상을 Red, 자식 노드들(부모 노드, 이모 노드)을 Black 색상으로 변경합니다.

2.2 Examples

삽입 순서 : 3->1->5->7->6->8->9->10

위 그림에서 정수 7를 삽입한 순간 규칙 5에 위반됩니다. 이모 노드가 Red이므로 조부모 노드(3)는 Red, 부모 노드(5)와 이모 노드(1)는 Black으로 색상 변환을 합니다. 그리고 조부모 노드(3)는 루트이지만 색상이 Red이므로 규칙2에 위반됩니다. 따라서 조부모 노드(3)의 색상을 Black으로 변환합니다.

 

위 그림에서 newNode(6)은 규칙 5를 위반합니다. newNode의 이모 노드의 색상은 Null 노드이기 때문에 Black입니다. 따라서 조부모 노드(5)를 기준으로 Right-Left Rotate를 수행합니다.

 

위와 같이 회전 수행 이후 색상을 변환합니다. newNode(6)는 Black, 왼쪽(5), 오른쪽(7) 자식은 Red로 변환합니다.

 

위 그림에서 newNode(8)은 규칙 5에 위반됩니다. 이모 노드(5)가 Red이므로 조부모 노드(6)의 색상을 Red, 부모 노드(7)와 이모 노드(5)의 색상을 Black으로 변환합니다.

 

위 그림에서 newNode(9)에서 규칙 5가 위반됩니다. 이모 노드는 Null 노드이기 때문에 조부모 노드(7)를 기준으로 Left Rotate를 수행합니다. 회전 이후 부모 노드(8)의 색상을 Black, newNode(9)와 형제 노드(7)의 색상을 Red로 변환합니다.

 

위 그림에서 newNode(10)을 삽입 이후 규칙 5에 위반됩니다. 이모 노드가 Red이므로 조부모 노드(8)의 색상을 Red, 부모 노드(9)와 이모 노드(7)의 색상을 Black으로 변환합니다. newNode(10)의 부모 노드들(9,8,6,3)을 올라가면서 RedBlackTree의 규칙에 위반되는지 검사합니다.

 

그리고 위 그림에서처럼 노드(8)에서 규칙 5가 위반되는 것을 볼 수 있습니다. 노드(8)을 기준으로 이모 노드(1)이 Black이므로 조부모 노드(3)을 기준으로 Left Rotate를 수행합니다. 회전 수행 이후 노드(8)과 형제 노드를 Red, 부모 노드(6)의 색상을 Black으로 색상 변환을 하고 종료합니다.

3. RedBlackTree 클래스

public class RedBlackTree<K, V> {
	Node<K,V> root;
	int size;
	
	private class Node<K,V>{
		K key;
		V value;
		Node<K,V> left, right, parent;
		boolean isLeftChild, black;
		
		public Node(K key, V value)
		{
			this.key = key;
			this.value = value;
			left = right = parent = null;
			black = false;
			isLeftChild = false;
		}
	}
}

Node 클래스

• Node<K,V> left, right, parent : 노드의 왼쪽 자식, 오른쪽 자식, 부모 노드를 가리키는 포인터 변수
• boolean black : true이면 Red 색상, false이면 Black 색상
• boolean isLeftChild : 이모 노드의 색상을 알아내기 위해 사용되는 변수

 

References

[부스트코스] 자바로 구현하고 배우는 자료구조