Post

19. AVL 트리

Posted Updated
By noir1458
9 min read
19. AVL 트리

개념

AVL 트리는 자가 균형 이진 탐색 트리(Self-Balancing BST)로, 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1이다.

균형 인수 (Balance Factor)

1
2

BF(node) = height(left) - height(right)
유효 범위: -1, 0, 1

BST와 비교

항목일반 BSTAVL 트리
탐색O(N) 최악O(log N) 보장
삽입O(N) 최악O(log N) 보장
삭제O(N) 최악O(log N) 보장
균형보장 안됨항상 균형
구현간단복잡 (회전)

회전 연산

상황BF회전
LL+2, 왼쪽 자식 ≥ 0우회전
RR-2, 오른쪽 자식 ≤ 0좌회전
LR+2, 왼쪽 자식 < 0좌회전 → 우회전
RL-2, 오른쪽 자식 > 0우회전 → 좌회전

핵심 연산 & 시간복잡도

연산시간복잡도설명
탐색O(log N)항상 균형
삽입O(log N)삽입 후 회전
삭제O(log N)삭제 후 회전
최솟값/최댓값O(log N)왼쪽/오른쪽 끝

구현 (No-STL)

노드 구조체

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

const int MAX_NODE = 100001;

struct Node {
    int key;
    int height;
    int left;
    int right;
} node[MAX_NODE];

int nodeCnt;
int root;

void init() {
    nodeCnt = 0;
    root = -1;
}

int makeNode(int key) {
    node[nodeCnt].key = key;
    node[nodeCnt].height = 1;
    node[nodeCnt].left = -1;
    node[nodeCnt].right = -1;
    return nodeCnt++;
}

높이 및 균형 인수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int getHeight(int cur) {
    if (cur == -1) return 0;
    return node[cur].height;
}

void updateHeight(int cur) {
    int lh = getHeight(node[cur].left);
    int rh = getHeight(node[cur].right);
    node[cur].height = 1 + (lh > rh ? lh : rh);
}

int getBalance(int cur) {
    if (cur == -1) return 0;
    return getHeight(node[cur].left) - getHeight(node[cur].right);
}

회전 연산

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

// 우회전 (Right Rotation)
//       y                x
//      / \              / \
//     x   C    →       A   y
//    / \                  / \
//   A   B                B   C

int rotateRight(int y) {
    int x = node[y].left;
    int B = node[x].right;

    node[x].right = y;
    node[y].left = B;

    updateHeight(y);
    updateHeight(x);

    return x;
}

// 좌회전 (Left Rotation)
//     x                  y
//    / \                / \
//   A   y      →       x   C
//      / \            / \
//     B   C          A   B

int rotateLeft(int x) {
    int y = node[x].right;
    int B = node[y].left;

    node[y].left = x;
    node[x].right = B;

    updateHeight(x);
    updateHeight(y);

    return y;
}

균형 유지

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

int balance(int cur) {
    updateHeight(cur);
    int bf = getBalance(cur);

    // LL Case
    if (bf > 1 && getBalance(node[cur].left) >= 0) {
        return rotateRight(cur);
    }

    // RR Case
    if (bf < -1 && getBalance(node[cur].right) <= 0) {
        return rotateLeft(cur);
    }

    // LR Case
    if (bf > 1 && getBalance(node[cur].left) < 0) {
        node[cur].left = rotateLeft(node[cur].left);
        return rotateRight(cur);
    }

    // RL Case
    if (bf < -1 && getBalance(node[cur].right) > 0) {
        node[cur].right = rotateRight(node[cur].right);
        return rotateLeft(cur);
    }

    return cur;
}

삽입

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int insert(int cur, int key) {
    if (cur == -1) {
        return makeNode(key);
    }

    if (key < node[cur].key) {
        node[cur].left = insert(node[cur].left, key);
    } else if (key > node[cur].key) {
        node[cur].right = insert(node[cur].right, key);
    } else {
        return cur;  // 중복 키
    }

    return balance(cur);
}

void insertKey(int key) {
    root = insert(root, key);
}

삭제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

int findMin(int cur) {
    while (node[cur].left != -1) {
        cur = node[cur].left;
    }
    return cur;
}

int deleteNode(int cur, int key) {
    if (cur == -1) return -1;

    if (key < node[cur].key) {
        node[cur].left = deleteNode(node[cur].left, key);
    } else if (key > node[cur].key) {
        node[cur].right = deleteNode(node[cur].right, key);
    } else {
        // 삭제할 노드 찾음
        if (node[cur].left == -1 || node[cur].right == -1) {
            int child = (node[cur].left != -1) ? node[cur].left : node[cur].right;
            return child;
        }

        // 두 자식 모두 있음
        int successor = findMin(node[cur].right);
        node[cur].key = node[successor].key;
        node[cur].right = deleteNode(node[cur].right, node[successor].key);
    }

    return balance(cur);
}

void deleteKey(int key) {
    root = deleteNode(root, key);
}

탐색

1
2
3
4
5
6

bool search(int cur, int key) {
    if (cur == -1) return false;
    if (key == node[cur].key) return true;
    if (key < node[cur].key) return search(node[cur].left, key);
    return search(node[cur].right, key);
}

전체 코드 (구조체화)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

const int MAX_NODE = 100001;

struct AVLTree {
    struct Node {
        int key, height, left, right;
    } node[MAX_NODE];

    int nodeCnt, root;

    void init() {
        nodeCnt = 0;
        root = -1;
    }

    int makeNode(int key) {
        node[nodeCnt] = {key, 1, -1, -1};
        return nodeCnt++;
    }

    int height(int cur) { return cur == -1 ? 0 : node[cur].height; }

    void updateHeight(int cur) {
        int lh = height(node[cur].left);
        int rh = height(node[cur].right);
        node[cur].height = 1 + (lh > rh ? lh : rh);
    }

    int balance(int cur) { return height(node[cur].left) - height(node[cur].right); }

    int rotateRight(int y) {
        int x = node[y].left;
        node[y].left = node[x].right;
        node[x].right = y;
        updateHeight(y);
        updateHeight(x);
        return x;
    }

    int rotateLeft(int x) {
        int y = node[x].right;
        node[x].right = node[y].left;
        node[y].left = x;
        updateHeight(x);
        updateHeight(y);
        return y;
    }

    int rebalance(int cur) {
        updateHeight(cur);
        int bf = balance(cur);

        if (bf > 1) {
            if (balance(node[cur].left) < 0)
                node[cur].left = rotateLeft(node[cur].left);
            return rotateRight(cur);
        }
        if (bf < -1) {
            if (balance(node[cur].right) > 0)
                node[cur].right = rotateRight(node[cur].right);
            return rotateLeft(cur);
        }
        return cur;
    }

    int insert(int cur, int key) {
        if (cur == -1) return makeNode(key);
        if (key < node[cur].key) node[cur].left = insert(node[cur].left, key);
        else if (key > node[cur].key) node[cur].right = insert(node[cur].right, key);
        return rebalance(cur);
    }

    void insert(int key) { root = insert(root, key); }
};

STL

C++에서 AVL 트리 직접 구현 대신 std::set/std::map을 사용하면 내부적으로 Red-Black Tree로 균형 BST 기능을 사용할 수 있다.

1
2
3
4
5
6
7
8
9

#include <set>
#include <map>

std::set<int> s;  // 내부적으로 Red-Black Tree
s.insert(5);
s.erase(5);
s.find(5);

// AVL 트리가 필요한 특수 케이스가 아니면 STL 사용 권장

사용 예시

중위 순회 (정렬된 출력)

1
2
3
4
5
6

void inorder(int cur) {
    if (cur == -1) return;
    inorder(node[cur].left);
    // node[cur].key 출력
    inorder(node[cur].right);
}

K번째 원소 (서브트리 크기)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// 각 노드에 서브트리 크기 저장
struct Node {
    int key, height, size;
    int left, right;
};

int getSize(int cur) {
    return cur == -1 ? 0 : node[cur].size;
}

void updateSize(int cur) {
    node[cur].size = 1 + getSize(node[cur].left) + getSize(node[cur].right);
}

int kthSmallest(int cur, int k) {
    int leftSize = getSize(node[cur].left);
    if (k <= leftSize) return kthSmallest(node[cur].left, k);
    if (k == leftSize + 1) return node[cur].key;
    return kthSmallest(node[cur].right, k - leftSize - 1);
}

주의사항 / Edge Cases

회전 후 높이 업데이트 순서

1
2
3
4
5
6
7
8
9
10

int rotateRight(int y) {
    int x = node[y].left;
    node[y].left = node[x].right;
    node[x].right = y;

    updateHeight(y);  // 자식(y)을 먼저 업데이트
    updateHeight(x);  // 부모(x)를 나중에 업데이트

    return x;
}

균형 인수 판정

1
2
3
4
5
6
7
8
9

// |BF| > 1 이면 불균형
if (bf > 1) {
    // 왼쪽이 무거움 → LL 또는 LR
    if (balance(node[cur].left) >= 0) {
        // LL: 우회전
    } else {
        // LR: 좌회전 후 우회전
    }
}

빈 트리 처리

1
2
3
4
5
6

int insert(int cur, int key) {
    if (cur == -1) {
        return makeNode(key);  // 첫 노드
    }
    // ...
}

코딩테스트에서의 선택

1
2
3
4
5
6
7

// AVL 직접 구현은 복잡함
// 대부분의 경우 std::set/std::map 사용 권장

// AVL 구현이 필요한 경우:
// - 특정 연산 커스터마이징 필요
// - 면접/CS 대비
// - No-STL 환경

추천 문제

난이도문제링크
Gold이중 우선순위 큐BOJ 7662
Gold보석 도둑BOJ 1202
Platinum중앙값BOJ 2696
Platinum순서 통계량BOJ 12899
PlatinumK번째 수BOJ 7469
datastructure
datastructure
This post is licensed under CC BY 4.0 by the author.