5-3) 트리 - 회전

 

아래 내용은 부스트코스 <자바로 구현하고 배우는 자료구조> 강의를 들으며 정리한 것입니다.

 

회전

균형(balance) 잡힌 트리를 만들기 위해 트리의 노드 위치를 바꾸는 과정이다. 

균형 잡히지 않은 트리

 

위처럼 마치 연결리스트와 같이 한 방향으로 나열된 트리는 구조 자체는 문제없이 가능하나 탐색에 걸리는 시간 복잡도가 O(n)이 되어버린다. 본래 일반적으로 균형이 잡힌 이진트리에서 요소를 탐색하는 시간 복잡도가 O(log n)인 것과 대조하여 위와 같은 트리는 매우 비효율적이다. 따라서 회전을 통해 트리를 균형 있게 만들 수 있다.

 

트리에서 부모 노드보다 작은 데이터가 왼쪽 자식 노드에 와야 하고, 더 큰 데이터가 오른쪽 자식 노드에 와야하므로 트리가 한 쪽으로 치우친 경우 다음과 같이 조부모 노드, 부모 노드, 자식 노드의 크기 관계에 따라 우측 회전, 혹은 좌측 회전을 한다. 

 

---

 

 

1. 우측 회전 : 불균형이 왼쪽 서브트리 왼쪽 자식에게서 발생

조부모 > 부모 > 자식

불균형의 원인이 된 노드의 조부모 노드를 부모 노드의 오른쪽 자식 노드 위치로 옮긴다.

 

---

 

2. 좌측 회전: 불균형이 오른쪽 서브트리 오른쪽 자식에게서 발생

조부모 < 부모 < 자식

불균형의 원인이 된 노드의 조부모 노드를 부모 노드의 왼쪽 자식 노드 위치로 옮긴다.

 

위와 같이 트리를 재정렬하면 항상 중간 크기의 요소가 가장 위에 있는 루트가 된다.

 

---

 

트리가 한 쪽으로 치우치지 않은 경우, 두 번 회전하여 우측 회전과 좌측 회전을 모두 사용해 불균형을 해소한다. 

 

3. 불균형이 오른쪽 자식의 왼쪽 서브트리에 발생

부모 > 자식 > 조부모

부모 노드를 우측 회전 시킨 후 조부모를 좌측 회전한다.

 

---

 

4. 불균형이 왼쪽 자식의 오른쪽 서브트리에 발생

부모 > 조부모 > 자식

부모 노드를 좌측 회전 시킨 후 조부모를 우측 회전한다.

 

---

 

회전: 코드 구현

좌측 회전과 우측 회전은 아래와 같이 임시 포인터를 활용하여 조부모 노드 node를 왼쪽 자식, 오른쪽 자식 노드 위치로 옮긴다.

// 좌측 회전: 조부모 노드를 부모 노드의 왼쪽 자식 노드 위치로 옮김
public Node<E> leftRotate (Node<E> node){
	Node<E> tmp = node.right; // set temp=grandparents right child
	node.right = tmp.left; // set grandparents right child=temp left child
	tmp.left = node; // set temp left child=grandparent 
	return tmp; // use temp instead of grandparent
}

// 우측 회전: 조부모 노드를 부모 노드의 오른쪽 자식 노드 위치로 옮김
public Node<E> leftRotate (Node<E> node){
	Node<E> tmp = node.left; 
	node.left = tmp.right; 
	tmp.right = node; 
	return tmp;
}