비선형 데이터구조, RedBlackTree #3 LeftRotate & LeftRightRotate 메서드

이전글

https://yonghwankim-dev.tistory.com/204

비선형 데이터구조, RedBlackTree #2 add 메서드

 

개요

이전글에서는 RedBlackTree의 add메서드와 Rotate 메서드를 구현하였습니다. 이번글에서는 LeftRotate 메서드를 구현하도록 하겠습니다.

 

1. LeftRotate 메서드

LeftRotate 메서드의 역할은 한쪽으로 기울어진 트리를 특정 노드를 왼쪽 자식으로 옮겨서 균형을 맞추어주는 역할을 수행합니다. LeftRotate 메서드는 아래 그림과 같이 수행됩니다.

RedBlackTree에서는 parent 포인터와 isLeftChild 변수로 인하여 이 변수들을 고려하여 구현하여야 합니다. 아래 그림은 이들을 고려한 LeftRotate 메서드의 수행과정을 그림으로 표현한 것입니다.

위의 그림을 코드로 구현하면 다음과 같습니다.

	private 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;
				node.parent.left = temp;	
			}
			else
			{
				temp.isLeftChild = false;
				node.parent.right = temp;
			}
			temp.left = node;
			node.isLeftChild = true;
			node.parent = temp;
		}
		
	}

 

2. Left-Right Rotate 메서드

Left-Right Rotate 메서드는 LeftRotate, RightRotate 메서드를 두번 사용하여 불균형한 트리를 균형있게 맞추는 메서드입니다. Left-Right Rotate 메서드의 수행과정을 그림으로 표현하면 아래와 같습니다.

위 수행과정을 코드로 표현하면 다음과 같습니다.

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

 

3. height 메서드

height 메서드는 본 RedBlackTree의 높이를 알려주는 메서드입니다.

public int height() {
		if(root==null)
		{
			return 0;
		}
		return height(root)-1;
	}
	private 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;
		}
		else
		{
			return rightheight;
		}	
	}

 

위와 같이 각각의 서브트리의 루트에서 재귀적으로 왼쪽과 오른쪽 서브트리의 높이를 호출하여 가장 높은 높이를 반환합니다.

 

4. black 노드의 개수

blackNodes 메서드의 기능은 RedBlackTree의 Black 노드의 개수를 알려주는 메서드입니다.

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

 

References

source code : https://github.com/yonghwankim-dev/DataStruct/tree/main/Tree/red_black_tree
[부스트코스] 자바로 구현하고 배우는 자료구조