AVL Tree
-
[Data Structure] AVL TreeCS/Data Structure 2021. 10. 7. 14:16
AVL Tree 이진 탐색 트리(Binary Search Tree)기반 트리 형식의 자료구조 이진 탐색 트리가 평균 저장, 삭제, 탐색 시간 복잡도가 평균 O(logN)을 갖지만, 한 쪽으로 편향될 경우(최악의 경우) 시간 복잡도가 O(N)이 될 수 있다. 이러한 단점을 보완하기 위해 스스로 높이 균형을 유지하는 AVL 트리가 고안됨. 특징 AVL 트리는 이진 탐색 트리의 속성을 가진다. 왼쪽, 오른쪽 서브 트리의 높이 차이(Banlance Factor)가 최대 1이다. Balance Factor가 1보다 커지면 회전(rotation)을 통해 균형을 잡는다. AVL 트리의 높이(h)는 logN을 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN)이다. 회전(Rotation) 삽입, 삭제 시..