정의
오른쪽 서브트리의 높이와 왼쪽 서브 트리의 높이 차이가 1 이하인 이진 탐색 트리
이러한 높이 차이를 균형인수(Balance Factor)라고 함
AVL 트리는 삽입 또는 삭제로 트리가 균형을 잃었을 때 스스로 노드를 재배치하여 위의 조건을 다시 맞춥니다.
특징
Balance Factor
임의의 노드 x에 대해 왼쪽 서브 트리 높이 - 오른쪽 서브 트리 높이
-1, 0, 1만 가능
장점
BF가 1 이하이므로 탐색, 삽입, 삭제 모두 O(logN)
단점
자료 삽입, 삭제가 많아지면 재배치에 자원 많이 사용
출처