[알고리즘] AVL 트리

[알고리즘] AVL 트리

- AVL 트리

러시아의 수학자 Adelson - Velskii 와 Landis가 고안한 높이 균형 이진 탐색 트리

오른쪽 서브트리와 왼쪽 서브트리의 높이 차가 2이상 이 되면 회전을 통해 트리의 높이 차를 1이하로 유지

이 되면 회전을 통해 트리의 높이 차를 1이하로 유지 높이차 = 오른쪽 서브트리의 높이 - 왼쪽 서브트리의 높이

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

- AVL 트리의 높이 차

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

경우 1: 높이 차 2인 노드부터 삽입 경로 전까지의 모양이 1자 인 경우 -> 단일 회전 단일 회전: 가운데 숫자가 위로 올라가면서, ㅅ자 모양 으로 회전

높이 차 2인 노드부터 삽입 경로 전까지의 모양이 인 경우 -> 단일 회전 경우 2: 높이 차 2인 노드부터 삽입 경로 전까지의 모양이 >, < 자 인 경우 -> 이중 회전 이중 회전:

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

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

높이 차 2인 노드부터 삽입 경로 전까지의 모양이 인 경우 -> 이중 회전

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

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

- AVL 트리의 구축 과정

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

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

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

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

이중 회전:

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

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

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

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

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

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

from http://hye0.tistory.com/41 by ccl(A) rewrite - 2021-10-24 04:01:15