[TIL] 자료구조 - 색상 확인 메소드

※ 색상 확인 메소드

- 노드를 트리의 규칙에 맞게 추가한 뒤, 레드 블랙 트리의 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;
	}
    
    // 출처: 부스트코스 - 자바로 구현하고 배우는 자료구조