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

이전글

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

비선형 데이터구조, RedBlackTree #1 RedBlackTree의 규칙 및 수행과정

 

개요

이전글에서는 RedBlackTree가 불균형 하였을때 트리를 Rebalance하는 연산들에 대해서 알아보았습니다. 이번글에서는 RedBlackTree의 add 메서드와 Rebalance(correctTree) 메서드를 구현하겠습니다.

 

1. add 메서드

add 메서드의 동작 방식은 AVL 트리와 동일합니다. 단, isLeftChild가 추가되기 때문에 이를 고려해주어야 합니다.

	public void add(K key, V value)
	{
		Node<K,V> newNode = new Node<K,V>(key,value);
		
		// 트리가 비었을 경우
		if(root==null)
		{
			root = newNode;
			root.black = true;
			size++;
			return;
		}
		
		// 트리에 노드가 있을 경우 재귀 메서드 사용
		add(root, newNode);
		size++;
	}

	// add 재귀함수
	private void add(Node<K,V> parent, Node<K,V> newNode)
	{
		// newNode.data < parent.data
		if(((Comparable<K>)newNode.key).compareTo(parent.key)<=0)
		{
			if(parent.left==null)
			{
				parent.left = newNode;
				newNode.parent = parent;
				newNode.isLeftChild = true;
				return;
			}
			add(parent.left, newNode);
			return;
		}
		// newNode.data > parent.data
		else if(((Comparable<K>)newNode.key).compareTo(parent.key)>0)
		{
			if(parent.right==null)
			{
				parent.right = newNode;
				newNode.parent = parent;
				newNode.isLeftChild = false;
				return;
			}
			add(parent.right, newNode);
			return;
		}
		
		checkColor(newNode);
	
	}

• newNode 노드와 parent 노드의 데이터를 비교하여 왼쪽, 오른쪽 자식 노드로 이동합니다.
• 왼쪽 또는 오른쪽 자식이 null이라면 newNode를 추가합니다.
• parent 포인터가 있으므로 newNode의 parent 포인터는 parent를 가리킵니다.
• 그리고 왼쪽 자식에 추가되었으면 newNode의 isLeftChild는 true, 오른쪽 자식이라면 false를 저장합니다.
• 노드를 추가한 후 RedBlackTree가 규칙에 맞는지 검사하기 위해 checkColor 메서드를 호출합니다.

2. checkColor 메서드

checkColor 메서드는 노드를 트리의 규칙에 맞게 추가한 후, 레드 블랙 트리의 6가지 규칙을 만족하는지 확인해주는 메서드입니다.

 

	private void checkColor(Node<K, V> node) {
		// 루트는 항상 검은색이므로 색을 확인할 필요가 없음
		if(node==root)
		{
			return;
		}
		// Red 노드가 2개가 연속으로 나오는 경우(레드 블랙 트리 규칙 위반)
		if(!node.black && !!node.parent.black)
		{
			correctTree(node);
		}
		// 부모 노드를 계속 확인합니다.
		checkColor(node.parent);
		
	}

• 레드 블랙 트리의 대표적인 규칙 위반 케이스는 새로 추가된 노드와 부모 노드가 연속으로 Red인 경우입니다. 이와 같은 경우 correctTree 메서드를 호출하여 회전 또는 색상 변환을 수행합니다.
• correctTree 메서드를 호출하였음에도 부모 노드와 조부모 노드가 또다시 연속으로 Red일 가능성이 있기 때문에 재귀적으로 checkColor 메서드를 호출합니다.

 

3. correctTree 메서드

회전을 수행하고 난 후 또는 이모 노드가 Red여서 색상을 변환할 때 부모 노드와 자식 노드들의 색상은 아래 그림과 같습니다.

 

correctTree 메서드는 위반된 레드 블랙 트리를 회전 또는 색상 변환을 통하여 규칙을 만족하도록 교정하는 메서드입니다.

	private void correctTree(Node<K, V> node) {
		// node의 부모 노드 = 왼쪽 자식, node의 이모 노드 = 오른쪽 자식
		if(node.parent.isLeftChild)
		{
			// 이모 노드가 검은색(이모 노드가 null인 경우도 포함)
			if(node.parent.parent.right == null || node.parent.parent.right.black)
			{
				//회전
				rotate(node);
				return;
			}
			// 이모 노드가 빨간색
			if(node.parent.parent.right!=null)
			{
				// 색상 변환
				node.parent.parent.right.black = true;
			}
			node.parent.parent.black = false;
			node.parent.black = true;
			return;
		}
		// node의 부모 노드 = 오른쪽 자식, node의 이모 노드 = 왼쪽 자식
		else
		{
			// 이모 노드가 검은색(이모 노드가 null인 경우 포함)
			if(node.parent.parent.left==null || node.parent.parent.left.black)
			{
				rotate(node);
				return;
			}
			// 이모 노드가 빨간색
			if(node.parent.parent.left!=null)
			{
				// 색상 변환
				node.parent.parent.black = true;
			}
			node.parent.parent.black = false;
			node.parent.black = true;
			return;
		}
	}

• 노드를 회전을 할 것인지 색상 변환을 할 것인지를 판단하는 기준은 노드의 이모 노드의 색상이 Black, Red 여부입니다.
• 이모 노드가 Black : 회전 수행(rotate) 후 색상 변환(color flip)
• 이모 노드가 Red : 색상 변환(color flip)

 

4. rotate 메서드

rotate 메서드는 노드, 부모 노드, 조부모 노드의 형태에 따라 회전 수행을 달리합니다.

 

아래의 그림은 각 회전에 따른 node의 이동(부모 노드, 자식 노드로 이동)과 회전 후 색상 변환(color flip)을 그림으로 표현한 것입니다.

 

위 회전에 따른 알고리즘은 다음과 같습니다.

	private 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;
			}
			// 부모 노드가 오른쪽 자식
			else
			{
				rightLeftRotate(node.parent.parent);
				node.black = true;
				node.right.black = false;
				node.left.black = false;
				return;
			}
		}
		// 현재 노드가 오른쪽 자식
		else
		{
			// 부모 노드가 왼쪽 자식
			if(node.parent.isLeftChild)
			{
				leftRightRotate(node.parent.parent);
				node.black = true;
				node.right.black = false;
				node.left.black = false;
			}
			// 부모 노드가 오른쪽 자식
			else
			{
				leftRotate(node.parent.parent);
				node.black = false;
				node.parent.black = true;
				if(node.parent.left!=null)
				{
					node.parent.left.black = false;
				}
				return;
			}
		}
	}

 

References

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