AVL 트리란 무엇인가?
AVL 트리는 1962년 이 알고리즘을 고안한 소련의 수학자 게오르기 아델슨-벨스키(Georgy Adelson-Velsky)와 예브게니 랜디스(Evgenii Landis)의 이름을 딴 자가 균형(self-balancing) 이진 탐색 트리입니다. 자가 균형 트리란 삽입과 삭제가 일어날 때마다 서브트리 내부에서 회전(rotation) 연산을 수행하여 왼쪽과 오른쪽의 균형을 스스로 유지하는 트리를 의미합니다.
왜 균형이 중요한가?
데이터가 한쪽 방향으로만 계속 삽입되면 일반적인 이진 탐색 트리는 연결 리스트처럼 한쪽으로 기울어지게 됩니다. 이렇게 완전히 불균형해진 트리에서는 탐색, 삽입, 삭제의 시간 복잡도가 최악의 경우 O(n)까지 나빠질 수 있습니다.
반면 AVL 트리는 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이, 즉 균형 인수(Balance Factor)가 항상 -1, 0, 1 중 하나를 유지하도록 강제합니다. 그 결과 어떤 순서로 데이터가 입력되더라도 트리의 높이가 log(n) 수준으로 유지되며, 탐색 시간은 O(log n)에 가깝게 보장됩니다.
회전(Rotation) 연산의 종류
삽입이나 삭제로 인해 균형이 깨지면 AVL 트리는 다음 네 가지 회전을 통해 균형을 복원합니다.
- LL 회전: 왼쪽-왼쪽 방향으로 불균형이 발생한 경우, 오른쪽으로 회전합니다.
- RR 회전: 오른쪽-오른쪽 방향으로 불균형이 발생한 경우, 왼쪽으로 회전합니다.
- LR 회전: 왼쪽-오른쪽 방향으로 불균형이 발생한 경우, 좌회전 후 우회전을 수행합니다.
- RL 회전: 오른쪽-왼쪽 방향으로 불균형이 발생한 경우, 우회전 후 좌회전을 수행합니다.
정리
AVL 트리는 삽입과 삭제가 빈번하게 일어나면서도 빠른 조회 성능이 필요한 상황에서 특히 유용한 자료구조입니다. 균형을 상시 유지함으로써 최악의 경우에도 O(log n)의 탐색 성능을 보장한다는 점이 가장 큰 장점이며, 자바스크립트에서 검색 기능이나 정렬된 데이터 관리를 구현할 때 훌륭한 선택지가 됩니다.