자료구조/알고리즘 - AVL 트리

 

패스트 캠퍼스 - 컴퓨터 공학전공 - 소프트웨어 베이직 - 자료구조와 알고리즘

 

 

 

 

자료구조와 알고리즘 - 탐색 - AVL 트리

 

1. AVL 트리 : 균형이 갖춰진 이진트리 (binary tree)

2. 완전 이진트리는 검색에 있어 O(logN)의 시간복잡도

3. AVL트리는 간단한 구현을 통해 특정 이진트리가 완전이진트리에 가까운 형태를 유지하도록 함

 

 

 

* AVL 트리는 균형 인수(Balance Factor) 개념을 이용

 

AVL 트리의 각 노드는 '균형인수'를 계산하기 위해 자신의 '높이(Height)'값을 갖는다.

 

균형 인수 = | 왼쪽 자식 높이 - 오른쪽 자식 높이 |

-> 균형인수가 2 이상일 때, 문제가 있다고 판단

 

 

=> AVL 트리는 모든 노드에 대한 균형인수가 +1, 0, -1 인 트리를 의미

균형인수가 위의 값에 해당하지 않는 경우 '회전(Rotation)'을 통해 트리 재구성

 

 

 

 

* AVL 트리의 회전 (4가지)

 

균형인수가 깨지는 노드를 X라고 가정했을 때,

 

1. LL 형식 : X의 왼쪽 자식의 왼쪽에 삽입하는 경우

2. LR 형식 : X의 왼쪽 자식의 오른쪽에 삽입하는 경우

3. RR 형식 : X의 오른쪽 자식의 오른쪽에 삽입하는 경우

4. RL 형식 : X의 오른쪽 자식의 왼쪽에 삽입하는 경우

 

 

 

ex) AVL 트리의 LL회전 조건

 

fastcampus 강의자료

 

위의 트리에서

LL형식이 발생했을 경우, 

 

 

 

X  노드의 균형인수가 2가 된다.

 

 

이러한 방식으로 AVL 트리에서 어떤 형식이 발생할 경우

각 회전조건을 충족시키게 된다.

 

 

 

 

** LL 회전

fastcampus 강의자료

fastcampus 강의자료

 

 

** LR 회전

 

 

fastcampus 강의자료

fastcampus 강의자료

 

fastcampus 강의자료

 

 

 

* AVL트리의 균형잡기

 

균형잡기는 각 노드가 '삽입'될 때마다 수행되야 한다.

삽입과정에 소요되는 시간복잡도는 O(logN)이기 때문에

각 트리의 균형잡기는 삽입 시 거치는 모든 노드에 대해 수행된다는 점에서 O(1)의 시간복잡도를 가져야 한다.

 

 

 

* AVL 트리의 삽입, 출력

 

삽입과정은 일반적인 이진탐색트리와 흡사하지만,

삽입 시 거치는 모든 노드에 대해 균형잡기를 수행해야 한다.

 

트리를 출력할 때는 트리구조를 적절하게 보여줄 수 있는 방식을 택해야 하는데,

일반적으로 트리의 너비가 높이보다 크다는 점에서 세로 방향으로 출력하는 함수를 구현한다고 한다.

 

 

 

 

 

 

- AVL 트리 구현하기

 

 

fastcampus 강의자료

 

 

 

 

*높이, 균형인수 계산

 

 

fastcampus 강의자료

 

 

 

*회전

 

fastcampus 강의자료

 

 

* 균형잡기

 

fastcampus 강의자료

 

 

 

* 삽입

 

 

fastcampus 강의자료

 

 

* 출력 & AVL 트리 이용

 

 

fastcampus 강의자료

 

 

 

 

강의내용의 코드를 출력한 결과이다.

완전이진트리에 가깝게 출력된 것을 볼 수 있다.

 

 

 

 

 

**

편향 이진트리의 탐색은 O(N)의 시간복잡도를 갖는다.

AVL트리를 이용한 탐색에는 O(logN)의 시간복잡도를 유지할 수 있다.