[자료구조] AVL tree 개념과 연산

AVL Tree

AVL tree란 Adelson-Velskii와 Landis에 의해 1962년에 제안된 트리로, 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차가 1이하인 이진탐색트리를 의미한다.

 

AVL tree의 연산과정은 다음과 같다.

 

탐색 연산 : 이진 탐색 트리와 동일하다. 값들을 비교하며 내려가는 구조이다.

삽입,삭제 연산: 삽입-삭제 위치에서 루트까지의 경로에 있는 조상 노드들의 균형 인수에 영향을 받는다. LL type 혹은 RR type을 맞추기 위해 rotation을 진행한다.