AVL 트리: 높이 차이를 제한해 검색 시간을 지키는 방법
AVL 트리는 이진 탐색 트리의 순서 규칙에 높이 균형 조건을 더한다. 모든 노드에서 왼쪽과 오른쪽 부분트리의 높이 차이가 많아야 1이어야 한다. 삽입이나 삭제가 이 조건을 깨뜨리면 회전으로 구조를 복구한다.
회전은 이진 탐색 트리의 키 순서를 유지하면서 구조를 바꾼다.
균형 인수로 불균형을 찾는다
왼쪽 높이에서 오른쪽 높이를 뺀 값을 균형 인수로 정의하면 허용 값은 -1,0,1이다. 높이 기준은 빈 트리와 잎에서 어떤 값을 쓸지 일관되게 정하면 된다. 노드마다 높이를 저장하면 변화가 생긴 경로에서 빠르게 갱신할 수 있다.
30,20,10을 차례로 넣으면 30의 왼쪽에 20, 그 왼쪽에 10이 있어 왼쪽-왼쪽 불균형이 생긴다. 30에서 오른쪽 회전을 하면 20이 위로, 10은 왼쪽, 30은 오른쪽이 된다. 중위 순서 10,20,30은 그대로 유지된다.
회전은 가운데 부분트리도 보존한다
아래 오른쪽 회전에서 promoted.right에 있던 부분트리는 새로운 오른쪽 자식의 왼쪽으로 옮긴다. 해당 키들은 promoted보다 크고 node보다 작으므로 이 위치가 맞다.
def rotate_right(node):
promoted = node.left
middle_subtree = promoted.right
promoted.right = node
node.left = middle_subtree
update_height(node)
update_height(promoted)
return promoted
높이는 아래로 내려간 노드를 먼저 갱신해야 위 노드 계산에 최신 값이 쓰인다. 반환된 새 루트를 부모나 전체 트리의 루트에 연결하는 일도 빠뜨리면 안 된다.
30,10,20처럼 왼쪽-오른쪽 모양이면 10에서 왼쪽 회전한 뒤 30에서 오른쪽 회전하는 이중 회전이 필요하다. 반대 두 경우도 대칭이다. 단순히 높은 쪽을 한 번 돌리는 규칙으로 모든 불균형을 해결할 수 없다.
최소 노드 수는 높이가 증가할 때 두 이전 높이의 최소 노드 수를 더하는 형태로 증가한다. 따라서 높이는 O(log n)으로 제한되고 검색·삽입·삭제가 최악 O(log n)이다. 회전 한 번의 참조 갱신은 O(1)이지만 조상을 따라 검사하는 비용이 포함된다.
삭제는 한 노드를 없앤 뒤 높이가 줄어 여러 조상에서 불균형이 생길 수 있으므로 위쪽으로 계속 확인해야 한다. 삽입의 처리 흐름과 삭제의 처리 흐름을 똑같이 가정하면 복구가 누락될 수 있다.
AVL의 엄격한 균형은 탐색 경로를 짧게 유지하지만 변경 때 높이 관리와 회전이 필요하다. 범위 검색이나 순서 정보가 중요하면서 최악 검색 시간을 제한하고 싶은 상황에 적합하다. 핵심은 회전 전후에 순서와 균형을 각각 확인하는 것이다.
회전 후 루트의 주소가 달라질 수 있다는 점은 실제 구현에서 중요하다. 부모의 왼쪽 또는 오른쪽 참조를 새 루트로 바꾸고, 부모 포인터가 있다면 그 방향도 함께 고쳐야 한다. 높이만 맞아도 연결 일부가 누락되면 트리의 원소를 잃을 수 있다. 갱신 전후 중위 순회가 같은지도 확인할 수 있다.