[자료구조] Tree에 대하여(2) - 이진 검색 트리와 AVL 트리

1. BST (Binary Search Tree) : 이진 검색 트리

 Binary Tree에서는 검색 연산의 worst case가 O(n)의 복잡도를 가졌다. 하나의 노드를 찾는 데에는 모든 노드를 탐색했어야 하기 때문이다.

 BST(Binary Search Tree)에서는 제약을 둔다. 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값, 오른쪽에는 큰 값. 위 제약을 통하여 검색 연산에 대한 시간 복잡도를 O(log n)으로 줄일 수 있다.

Data Input에 따른 시간 복잡도, O(n) vs O(log n)

 사실 위 제약만으로는 검색 연산에서의 worst case가 O(n)으로 동일하다. (skew tree의 경우) 이는 BST를 밸런싱 작업을 통해 해결할 수 있으며 잠시 후 배우게 될 것이다.

 

1-1. 특징

 1. 노드의 왼쪽 서브 트리는 노드의 키 값보다 작은 키 값을 갖는 노드들로만 구성

 2. 노드의 오른쪽 서브 트리는 노드의 키 값보다 큰 키 값을 갖는 노드들로만 구성

 3. 왼쪽과 오른쪽 서브 트리 모두 BST

 

1-2. 주요 사항

 1. 루트 데이터가 항상 왼쪽 서브 트리 데이터와 오른쪽 서브 트리 데이터 사이에 있기 때문에 중위 탐색(Inorder)을 수행하면 정렬된 리스트가 만들어진다.

 2. 이진 검색 트리에 대한 문제를 풀 때 대부분의 경우, 왼쪽 서브 트리를 먼저 처리하고 루트 데이터를 처리한 다음 오른쪽 서브 트리를 처리한다. 즉, 중위 탐색(Inorder)을 수행한다.

 3. 어떤 항목을 검색할 때, 왼쪽 서브 트리의 데이터가 검색하는 항목보다 작으면 왼쪽 서브 트리 검색은 생략할 수 있다. 오른쪽 서브 트리에서도 같다. 이와 같은 이유로 시간 복잡도를 줄일 수 있는 것이다.

 

---

2. Balanced Binary Search Tree : 균형 이진 검색 트리

 BST는 평균적으로 O(log n)이나 최악의 경우(eg. skew tree) O(n)의 시간 복잡도를 갖는 것은 Binary Tree와 동일하다고 말했다.

 위 단점을 없애기 위한 트리로 균형 이진 검색 트리가 탄생했다.

 

 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차를 최소로 만들어주면 '균형 잡혔다'라고 할 수 있다. 높이의 차를 balanced factor, 균형 인자라고 부른다.

높이의 차가 0일 경우 완전 균형 이진 검색 트리라고 부르며 이는 이전 포스팅에서 배운 완전 이진 트리와 같은 개념을 생각하면 쉽다.

 

 균형 이진 검색 트리에는 여러가지 종류가 있다. AVL 트리, Red-Black 트리 등.

이번 포스팅에서는 가장 많이 사용되는 3. AVL 트리에 대하여 알아보도록 하겠다.

 

---

3. AVL 트리

 Abelson-Velskii와 Landis가 만든 트리

 Balanced factor인 양쪽 서브 트리의 높이 차가 1일 때를 AVL 트리라고 한다.

이진 검색 트리이면서, 어떤 노드 X에 대해서도 X의 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 최대 1이다.

 

 AVL 트리에서 구조가 변경 될 때, 즉 삽입이나 삭제가 이루어질 때 속성을 유지하려면 그때마다 트리를 수정해야한다.

이를 '트리의 균형이 깨졌다'라고 표현한다.

 

 트리의 균형이 깨질 경우 회전을 통하여 균형을 맞추게 되는데, 4가지 경우로 나눌 수 있다.

• LL 타입 : 왼쪽 서브 트리의 왼쪽 서브 트리에 삽입되는 경우
• LR 타입 : 왼쪽 서브 트리의 오른쪽 서브 트리에 삽입되는 경우
• RR 타입 : 오른쪽 서브트리의 오른쪽 서브 트리에 삽입되는 경우
• RL 타입 : 오른쪽 서브트리의 왼쪽 서브 트리에 삽입되는 경우

 회전을 한 번만 시킬 경우를 단순 회전(Single Rotation)이라고 하며, 이는 LL타입과 RR타입에 해당한다.

 회전을 두 번 시킬 경우를 이중 회전(Double Rotation)이라고 하며, 이는 LR타입과 RL타입에 해당한다.

 

3-1. LL 회전

 위 그림의 경우 노드 7에서 최대 높이의 차인 균형 인자가 2로 불균형한 상태이다.

이때 오른쪽으로 회전을 시키면, 즉 노드 7과 노드 6을 바꾸면 균형을 맞출 수 있다.

(LL 회전은 LL에 삽입된 것을 회전하는 말로 왼쪽으로 회전한다라는 것과 헷갈리면 안된다.)

 

 

3-2. RR 회전

 RR 회전은 LL 회전과 반대로 왼쪽으로 한번 회전하면 균형을 맞추게 된다.

 

3-3. LR 회전

 위 그림과 같이 왼쪽 서브 트리의 오른쪽에 노드 N이 삽입될 경우를 LR 타입(회전)이라고 한다.

이 경우에서는 B 기준으로 RR 회전을 먼저 진행하고, A 기준으로 LL 회전을 진행하면, 그림에서 3번째 형태와 같이 균형이 잡히게 된다.

 

3-4. RL 회전

 RL 회전은 LR 회전과 반대로 LL 회전을 먼저 진행하고, RR 회전을 진행하면 균형이 잡힌다. 반대되는 경우와 동일하기에 그림은 생략한다.

 

---