이진 탐색 트리는 탐색 트리의 높이에 따라 비교 연산의 횟수가 달라집니다.
노드의 수가 같다면 트리의 레벨이 최소인 경우에서가 가장 적은 횟수를 가질 수 있고 편향 이진 트리에서 가장 높은 횟수를 가질 수 있습니다.
그렇기때문에 레벨을 최소화할 수 있도록 균형을 맞춰주는 조건을 추가하여 정의하는 트리를 균형 트리 혹은 균형 이진 탐색 트리라고 합니다.
아델슨 벨스키와 란디스가 제안한 대표적인 균형 이진 탐색트리인 AVL은 왼쪽 서브트리의 높이 hL과 오른쪽 서브트리의 높이 hR의 차이를 1 이하로 합니다.
AVL 트리의 특징은 다음과 같습니다.
말단 노드부터 조상 노드까지 BF를 확인하면서 진행하고 노드를 추가한 시점에서 BF의 절대값이 1을 초과했을 때 회전 연산을 통해 균형을 회복합니다.
하나의 자식 노드를 가지고 있는 자식노드만 가지고 있는 노드가 있을 때 오른차순으로 정렬 후 가운데 있는 노드를 부모노드로, 좌 우의 노드를 자식 노드로 가지게 수정하는 방식입니다.
LL 회전 연산
RR 회전 연산
LR 회전 연산
RL 회전 연산