7-2) RB(Red Black Tree) - rotate 메소드, 좌측 회전, 좌-우 회전, 높이, 검은색 노드 개수

 

아래 내용은 부스트코스 <자바로 구현하고 배우는 자료구조> 강의를 들으며 정리한 것입니다.

 

rotate (회전) 메소드

현재 노드와 부모 노드가 각각 오른쪽 자식인지 왼쪽 자식인지에 따라 필요한 회전이 달라진다.

public void rotate(Node<K,V> node){
	// 현재 노드가 왼쪽 자식
	if (node.isLeftChild) {
		// 부모 노드가 왼쪽 자식
		if (node.parent.isLeftChild)
			// 조부모 노드를 우측회전
			rightRotate(node.parent.parent);
			node.black = false;
			node.parent.black = true;
			if(node.parent.right != null)
				node.parent.right.black = false;
			return;
		}
		// 부모 노드가 오른쪽 자식
		// 조부모 노드를 우측-좌측 회전
		rightleftRotate(node.parent.parent);
		node.black = true;
		node.right.black = false;
		node.left.black = false;
		return;
	}
	// 현재 노드가 오른쪽 자식
	else {
    	// 부모 노드가 오른쪽 자식
    	if (!node.parent.isLeftChild)
			// 조부모 노드를 좌측회전
			leftRotate(node.parent.parent);
			node.black = false;
			node.parent.black = true;
			if(node.parent.right != null)
				node.parent.right.black = false;
			return;
		}
		// 부모 노드가 왼쪽 자식
		// 조부모 노드를 좌측-우측 회전
		leftrightRotate(node.parent.parent);
		node.black = true;
		node.right.black = false;
		node.left.black = false;
		return;
	}
}

 

좌측 회전

 parent 노드를 가리키는 포인터와 isLeftChild 변수를 추가로 사용하기 때문에 이들을 고려해주어야 한다.

 

// 좌측 회전: 조부모 노드를 부모 노드의 왼쪽 자식 노드 위치로 옮깁니다.
public void leftRotate (Node<K,V> node){
	Node<K,V> temp = node.right;
	node.right = temp.left;
	// 부모 노드 node.right가 temp가 되면서 조부모 노드가 없어집니다.
	if(node.right != null) {
		node.right.parent = node;
		node.right.isLeftChild = false;
	}
	// node가 루트인 경우
	if(node.parent == null) {
		root = temp;
		temp.parent = null;
	}
	// node가 루트가 아닌 경우
	else {
		temp.parent = node.parent;
		if(node.isLeftChild) {
			temp.isLeftChild = true;
			temp.parent.left = temp;
		} else {			
			temp.isLeftChild = false;
			temp.parent.right = temp;
		}
		temp.left = node;
		node.isLeftChild = true;
		node.parent = temp;
	}
}

 

좌측-우측 회전

앞의 트리에서 보았던 좌-우측 회전과 마찬가지로 작성한다.

// 좌측 회전 후 우측 회전
public void leftRightRotate(Node<K,V> node){
	leftRotate(node.left);
	rightRotate(node);
}

 

높이 구하기 (height)

간단한 재귀 메소드를 이용해 트리의 높이를 구한다.

public int height() {
	if(root == null)
		return 0;
	return height(root) - 1;
}
// 오버로딩: 높이는 가장 긴 경로의 길이
// 트리 끝까지 가게 되면(null) 다시 돌아오며 높이가 반환됨
public int height(Node<K,V> node) {
	if (node == null)
		return 0;
	int leftheight = height(node.left) + 1
	int rightheight = height(node.right) + 1
	if (leftheight > rightheight)
		return leftheight;
	return rightheight;
}

 

검은색 노드 개수

public int blackNodes(Node<K,V> node) {
	if (node == null)
		return 1;
	int rightBlackNodes = blackNodes(node.right)
	int leftBlackNodes = blackNodes(node.left)
	// 오른쪽과 왼쪽의 검은색 노드 개수가 다르면 에러를 내거나 고침
	if (rightBlackNodes != leftBlackNodes)
		// throw an error
		// or fix the tree
	// 검은색 노드이면 해당 노드의 수를 늘려준다
	if (node.black)
		leftBlackNodes++;
	return leftBlackNodes;
}