AVL 트리란?

이진 트리의 문제점

이진 트리의 문제점은 한쪽으로 치우친 형태로 트리 구조가 만들어질 수 있다는 것이다. 이렇게 되면 트리 구조가 아닌 일반적인 연결 리스트와 별 차이가 없는 구조가 되어 이진 트리의 장점을 발휘할 수 없게 된다.

 

편향 트리

이와 같이 이진 트리가 구성되면 검색 시 성능이 O(logN)이라는 이진 트리의 장점을 보장할 수 없게 된다. 최악의 경우에는 성능이 O(N)이 되기도 한다.

 

AVL 트리

AVL 트리는 전체 트리의 구조가 균형이 맞도록 하는 트리이다. 즉, 트리 구조가 한쪽으로 쏠리는 것을 막고자 하는 것이 가장 기본적인 개념이다. G.M Adelson-Velski와 E.M Landi 두 사람이 발표한 논문에서 유래되었고 발표한 사람의 이름 첫 글자를 모아 AVL 트리라고 이름 지어졌다.

AVL 트리의 특징

1. 균형도라는 개념이 있다.

2. 리프 노드의 균형도는 0이다.

3. 균형도는 '왼쪽 자식 트리의 높이 - 오른쪽 자식 트리의 높이'로 계산한다.

4. 왼쪽 자식 노드와 오른쪽 자식 노드의 균형도는 -1, 0, 1의 세 가지 값만 갖는다.

 

출처:

AVL 트리 (AVL tree) (tistory.com),

https://code-lab1.tistory.com/61?category=1213002