Tree Structure 노트6 - AVL Tree

높이균형트리(Height balanced tree) AVL트리

AVL트리 : 스스로 균형을 잡는 이진 탐색 트리. 트리의 높이가 h일때 이진 탐색 트리의 시간 복잡도는 O(h). 한쪽으로 치우친 skewed tree가 되면 트리의 높이가 높아지기 때문에 이를 방지하고자 높이 균형을 유지하는 AVL트리 사용.

-> self-organizing data structure. balance factor가 2이상 차이가 나면 작업.

 

특징 : AVL트리는 이진 탐색 트리의 속성을 가짐./ 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1./ 어떤 시점에서 높이 차이가 1보다 커지면 회전(rotation)을 통해 균형을 잡아 높이 차이를 줄임./ AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 삭제, 검색의 시간 복잡도는 O(logN).

 

Balance Factor : 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값.

BF == 1이면 왼쪽 서브트리가 오른쪽 서브트리보다 높이가 한단계 높음. BF == 0이면 높이 같음. BF == -1이면 왼쪽이 오른쪽보다 하나 낮음.

 

회전 (rotation) : AVL트리는 BST이기 때문에 모든 작업은 BST에서 하는 방식 사용.

검색 및 순회 연산은 Balance Factor를 변경하지 않지만, 삽입 및 삭제는 변경될 수 있음./ 삽입, 삭제 시 불균형 상태가 되면 AVL트리는 불균형 노드를 기준으로 서브트리의 위치를 변경하는 rotation작업을 수행하여 트리의 균형을 맞춤.

AVL트리의 삽입 삭제 방식은 BST와 같지만 높이 균형을 유지하기 위해 노드의 높이 정보와 case별 rotation 과정이 추가됨.