---
title: "AVL 트리: 높이 차이를 제한해 검색 시간을 지키는 방법"
author: "Lee"
published_at: "2026-10-28T09:00:04.639Z"
updated_at: "2026-09-30T09:28:19.908Z"
tags: ["컴퓨터공학","자료구조"]
canonical_url: "https://ariser.io/@writer_a1cd615ab19e/avl-%ED%8A%B8%EB%A6%AC-%EB%86%92%EC%9D%B4-%EC%B0%A8%EC%9D%B4%EB%A5%BC-%EC%A0%9C%ED%95%9C%ED%95%B4-%EA%B2%80%EC%83%89-%EC%8B%9C%EA%B0%84%EC%9D%84-%EC%A7%80%ED%82%A4%EB%8A%94-%EB%B0%A9%EB%B2%95"
ai_assisted: false
---

# AVL 트리: 높이 차이를 제한해 검색 시간을 지키는 방법

[원문](https://ariser.io/@writer_a1cd615ab19e/avl-%ED%8A%B8%EB%A6%AC-%EB%86%92%EC%9D%B4-%EC%B0%A8%EC%9D%B4%EB%A5%BC-%EC%A0%9C%ED%95%9C%ED%95%B4-%EA%B2%80%EC%83%89-%EC%8B%9C%EA%B0%84%EC%9D%84-%EC%A7%80%ED%82%A4%EB%8A%94-%EB%B0%A9%EB%B2%95)

AVL 트리는 이진 탐색 트리의 순서 규칙에 높이 균형 조건을 더한다. 모든 노드에서 왼쪽과 오른쪽 부분트리의 높이 차이가 많아야 1이어야 한다. 삽입이나 삭제가 이 조건을 깨뜨리면 회전으로 구조를 복구한다.

![30·20·10으로 치우친 트리를 오른쪽 회전해 루트 20으로 균형을 잡는 AVL 예시](/api/v1/media/9c515424-4f83-4c5b-ae10-936407973d5a)

*회전은 이진 탐색 트리의 키 순서를 유지하면서 구조를 바꾼다.*

### 균형 인수로 불균형을 찾는다

왼쪽 높이에서 오른쪽 높이를 뺀 값을 균형 인수로 정의하면 허용 값은 -1,0,1이다. 높이 기준은 빈 트리와 잎에서 어떤 값을 쓸지 일관되게 정하면 된다. 노드마다 높이를 저장하면 변화가 생긴 경로에서 빠르게 갱신할 수 있다.

30,20,10을 차례로 넣으면 30의 왼쪽에 20, 그 왼쪽에 10이 있어 왼쪽-왼쪽 불균형이 생긴다. 30에서 오른쪽 회전을 하면 20이 위로, 10은 왼쪽, 30은 오른쪽이 된다. 중위 순서 10,20,30은 그대로 유지된다.

### 회전은 가운데 부분트리도 보존한다

아래 오른쪽 회전에서 promoted.right에 있던 부분트리는 새로운 오른쪽 자식의 왼쪽으로 옮긴다. 해당 키들은 promoted보다 크고 node보다 작으므로 이 위치가 맞다.

```python
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의 엄격한 균형은 탐색 경로를 짧게 유지하지만 변경 때 높이 관리와 회전이 필요하다. 범위 검색이나 순서 정보가 중요하면서 최악 검색 시간을 제한하고 싶은 상황에 적합하다. 핵심은 회전 전후에 순서와 균형을 각각 확인하는 것이다.

회전 후 루트의 주소가 달라질 수 있다는 점은 실제 구현에서 중요하다. 부모의 왼쪽 또는 오른쪽 참조를 새 루트로 바꾸고, 부모 포인터가 있다면 그 방향도 함께 고쳐야 한다. 높이만 맞아도 연결 일부가 누락되면 트리의 원소를 잃을 수 있다. 갱신 전후 중위 순회가 같은지도 확인할 수 있다.

### 참고 자료

- [MIT OpenCourseWare · Introduction to Algorithms](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/)