Java-자료구조 5주차 RB Tree 5 - 14 ~ 17

5주차. RB Tree

5-14 좌측 회전

• 좌측 회전 in RB Tree
  -원래 좌측 회전 코드와 유사하나, 포인터 parent와 isLeftChild라는 변수가 추가되어 이를 고려해야한다
  -입력값: 조부모 노드

자식->부모인 포인터:parent
부모->자식인 포인터:left,right
:이를 가지고 노드의 존재 파악(반환X)

+) 회전 결과

<코드-좌측 회전>

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;
        // temp는 조부모 노드와 같은 취급
		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;
	}
}

:회전의 종류에 따라 어느 쪽의 child를 건드려야 하는지가 달라진다
회전 과정)

+)코드-우측 회전

public void RightRotate (Node<K,V> node){ 입력값:조부모 노드
	Node<K,V> temp = node.left;
	node.left = temp.right;
    
	// 부모 노드 node.right가 temp가 되면서 조부모 노드가 없어진다
	if(node.left != null) { 
		node.right.parent = node;
		node.right.isLeftChild = true;
	}
    
	// node가 루트인 경우
	if(node.parent == null) {
		root = temp; 
		temp.parent = null;
	}
    
	// node가 루트가 아닌 경우
	else {
		temp.parent = node.parent; // temp(부모 노드가 조부모노드의 부모를 따름)
		if(node.isLeftChild) {
			temp.isLeftChild = true;
			temp.parent.right = temp;
		} else {			
			temp.isLeftChild = false;
			temp.parent.left = temp;
		}
		temp.right = node;
		node.isLeftChild = true;
		node.parent = temp;
	}
}

5-15 좌측-우측 회전

• 기본적으로 좌측-우측/우측-좌측 회전을 할 경우, 이전과 비슷하게 진행 -> 메소드 호출로 회전을 한다

좌측/우측 회전의 경우, 한 번에 회전하기에 조부모 노드를 가지고 발동하지만
좌측-우측/우측-좌측 회전인 경우, 회전을 두 번 발동하기 때문에 먼저 부모 노드를 가지고 회전을 발동한 뒤에 조부모 노드로 회전한다

<좌측-우측 회전 코드>

public void leftRightRotate(Node<K,V> node){
	leftRotate(node.left);
	rightRotate(node);
}

<우측-좌측 회전 코드>

public void leftRightRotate(Node<K,V> node){
	rightRotate(node.left);
	leftRotate(node);
}

5-16 높이
트리에서는 높이를 계산해야 한다

• 높이:트리의 어느 지점에서나 높이는 왼쪽과 오른쪽 중 가장 긴 경로의 길이

트리의 높이 구하는 메소드
<코드>

public int height() {
	if(root == null)
		return 0; // height = 0
	return height(root) - 1;
}

public int height(Node<K,V> node) { // height 메소드 오버 로딩
	if (node == null)
		return 0;
	int leftheight = height(node.left) + 1
	int rightheight = height(node.right) + 1
	if (leftheight > rightheight)
		return leftheight;
	return rightheight;
}

:노드의 갯수와 높이는 연관없다
:null이 되는 부분이 height

5-17 검은색 노드 갯수

• RB Tree 내 black node의 갯수 구하는 메소드
  -루트 아래에 있는 black node의 갯수 구하며, 이때 재귀 메소드 사용
  -입력 노드: 루트

<코드>

public int blackNodes(Node<K,V> node) {
	if (node == null)
		return 1; // 빈 노드 == black node
        
	int rightBlackNodes = blackNodes(node.right)
	int leftBlackNodes = blackNodes(node.left)
	if (rightBlackNodes != leftBlackNodes)
		// throw an error or fix the tree
	// 검은색 노드이면 해당 노드의 수를 늘려줍니다.
	if (node.black) // 현재 노드는 black node인가
		leftBlackNodes++;
	return leftBlackNodes;
}

:right의 black node와 left의 black node의 갯수가 같은지 먼저 확인한 뒤에 black node의 존재 확인과 갯수 추가
:오른쪽과 왼쪽의 검은색 노드 개수가 다르면 에러가 일어나니 고친다