AVL 트리 - 성질/삽입방법/활용

탄생 계기

편향 트리

 

이진탐색트리는 위 그림과 같이 한쪽으로 노드가 쏠릴 수가 있는 문제점이 있다. 10,9,8,7,6을 순서대로 삽입한다고 생각해보면 저런 형태의 트리가 만들어진다는 것을 알 수 있을 것이다. 이런 트리를 편향 트리라 하는데 이러한 형태에서 특정 값을 찾으려면 O(N)의 시간이 필요하다. 예를 들어 6을 찾으려면 모든 노드를 탐색해야지 찾을 수 있다. 따라서 성능이 매우 나빠지게 된다. 

 

이진 탐색 트리 (BST-Binary Search Tree)

 

이런 단점을 극복할 수 있는 자료구조가 자가균형 이진탐색트리인데 이 중 하나는 AVL트리이다. 위의 편향트리를 AVL트리로 재구성하면 다음과 같다. 이렇게 된다면 어떤 노드를 탐색하든 O(logn)으로 탐색할 수 있다. 

 

 

 

 

 

AVL 트리 성질

 

• 이진 탐색 트리의 속성을 가진다.
• 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다. 
• 높이 차이가 1보다 커지면 ★회전(Rotation)을 통해 균형을 맞춰 높이 차이를 줄인다. (높이 차이를 Balance Factor(BF)라 한다. BF = 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이) 
• 삽입, 검색, 삭제의 시간 복잡도가 O(log N)이다. (N : 노드의 개수)

 

 

회전에 대해 설명하기 전에 T1, T2..등은 서브트리를 의미하고, 회전의 기준은 z노드라고 가정한다. 

 

 

우회전 (Right Rotation)

 

 

 

1. y노드의 오른쪽 자식 노드를 z노드로 변경한다.
2. z노드 왼쪽 자식 노드를 y노드의 오른쪽 서브트리(T2)로 변경한다.

 

 

 

좌회전 (Left Rotation)

 

 

1. y노드의 왼쪽 자식 노드를 z노드로 변경한다.
2. z노드 오른쪽 자식노드를 y노드의 왼쪽 서브트리(T2)로 변경한다.

 

 

 

AVL 트리는 LL, LR, RL, RR 4가지의 균형이 무너진 경우가 존재한다. 각각 해결법을 설명한다.

 

 

 

LL (Left Left)

 

위 그림처럼 BF가 -1~1을 벗어난 노드를 기준으로 왼쪽, 왼쪽 노드가 존재한다면 LL Case이다.

이때 해당 노드를 기준으로 우회전을 적용하면 불균형이 해소된다.

 

 

 

RR (Right Right)

 

 

 

위 그림처럼 BF가 -1~1을 벗어난 노드를 기준으로 오른쪽, 오른쪽 노드가 존재한다면 RR Case이다.

이때 해당 노드를 기준으로 좌회전을 적용하면 불균형이 해소된다.

 

 

 

LR (Left Right)

 

 

 

위 그림처럼 BF가 -1~1을 벗어난 노드를 기준으로 왼쪽, 오른쪽 노드가 존재한다면 LR Case이다.

이때 먼저 BF에 이상이 있는 노드(값이 4인노드)의 왼쪽 자식노드(값이 2인 노드)를 기준으로 좌회전을 진행한다.

이후 BF에 이상이 있는 노드(값이 4인 노드)를 기준으로 우회전을 진행하면 불균형이 해소된다.

 

 

 

RL (Right Left)

 

 

 

위 그림처럼 BF가 -1~1을 벗어난 노드를 기준으로 오른쪽(Right), 왼쪽(Left) 노드가 존재한다면 RL Case이다.

이때 먼저 BF에 이상이 있는 노드(값이 4인노드)의 오른쪽 자식노드(값이 4인 노드)를 기준으로 우회전을 진행한다.

이후 BF에 이상이 있는 노드(값이 4인 노드)를 기준으로 좌회전을 진행하면 불균형이 해소된다.

 

 

 

활용

 

1) 데이터베이스 시스템에서 쿼리 실행 계획을 생성하는 인덱스 구조를 작성할 때

2) 자연어 처리 분야에서 문자열 검색 및 검색 결과의 정확도 개선이 필요할 때

3) 게임 개발에서 오브젝트와의 충돌을 일관성있게 검사할 때 

 

AVL 트리는 삽입과 삭제, 검색이 모두 O(logn)에 이루어지지만,

트리의 구현이 어렵고 균형 트리에 최적화된 B-tree가 존재하기에 상대적으로 덜 사용되고 있다.

 

---

 

※ AVL트리 시뮬레이터

AVL Tree Visualzation