[자료구조] 자바 트리 회전 소개 및 구현

https://www.youtube.com/playlist?list=PLpPXw4zFa0uKKhaSz87IowJnOTzh9tiBk

Data Structures

 

Rob Edwards 교수님의 CS310 Data Structures in Java를 공부하고 정리한 내용입니다.

 

부스트 코스 자바로 구현하고 배우는 자료구조에서도 학습할 수 있습니다.

 

트리의 불균형에 대해 알아보고, 회전으로 균형된 트리를 만드는 법을 학습합니다. 경우의 수를 나눠 rotate를 구현합니다.

---

회전 소개 및 구현

트리의 장점 중 하나는 탐색 시 시간복잡도가 O(logn)라는 것이다. 그런데 아래 그림과 같이 트리가 unbalance하면 최악의 경우 시간복잡도가 O(n)이다. 트리가 한쪽으로 치우친 경우 회전을 통해 균형잡힌 트리로 재구성할 수 있다.

 

불균형 트리

 

1. 불균형이 왼쪽 자식의 왼쪽 서브트리에서 나타날 때

 

right rotation

 

크기 관계는 (grandparent > parent > child)이다. right rotation을 통해 조부모 노드를 부모 노드의 오른쪽 자식 노드 위치로 옮긴다. 구현 단계는 다음과 같다.

 

Right Rotation 과정 1. 왼쪽 위 2. 오른쪽 위 3. 왼쪽 아래 4. 오른쪽 아래

 

1. 중간 크기 노드(6)을 temp로 지정한다.

2. 조부모(8)의 왼쪽 자식 노드를 temp의 오른쪽 자식으로 지정한다.

3. temp의 오른쪽 자식을 조부모(8)로 지정한다.

4. temp(6)을 조부모로 사용한다. temp를 return

 

기억할 점은 입력 node는 조부모 노드이다. 그리고 새로운 조부모 노드 temp를 반환한다.

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

 

 2. 불균형이 오른쪽 자식의 오른쪽 서브트리에서 나타날 때

 

left rotation

 

left rotation을 통해 조부모 노드 4을 6의 왼쪽 자식 노드로 옮긴다.

 

left rotation 과정

 

위의 right rotation과 같다.

1. 중간 크기 노드(6) 을 temp로 지정한다.

2. 조부모(4)의 오른쪽 자식을 temp(6)의 왼쪽 자식으로 지정한다.

3. temp의 왼쪽 자식을 조부모(4)로 지정한다.

4. temp(6)을 조부모로 사용하고 temp를 return

 

마찬가지로 아래 코드의 입력 노드는 조부모 노드이다. 그리고 새로운 조부모 노드 temp를 반환한다.

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

 

3. 불균형이 오른쪽 자식의 왼쪽 서브트리에서 나타날 때

 

1. right rotation of parent 2. left rotation of grandparent

 

rotation을 두 번 사용한다. 앞의 경우와 다르게 조부모보다 먼저 부모노드를 회전시킨다. 부모노드(8)을 왼쪽 자식 노드(6) 오른쪽 자식으로 옮긴다. 그리고 불균형이 4를 기준으로 오른쪽 자식의 오른쪽 서브트리에서 일어나므로 leftRotate를 호출한다.

 

1. Parent를 Right Rotation

2. GrandParent를 Left Rotation

 

입력 노드 : 조부모 노드 (4)

출력 노드 : 새로운 조부모 노드 (6)

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

 

4. 불균형이 왼쪽 자식의 오른쪽 서브트리에서 나타날 때

 

1. right rotation of parent 2. left rotation of grandparent

 

위와 같은 원리로

1. Parent를 left Rotation

2. GrandParent를 right Rotation

 

입력 노드 : 기존 조부모 노드 (8)

출력 노드 : 새로운 조부모 노드 (6)

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