비선형 데이터구조, 트리(Tree) #10 이진탐색트리의 회전(Rotate)

개요

이번글에서는 이진 탐색 트리의 회전에 대해서 소개하겠습니다.

 

1. 회전(Rotate) 소개

이진 탐색 트리의 대표적인 특징은 특정 노드를 기준으로 노드보다 작은 값은 왼쪽 자식에 위치하고 큰 값은 오른쪽 자식에 위치합니다. 따라서 이진 탐색 트리는 아래와 같이 저장될 수 있습니다.

위 그림의 이진 탐색 트리는 매우 안정적인 이진 탐색 트리입니다. 하지만 아래와 같은 트리도 이진 탐색 트리가 될 수 있습니다.

위와 같은 트리도 이진 탐색 트리가 되지만 탐색시 시간복잡도는 O(n)가 소요됩니다. 위와 같은 이진 탐색 트리는 균형이 잡혀 있지 않다고 합니다. 따라서 회전 기능은 균형 잡혀있지 않은 트리를 균형 있는 트리로 변환할 수 있도록 도와주는 기능입니다. 회전 기능에는 대표적으로 왼쪽 회전(Left Rotate), 오른쪽 회전(Right Rotate)가 존재합니다.

 

1.1 왼쪽 회전(Left Rotate)

왼쪽 회전은 오른쪽으로 균형이 쏠린 트리를 균형을 맞추어 주는 기능입니다. 왼쪽 회전의 과정은 아래 그림과 같습니다.

 

1.2 오른쪽 회전(Right Rotate)

오른쪽 회전은 왼쪽으로 균형이 잡혀있지 않은 트리를 균형있게 맞추어주는 기능입니다. 오른쪽 회전의 수행과정은 아래 그림과 같습니다.

 

2. 회전(Rotate)

위에서 한쪽으로 쏠린 트리의 왼쪽 회전, 오른쪽 회전을 통해서 트리의 균형을 맞춘 것을 보았습니다. 하지만 위의 케이스만이 아니라 다른 케이스가 존재합니다. 그것은 한쪽으로 치우치지 않고 불균형한 경우입니다. 아래 그림의 두 트리가 한쪽으로 치우지지는 않지만 불균형한 트리라고 볼 수 있습니다.

위와 같은 불균형한 트리는 왼쪽 회전과 오른쪽 회전을 1번만 사용해서 균형있는 트리를 사용할 수 없습니다. 즉, 왼쪽 회전과 오른쪽 회전을 같이 사용해서 문제를 해결해야 합니다.

 

2.1 불균형이 오른쪽 자식의 왼쪽 서브트리에서 나타날 경우

위와 같이 20을 기준으로 오른쪽 회전을 수행하고 다시 10을 기준으로 왼쪽 회전을 수행하여 균형 잡힌 트리로 만듭니다.

 

2.1 불균형이 왼쪽 자식의 오른쪽 서브트리에서 나타날 경우

위와 같이 5를 기준으로 왼쪽 회전을 수행하고 10을 기준으로 오른쪽 회전을 수행하여 균형 잡힌 트리를 만듭니다.

 

3. 회전(Rotate) 구현

다음과 같이 임시 포인터를 사용하여 왼쪽 회전, 오른쪽 회전을 구현합니다.

	public Node<E> leftRotate(Node<E> node)
	{
		Node<E> temp = node.right;
		
		node.right = temp.left;
		temp.left = node;
		
		return temp;	
	}
	
	public Node<E> rightRotate(Node<E> node)
	{
		Node<E> temp = node.left;
		
		node.left = temp.right;
		temp.right = node;
		
		return temp;
	}

 

위와 같이 한쪽으로 쏠린 트리를 왼쪽 회전, 오른쪽 회전으로 균형있게 할 수도 있지만 한쪽으로 쏠리지 않고 불균형한 트리는 왼쪽회전, 오른쪽 회전을 모두 사용하여야 합니다.

	public Node<E> leftRightRotate(Node<E> node)
	{
		node.left = leftRotate(node.left);
		return rightRotate(node);
	}
	
	public Node<E> rightLeftRotate(Node<E> node)
	{
		node.right = rightRotate(node.right);
		return leftRotate(node);
	}

 

References

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