자료구조의 정리와 이해(AVL 트리) 균형트리

AVL트리는 트리가 한쪽으로 치우쳐 자라나는 현상을 방지하여 트리 높이의 균형을 유지하는 이진탐색트리

Balanced 이진탐색트리를 만들면 N개의 노드를 가진 트리의 높이가  O(logN)이 되어 탐색,삽입,삭제 연산의

수행시간이  O(logN)이 보장된다.

 

-Linked List

구현이 쉬움

많은 포인터를 저장

O(N) 시간복잡도를 가짐

- Binary Search Tree

탐색의 O(N) 시간 복잡도를  O(logN) 시간복잡도로 줄임

Unbalanced Tree일 경우 탐색의 속도는 느려짐

- Balanced Binary Tree(AVL Tree,Red-Black Tree)

균형을 이루도록 보장

항상 O(logN)의 시간 복잡도를 보장

---

AVL Tree의 특성

1. 이진탐색트리 연산 실행시간은 이진탐색트리의 높이에 따라 달라지는데 최상의 성능을 얻으면

트리의 균형을 유지해야한다.

2.AVL트리에서 노드의 두 하위 트리(왼쪽,오른쪽)의 높이의 차이가 최대 1을 넘지말아야합니다.

3. AVL트리는 엄격하게 균형을 유지하기 때문에 Red-Black 트리보다 더 빠른 성능을 가지지만

더 많은 작업을 수행해야만 한다.

4. 특히 운영체제의 경우 이러한 자료구조에 의존한다.

5. 대부분의 연산은 이진탐색트리와 동일하다.

6. 이진 탐색트리와 동일하게 모든 노드는 최대 2개의 자식노드를 가질수 있고,

왼쪽 자식노드는 부모노드보다 작고,오른쪽 자식노드는 크다.

7. 삽입 연산의 경우 이진탐색트리와 동일하지만 모든 삽입 연산은 트리가 균현을 유지하는지 확인을 해야한다.

8.삭제,최대/최소 반환 연산 또한 마찬가지이다.

---

AVL Tree 연산

연산의 시간복잡도

AVL 트리의 기본연산은 이진 탐색트리와 동일하지만 아래의 표를 보면 시간복잡도가 다르다.

 

탐색

AVL트리의 탐색은 이진트리와 동일하다.

높이

AVL트리의 연산을 수행하고, 불균형이 발생하면 회전을 통해 균현을 다시 맞춘다.

이렇게 균형을 맞추기 위해서는 각 노드들의 높이를 알아야만 한다.

그렇기 때문에 각 노드의 높이를 계산하는 과정을 이해하는 것이 중요하다.

노드의 높이는 특정 노드로부터  leaf노드까지 가장 긴 경로의 길이를 말한다.

height = max(leftChild.height(), rightChild.height()) + 1

특정 노드의 높이를 계산하는 방법은 위와같은 코드를 통해 계산할수 있다.

- 특정 노드의 왼쪽,오른쪽 자식노드의 높이 중에서 가장 큰 값을 1을 더한 값이 특정 노드의 높이가 된다.

- leaf노드는 null인 자식노드를 가지고 있는데 이런 경우 자식 노드의 높이는 -1로 간주한다.

회전

AVL트리에서 삽입,삭제 연산을 수행할 때 트리의 균형을 유지하지 위해 LL-회전,RR-회전,LR- 회전,RL-회전 연산이

사용된다.

• rightRotate() : 오른쪽 방향으로 회전

• leftRotate() : 왼쪽 방향으로 회전

rightRotate() 은 왼쪽 방향의 서브트리가 높아서 불균형이 발생할 때 서브트리를 오른쪽 방향으로 회전하기

위한 메소드이고, leftRotate() 는 오른쪽 방향의 서브트리가 높아서 불균형이 발생했을 때 왼쪽방향으로 회전하기 위한

메소드이다