들어가기 전에

레드 블랙 트리 규칙을 만족하는지 확인하고 색상 전환을 하는 색상 확인 메소드에 대해 알아보도록 하겠습니다.

학습 목표

레드 블랙 트리의 색상 확인 메소드를 이해할 수 있습니다.

핵심 단어

• 레드 블랙 트리
• 색상 확인 메소드

강의 듣기

색상 확인 메소드

노드를 트리의 규칙에 맞게 추가한 후, 2-1강에서 배운 레드 블랙 트리의 6가지 규칙을 만족하는지 확인해주어야 합니다.

public void checkColor(Node<K,V> node){
	//  루트는 항상 검은색이므로 색을 확인할 필요가 없습니다.
	if (node == root)
		return;
	// 빨간 노드 2개가 연속으로 나오는 경우 (레드 블랙 트리 규칙 위반)
	if (!node.black && !node.parent.black){
		correctTree(node);
	// 부모 노드를 계속 확인합니다.
	checkColor(node.parent);
}

public void correctTree(Node<K,V> node){
	// node의 부모 노드가 왼쪽 자식이면 이모 노드는 조부모 노드의 오른쪽 자식입니다.
	if (node.parent.isLeftChild) {
		// 이모 노드가 검은색 (이모 노드가 비어있는 경우 포함)
		if(node.parent.parent.right == null || node.parent.parent.right.black)
			// 회전
			return rotate(node);
		//  이모 노드가 빨간색
		if (node.parent.parent.right != null)
			// 색상 변환
			node.parent.parent.right.black = true;
		node.parent.parent.black = false;
		node.parent.black = true;
		return;
	}
	// node의 부모 노드가 오른쪽 자식이면 이모 노드는 조부모 노드의 왼쪽 자식입니다.
	// 위 코드와 동일하게 하되, 이모 노드를 node.parent.parent.left로 바꿉니다.
	else {
		// 이모 노드가 검은색 (이모 노드가 비어있는 경우 포함)
		if(node.parent.parent.left == null || node.parent.parent.left.black)
			// 회전
			return rotate(node);
		//  이모 노드가 빨간색
		if (node.parent.parent.left != null)
			// 색상 변환
			node.parent.parent.left.black = true;
		node.parent.parent.black = false;
		node.parent.black = true;
		return;
	}

생각해보기

1) correctTree 메소드는 어떤 일을 하나요?