[알고리즘] AVL 트리

AVL 트리

• 러시아의 수학자 Adelson - Velskii 와 Landis가 고안한 높이 균형 이진 탐색 트리
• 오른쪽 서브트리와 왼쪽 서브트리의 높이 차가 2이상이 되면 회전을 통해 트리의 높이 차를 1이하로 유지
• 높이차 = 오른쪽 서브트리의 높이 - 왼쪽 서브트리의 높이

이진 탐색 트리를 기반으로 하기 때문에 삽입 시엔 이진 트리 처럼 노드를 삽입한다. 

 

AVL 트리의 높이 차

 

 

AVL 트리에선 노드 삽입 시, 회전이 필요한  경우 2가지가 있습니다.

• 경우 1: 높이 차 2인 노드부터 삽입 경로 전까지의 모양이 1자인 경우 -> 단일 회전
  • 단일 회전: 가운데 숫자가 위로 올라가면서, ㅅ자 모양으로 회전
• 경우 2: 높이 차 2인 노드부터 삽입 경로 전까지의 모양이 >, < 자인 경우 -> 이중 회전
  • 이중 회전:
    - 1회전: 맨 아래에 위치한 노드를 한 칸 위(부모 노드)로 올려주어 1자 모양로 만듦
    - 2회전: 가운데 숫자가 위로 올라가면서, ㅅ자 모양으로 회전

     * 여러 개의 높이 차 2인 노드가 존재 시엔. 루트부터 가장 먼 2부터 시작한다. 

 

(어려운 용어보단 모양으로 설명하는 것이 이해가 더 잘되어서 용어 생략 하였습니다. )

 

---

AVL 트리의 구축 과정

삽입 과정 및 회전 과정을 차근차근 설명해보겠습니다.

2, 1, 8, 9, 7, 3, 6, 4, 5

3 삽입 시 이중 회전이 일어난다. 

아래 그림은 이중 회전이 일어나는 과정을 차근차근 그려본 결과 입니다. 

 

이중 회전:

- 1회전: 맨 아래에 위치한 노드를 한 칸 위(부모 노드)로 올려주어 1자 모양로 만듦

- 2회전: 가운데 숫자가 위로 올라가면서, ㅅ자 모양으로 회전

4 삽입 시 이중 회전이 일어난다. 

5삽입 시, 단일 회전이 일어난다.

단일 회전: 가운데 숫자가 위로 올라가면서, ㅅ자 모양으로 회전

 

 

 

 

 

틀린 내용이 있거나, 이해가지 않는 부분이 있다면 댓글로 남겨주세요.