[자료구조] AVL 트리

이진탐색트리는 쏠림현상이 발생할 경우 (최악의 경우) 탐색 시 시간 복잡도가 $O(N)$이다.

이러한 경우를 방지하기 위해 AVL 트리를 고안해냈다.

특징은 다음과 같다.

 

1. 이진 탐색 트리의 속성을 가진다.

2. 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다.

3. 높이 차이가 1보다 커지면 회전(Rotation)을 통해 균형을 맞춰 높이 차이를 줄인다.

4. 삽입, 검색, 삭제의 시간 복잡도가 $O(logN)이다. (N = 노드의 개수)$

 

 

 

AVL 트리의 전반적인 작동을 시뮬레이션 해볼 수 있는 유용한 사이트이다.(백문이 불여일견)

 

https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

AVL Tree Visualzation