[자료구조론] 탐색구조 - AVL 트리

균형트리 O(log n) : AVL, 2.3트리, 래드 블랙 트리, B트리, B+트리

비균형트리 : 이진탐색, m원탐색

 

- Andelson-Velskii와 Landis가 제안

 

특징

1) 이진탐색

2) BF(balance factor) -1, 0, 1 - 서브트리 좌 우 높이 차이

 

 

cf) 임계노드 : BF가 -1, 1인 노드

 

 

회전 종류

 

 

 

[2012년 국가 7급]
12 11 10 5 3 7 6 1 13 2 4 AVL 생성시 옳지 않은 것은? 

① AVL트리에서 7을 검색하기 위해서는 4번의 비교가 필요하다.

② AVL트리의 루트 값은 5이다.

③ 4가 삽입될 때, AVL 트리의 균형이 깨져서 재구성이 발생한다.

④ 6은 리프노드이다.

 

답 : 1번 -> 3번의 비교가 필요하다.