Java-자료구조 5주차 RB Tree 5 - 11 ~ 13

5주차. RB Tree
<코드 구현>

5-11 add 메소드 with RB Tree
:AVL Tree와 동작 방식은 동일하나 몇 가지 추가하여 이를 관리해야 한다
<코드>

public void add(K key, V value){
	Node<K,V> node = new Node<K,V>(key, value);
    
	// 트리가 비어있을 경우
	if (root == null) {
		root = node;
		root.black = true; // root는 항상 black
		size++;
		return;
	}
	// 트리에 노드가 있을 경우 재귀 메소드 사용해 추가
	add(root, node); (탐색 시작할 노드, 추가할 노드)
	size++;
}


// add 재귀함수, 내부클래스
private void add (Node<K,V> parent, Node<K,V> newNode){
	if (((Comparable<K>) newNode.key).compareTo(parent.key) > 0){ newNode > parent시 실행
		if(parent.right == null){ // 안하면 NullException 발생
			parent.right = newNode;
			newNode.parent = parent;
			newNode.isLeftChild=false;
			return; 
		}
		return add(parent.right, newNode); // 재귀 메소드로 
        
    //조건문에서 return하여 else 작성이 필요하지 않을 뿐 현재 코드는 else가 있는 상태로 발현된다
    // 즉, 아래는 newNode < parent인 상태
	if (parent.left == null){ 
		parent.left = newNode;
		newNode.parent = parent;
		newNode.isLeftChild=true;
		return;
	}
	return add(parent.left, newNode);
	
    // 노드 추가 후 트리에 규칙 확인
	checkColor(newNode);
}

:key-value가 있는 코드에서 비교할 경우, 보통 key만 비교
:isLeftChild가 원래 설정된 값과 같아도 설정하는 하는 편이 좋음(Boolean으로 다시 확인 가능)
:현재 isLeftChild는 현재 노드가 왼쪽 서브 트리에 해당하는가?를 물어본다
(True면 '이 노드는 왼쪽 서브 트리에 위치한다'를 의미)

5-12 색상 확인 메소드

• 추가할 새 노드를 트리의 규칙에 맞게 추가한 후, 규칙 만족하는지 체크하는 메소드 - checkColor메소드
• 규칙 위반 시, 수정을 위한 메소드 - CorrectTree메소드
  <코드>

public void checkColor(Node<K,V> node){
	if (node == root) // root는 항상 black으로 확인 필요X
		return;
	if (!node.black && !node.parent.black){ // 빨간 노드 2개가 연속으로 나오는 경우
		correctTree(node);
	
	checkColor(node.parent); // 재귀메소드로 부모 노드를 계속 확인
}

public void correctTree(Node<K,V> node){
	if (node.parent.isLeftChild) { // 부모 노드가 left child를 가지고 있음
    	// :이모 노드는 node.parent.parent.right
		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;
	}
    
    
	else { // 부모 노드가 right child를 가지고 있음
    	// :이모 노드는 node.parent.parent.left
		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;
	}

:루트는 항상 검은색, 새로 추가할 노드는 항상 붉은색이므로 이는 색을 확인할 필요X
:코드가 짧을수록 디버깅은 쉬워진다
:node의 parent가 left child이면 이모 노드는 grandparent의 right child
:node의 parent가 right child이면 이모 노드는 grandparent의 left child

5-13 Rotate 메소드

• RB Tree에서 회전할 때, 탐색 요소
  :현재 노드와 부모 노드는 각각 left child인가? right child인가?
  +) 회전 시 조부모-부모-아이의 위치
  
  :이에 맞춰 색상을 파악한다

<코드>

public void rotate(Node<K,V> node){
	if (node.isLeftChild) { // 현재 노드가 왼쪽 자식
		if (node.parent.isLeftChild) // 부모 노드가 왼쪽 자식 -> 조부모 노드를 우측회전
			rightRotate(node.parent.parent);
            // 이 후 node는 child 입장에서 구한다
			node.black = false;
			node.parent.black = true;
			if(node.parent.right != null)
				node.parent.right.black = false;
			return;
		}
        
		// 부모 노드가 오른쪽 자식 -> 조부모 노드를 우측-좌측 회전
		rightleftRotate(node.parent.parent);
        // 이 후 node는 child 입장에서 구한다
		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.left != null)
				node.parent.left.black = false;
			return;
		}
        
		// 부모 노드가 오른쪽 자식 -> 조부모 노드를 좌측-우측 회전
		leftrightRotate(node.parent.parent);
		node.black = true;
		node.left.black = false;
		node.right.black = false;
		return;
	}
}

:조건문에서 return을 사용하여 나오는 경우, else 작성을 요구하지 않는다

• 다시 한 번!
  <회전 조건과 결과>
  조건)
  left-left시, R rotation
  right-right시, L rotation
  left-right시, RL rotation
  right-left시, LR rotation
  결과)
  parent:black, children: red