AVL Tree란 무엇인가요?

AVL 트리의 모든 노드는 자신의 높이(height)를 추적합니다. 이는 리프 노드까지의 가장 긴 경로에 있는 간선의 수입니다. 리프 노드의 높이는 1이며, 빈 서브트리의 높이는 0으로 계산됩니다. 노드의 두 자식 노드 높이를 통해 균형 인수(balance factor)를 계산할 수 있습니다: height(left) - height(right).

균형 인수가 -1, 0, 또는 1일 때 노드는 균형이 잡힌 상태입니다. AVL 트리의 규칙은 간단합니다: 모든 단일 노드는 항상 균형을 유지해야 합니다. 삽입이나 삭제로 인해 노드의 균형 인수가 2 또는 -2가 될 때마다, 트리는 회전(rotation)을 수행합니다. 이는 탐색 트리 순서를 깨뜨리지 않으면서 상수 시간 내에 균형을 복구하는 몇 가지 포인터의 국소적 재배열입니다.

네 가지 회전 사례(left-left, right-right, left-right, right-left)가 있지만, 모두 두 가지 기본 구성 요소인 단일 왼쪽 회전과 단일 오른쪽 회전으로 요약됩니다. 다음 몇 번의 레슨에서 이 두 가지를 모두 처음부터 직접 구현해 볼 것입니다.