AVL 트리 (AVL Tree)

AVL 트리

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

노드의 두 하위 트리(왼쪽, 오른쪽)의 높이의 차이가 최대 1을 넘지 않음
엄격하게 균형을 유지하기 때문에 Red-black 트리보다 더 빠른 성능을 가지지만 더 많은 작업이 필요
대부분의 연산은 이진탐색트리와 동일
삽입 삭제 연산은 트리가 균형을 유지하는지 확인

Linked List, Binary Search Tree, Balanced Binary Tree 차이점

1. Linked List

- 구현이 쉬움
- 많은 포인터(참조)를 저장
- O(N) 시간복잡도를 가짐

2. Binary Search Tree

- 탐색의 O(N) 시간복잡도를 O(logN) 시간복잡도로 줄임
- Unbalanced Tree일 경우 탐색의 속도는 느려짐

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

- 균형을 이루도록 보장
- 항상 O(logN)의 시간복잡도를 보장

 

시간 복잡도

이진 탐색 트리

공간 : 평균 O(N),      최악 O(N)
삽입 : 평균 O(logN),  최악(N)
삭제 : 평균 O(logN),  최악(N)
탐색 : 평균 O(logN),  최악(N)

AVL 트리

공간 : 평균 O(N),      최악 O(N)
삽입 : 평균 O(logN),  최악(logN)
삭제 : 평균 O(logN),  최악(logN)
탐색 : 평균 O(logN),  최악(logN)

탐색

이진트리와 동일한 방식으로 진행
최솟값 찾기 => 왼쪽 노드 방향으로 탐색
최댓값 찾기 => 오른쪽 노드 방향으로 탐색

https://walbatrossw.github.io/data-structure/2018/10/26/ds-avl-tree.html

https://walbatrossw.github.io/data-structure/2018/10/26/ds-avl-tree.html

 

높이

https://walbatrossw.github.io/data-structure/2018/10/26/ds-avl-tree.html

높이 : 특정 노드부터 leaf 노드까지 가장 긴 경로의 길이

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

불균형 상태 : 하나의 노드를 기준으로 양쪽 서브트리의 높이 차이가 2 이상인 경우

불균형 상태인 경우 회전을 통해서 균형 상태로 맞춤

 

회전

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

왼쪽 방향의 서브트리가 높아서 불균형이 발생할 때 서브트리를 오른쪽 방향으로 회전
오른쪽 방향의 서브트리가 높아서 불균형이 발생했을 때 왼쪽 방향으로 회전

회전을 하더라도 중위 순회를 통한 노드 순회의 순서는 동일.
트리 구조의 불균형을 맞추는 작업만을 수행

1. 왼쪽으로 트리가 치우쳐진 경우 - LL

https://walbatrossw.github.io/data-structure/2018/10/26/ds-avl-tree.html

왼쪽 노드와 오른쪽 노드의 높이 차를 구함
A의 왼쪽 = -1, 오른쪽 = -1, 차 = 0
B의 왼쪽 = 0, 오른쪽 = -1, 차 = 1
C의 왼쪽 = 1, 오른쪽 = -1, 차 = 2

높이의 차가 2이상인 경우 불균형임을 판단 할 수 있음

왼쪽으로 치우쳐진 트리를 오른쪽으로 회전함

 

2. 오른쪽으로 트리가 치우쳐진 경우- RR

https://walbatrossw.github.io/data-structure/2018/10/26/ds-avl-tree.html

오른쪽으로 치우쳐진 트리를 왼쪽으로 회전함

3. 왼쪽 자식노드에 오른쪽 자식 노드만 있는 트리 - LR

https://walbatrossw.github.io/data-structure/2018/10/26/ds-avl-tree.html

왼쪽 자식노드에 오른쪽 자식 노드만 있는 경우
1. 왼쪽 자식 노드를 왼쪽으로 회전
2. 왼쪽으로 트리가 치우쳐진 모양이 되었으므로 오른쪽으로 회전

 

4. 오른쪽 자식 노드에 왼쪽 자식 노드만 있는 트리 - RL

https://walbatrossw.github.io/data-structure/2018/10/26/ds-avl-tree.html

오른쪽 자식 노드에 왼쪽 자식 노드만 있는 경우
1. 오른쪽 자식 노드를 오른쪽으로 회전
2. 오른쪽으로 트리가 치우쳐진 모양이 되었으므로, 왼쪽으로 회전

 

삽입

1. 이진 탐색 트리와 동일하게 삽입을 진행
2. 삽입한 노드부터 루트 노드까지 높이를 측정
3. 높이를 통해 불균형 노드일 경우 모양에 따라 회전 수행
4. 불균형이 없을 때까지 2~3을 반복

삭제

1. 삭제 할 노드가 leaf노드일 경우
1-1) 해당 노드를 삭제

2. 삭제 할 노드가 한 개의 자식 노드를 가지고 있는 경우
2-1) 자식 노드를 삭제할 노드의 부모에 연결
2-2) 삭제할 노드를 제거

3. 삭제 할 노드가 두 개의 자식 노드를 가지고 있는 경우

3-1) 왼쪽 노드의 가장 큰 값 또는 오른쪽 노드의 가장 작은 값을 삭제할 노드와 위치를 변경
3-2) 삭제할 노드를 제거

https://walbatrossw.github.io/data-structure/2018/10/26/ds-avl-tree.html

ex) 32를 제거할 경우
    왼쪽 노드에 가장 큰 값인 23과 위치를 변경
    바꾼 후 32 노드 제거

오른쪽 노드의 가장 작은 값 55에 해당 작업 수행 가능
삭제한 후에 노드가 불균형일 경우 회전 작업을 수행