AVL 트리

AVL 트리는 값을 어떤 순서로 넣어도 찾는 길이 길어지지 않게 지켜 줍니다. 값을 크기 순서대로 담는 이진 탐색 트리에 균형을 지키는 규칙 하나를 더한 것입니다. 값을 넣거나 지울 때마다 한쪽으로 기운 곳을 찾아 바로 고쳐 세웁니다. 그래서 담긴 값이 많아져도 몇 번의 비교만으로 원하는 값에 닿습니다.

상세

이 절은 먼저 보통의 이진 탐색 트리가 왜 한쪽으로 기우는지 봅니다. 그다음 AVL 트리가 지키는 균형 조건과, 기운 곳을 되돌리는 회전을 봅니다. 마지막으로 10 부터 70 까지 일곱 키를 차례로 넣어 봅니다. 비용과 레드-블랙 트리와의 차이도 짚습니다.

AVL 은 이 트리를 처음 내놓은 두 연구자 Georgy Adelson-Velsky 와 Evgenii Landis 의 성에서 딴 이름입니다. 스스로 균형을 지키는 이진 탐색 트리 가운데 가장 먼저 나온 것입니다.

한쪽으로 기우는 이진 탐색 트리

이진 탐색 트리는 값을 크기 순서대로 담아 두고 빨리 찾게 해 주는 트리입니다. 값을 담은 상자 하나하나를 노드라고 부릅니다. 노드마다 아래에 자식을 둘까지 둡니다.

맨 위 노드를 루트라고 부릅니다. 자식이 하나도 없는 노드는 잎이라고 부릅니다. 트리는 루트에서 아래로 뻗어 잎에서 끝납니다.

노드에 담겨 크기를 비교하는 값이 키입니다. 회원 번호로 회원을 찾는다면 회원 번호가 키입니다. 이진 탐색 트리는 어느 노드에서 봐도 왼쪽 아래에는 그보다 작은 키만, 오른쪽 아래에는 큰 키만 둡니다.

찾을 때는 루트에서 출발해 한 층씩 내려갑니다. 찾는 키가 지금 노드의 키보다 작으면 왼쪽으로, 크면 오른쪽으로 갑니다. 그래서 드는 시간은 트리가 몇 층인지가 정합니다.

루트에서 가장 먼 잎까지 거치는 노드 수를 트리의 높이라고 부릅니다. 높이가 3 이면 어느 키를 찾든 세 번 안에 비교가 끝납니다.

문제는 트리의 모양을 넣는 순서가 정한다는 것입니다. 10, 20, 30, 40 처럼 작은 키부터 차례로 넣으면 새 키가 늘 지금까지의 가장 큰 키보다 큽니다. 그래서 매번 오른쪽 끝에만 매달려 한 줄로 늘어섭니다.

flowchart TD
    subgraph 치우침["작은 키부터 차례로 넣은 이진 탐색 트리 · 높이 4"]
        A["10"] --> B["20"] --> C["30"] --> D["40"]
    end

이 트리에서 40 을 찾으려면 네 노드를 모두 거칩니다. 키가 n 개면 n 번 비교합니다. 값을 줄지어 이어 놓고 처음부터 훑는 연결 리스트와 다를 것이 없습니다.

넣고 지울 때마다 모양을 손봐 높이를 낮게 붙잡는 이진 탐색 트리를 균형 이진 탐색 트리라고 부릅니다. AVL 트리는 그 가운데 하나입니다.

균형 인수

AVL 트리는 노드마다 왼쪽과 오른쪽이 얼마나 깊은지를 견줍니다. 한 노드의 자식과 그 아래에 딸린 노드를 모두 묶은 것을 서브트리라고 부릅니다. 왼쪽 자식 아래를 묶으면 왼쪽 서브트리, 오른쪽 자식 아래를 묶으면 오른쪽 서브트리입니다.

왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값을 그 노드의 균형 인수라고 부릅니다. 비어 있는 서브트리는 높이를 0 으로 칩니다. 균형 인수가 양수면 왼쪽이 깊습니다. 음수면 오른쪽이 깊습니다.

앞의 한 줄짜리 트리에서 10 을 봅시다. 왼쪽은 비어 있어 높이가 0 입니다. 오른쪽은 20·30·40 세 층이라 높이가 3 입니다. 그래서 10 의 균형 인수는 -3 입니다.

균형 조건

AVL 트리는 모든 노드의 균형 인수를 -1, 0, 1 셋 가운데 하나로 지킵니다. 어느 노드에서 봐도 양쪽 높이가 1 넘게 벌어지지 않는다는 뜻입니다. AVL 트리가 이진 탐색 트리에 더하는 규칙은 이것 하나입니다.

아래는 키 일곱 개를 담은 AVL 트리입니다. 노드마다 균형 인수를 적었습니다. 20 과 70 은 자식이 왼쪽에만 하나 있습니다.

flowchart TD
    N50["50 · 균형 인수 1"] --> N30["30 · 균형 인수 1"]
    N50 --> N70["70 · 균형 인수 1"]
    N30 --> N20["20 · 균형 인수 1"]
    N30 --> N40["40 · 균형 인수 0"]
    N20 --> N10["10 · 균형 인수 0"]
    N70 --> N60["60 · 균형 인수 0"]

트리 전체가 왼쪽으로 조금 기울었습니다. 그래도 어느 노드의 균형 인수도 1 을 넘지 않으니 AVL 트리의 조건을 지킵니다. 루트 50 의 왼쪽 서브트리는 높이 3, 오른쪽은 높이 2 입니다.

높이의 상한

균형 조건이 높이를 얼마나 낮게 붙잡는지는 거꾸로 따져 보면 보입니다. 높이가 h 인 AVL 트리 가운데 노드를 가장 적게 쓰는 모양을 찾는 것입니다. 노드 수에 비해 높이가 크면 그만큼 성기게 기운 트리입니다.

그런 트리는 한쪽 서브트리의 높이가 h-1, 다른 쪽이 h-2 입니다. 둘 다 h-1 이면 노드가 더 듭니다. 차이가 2 면 조건이 깨집니다. 두 서브트리도 저마다 노드를 가장 적게 쓴 모양입니다.

flowchart TD
    G["루트"] --> GL["한쪽 서브트리 · 높이 h-1 · 노드를 가장 적게 쓴 모양"]
    G --> GR["다른 쪽 서브트리 · 높이 h-2 · 노드를 가장 적게 쓴 모양"]

그래서 높이 h 에 필요한 최소 노드 수는 높이 h-1 과 h-2 의 최소 노드 수에 루트 하나를 더한 값입니다. 앞의 두 수를 더해 다음 수를 만드는 피보나치 수열과 같은 꼴로 불어납니다.

아래는 높이 1·2·3 에서 노드를 가장 적게 쓴 모양을 차례로 쌓은 것입니다. 높이 3 모양은 루트 30 아래에 높이 2 모양(20·10)과 높이 1 모양(40)이 달린 것입니다.

flowchart TD
    subgraph H1["높이 1 · 노드 1개"]
        K40a["40"]
    end
    subgraph H2["높이 2 · 노드 2개"]
        K20b["20"] --> K10b["10"]
    end
    subgraph H3["높이 3 · 노드 4개"]
        K30c["30"] --> K20c["20"]
        K30c --> K40c["40"]
        K20c --> K10c["10"]
    end
    K40a ~~~ K20b
    K10b ~~~ K30c

높이 4 에서 노드를 가장 적게 쓴 모양은 「균형 조건」의 일곱 노드 트리입니다. 50 의 왼쪽은 높이 3 최소 모양으로 노드 4개, 오른쪽은 높이 2 최소 모양으로 2개입니다. 4 + 2 + 1 = 7 입니다.

표를 내려가면 한 층 높아질 때마다 최소 노드 수가 1.6 배쯤씩 늡니다. 뒤집어 말하면 노드 수가 1.6 배쯤 늘어야 높이가 한 층 늘 수 있습니다.

n 을 몇 번 반으로 나눠야 1 이 되는지를 세는 값을 log₂ n 이라고 적습니다. 층마다 노드가 꽉 찬 트리의 높이가 이 값 언저리입니다. 꽉 찬 트리는 한 층 늘 때마다 노드가 두 배로 늘기 때문입니다.

1.6 을 1.44 번쯤 거듭 곱하면 2 가 됩니다. 그래서 노드가 두 배로 느는 동안 가장 성긴 AVL 트리는 약 1.44 층 높아집니다. AVL 트리의 높이가 log₂ n 의 약 1.44 배를 넘지 않는 까닭입니다.

노드가 백만 개면 log₂ n 이 20 남짓입니다. 그러니 높이는 서른을 넘지 않습니다. 이처럼 노드 수의 로그에 묶이는 한계를 빅오 표기법으로 O(log n) 이라고 적습니다. 데이터가 두 배로 늘어도 거치는 층은 한 층 남짓 는다는 뜻입니다.

회전

균형이 깨지면 AVL 트리는 회전으로 고칩니다. 회전은 노드 둘의 부모와 자식 관계를 뒤바꾸는 일입니다. 크기 순서 규칙은 지킨 채 한쪽 높이를 한 층 줄이고 다른 쪽을 한 층 늘립니다.

가장 작은 예부터 봅니다. 빈 AVL 트리에 30, 20, 10 을 차례로 넣으면 세 노드가 왼쪽으로 한 줄로 섭니다. 30 의 균형 인수가 2 라 조건이 깨졌습니다.

flowchart TD
    N30["30 · 균형 인수 2"] --> N20["20"]
    N20 --> N10["10"]

20 을 위로 끌어올리고 30 을 20 의 오른쪽 자식으로 내립니다. 30 은 20 보다 크니 오른쪽에 두어도 크기 순서 규칙이 지켜집니다. 높이는 3 에서 2 로 줄었습니다.

flowchart TD
    N20["20 · 균형 인수 0"] --> N10["10"]
    N20 --> N30["30"]

위 노드 30 이 오른쪽 아래로 내려갔으므로 이것을 30 에서 한 오른쪽 회전이라고 부릅니다. 좌우를 뒤집은 것이 왼쪽 회전입니다. 위 노드가 왼쪽 아래로 내려가고 그 오른쪽 자식이 올라섭니다.

20 에 원래 오른쪽 자식이 있었다면 그 서브트리는 30 의 새 왼쪽 자식으로 옮겨 갑니다. 그 서브트리의 키는 모두 20 보다 크고 30 보다 작기 때문입니다. 아래 두 그림은 20 과 30 아래에 서브트리 셋이 달린 경우의 회전 앞뒤입니다.

flowchart TD
    Y["30"] --> X["20"]
    Y --> C["C · 30 보다 큰 키"]
    X --> A["A · 20 보다 작은 키"]
    X --> B["B · 20 과 30 사이의 키"]

오른쪽 회전을 하면 20 이 올라섭니다. 30 은 20 의 오른쪽 자식으로 내려갑니다. B 는 20 을 떠나 30 의 왼쪽 자식이 됩니다.

flowchart TD
    X["20"] --> A["A · 20 보다 작은 키"]
    X --> Y["30"]
    Y --> B["B · 20 과 30 사이의 키"]
    Y --> C["C · 30 보다 큰 키"]

두 그림 모두 크기 순서로 늘어놓으면 A, 20, B, 30, C 입니다. 회전 앞뒤로 이 순서가 같습니다.

바꿔 건 연결은 셋뿐입니다. 30 의 왼쪽 자식, 20 의 오른쪽 자식, 그리고 위에서 이 서브트리를 가리키던 연결입니다.

기운 모양 네 가지

균형 인수가 2 나 -2 가 되면 그 노드는 균형이 깨진 것입니다. 고치는 방법은 그 노드 아래의 모양에 따라 넷으로 갈립니다. 먼저 깨진 노드의 두 자식 가운데 깊은 쪽을 봅니다. 그다음 그 자식이 같은 쪽으로 기울었나, 반대쪽으로 꺾였나를 봅니다.

넣기에서는 새 키가 들어간 곳이 이 모양을 정합니다. 새 키가 왼쪽 자식의 오른쪽 아래로 들어가면 왼쪽 자식이 오른쪽으로 기웁니다. 그러면 꺾인 모양이 됩니다.

아래는 네 모양을 노드 셋으로 그린 것입니다. 맨 위 노드가 균형이 깨진 노드입니다.

flowchart TD
    subgraph SLL["왼쪽-왼쪽"]
        A1["30"] --> A2["20 · 왼쪽 자식"] --> A3["10 · 왼쪽 자식"]
    end
    subgraph SRR["오른쪽-오른쪽"]
        B1["10"] --> B2["20 · 오른쪽 자식"] --> B3["30 · 오른쪽 자식"]
    end
    subgraph SLR["왼쪽-오른쪽"]
        C1["30"] --> C2["10 · 왼쪽 자식"] --> C3["20 · 오른쪽 자식"]
    end
    subgraph SRL["오른쪽-왼쪽"]
        D1["10"] --> D2["30 · 오른쪽 자식"] --> D3["20 · 왼쪽 자식"]
    end
    A3 ~~~ B1
    B3 ~~~ C1
    C3 ~~~ D1

모양마다 고치는 방법은 아래와 같습니다.

앞의 두 경우는 곧게 한 줄로 기운 모양이라 회전 한 번이면 됩니다. 「회전」에서 본 30·20·10 이 왼쪽-왼쪽 경우였습니다.

뒤의 두 경우는 한 번 꺾여 기운 모양이라 회전을 두 번 합니다. 이것을 이중 회전이라고 부릅니다.

위 그림의 왼쪽-오른쪽 모양으로 봅니다. 30, 10, 20 순서로 넣으면 이 모양이 됩니다. 30 의 균형 인수는 2 입니다.

30 에서 오른쪽 회전만 하면 10 이 루트가 됩니다. 20 은 30 의 왼쪽으로 옮겨 갑니다. 그러면 10 의 균형 인수가 -2 가 되어 반대쪽으로 기울 뿐입니다.

flowchart TD
    subgraph 잘못["오른쪽 회전만 한 결과"]
        F10["10 · 균형 인수 -2"] --> F30["30 · 10 의 오른쪽 자식"]
        F30 --> F20["20 · 30 의 왼쪽 자식"]
    end

그래서 꺾인 곳을 먼저 폅니다. 10 에서 왼쪽 회전을 하면 20 이 10 의 위로 올라섭니다. 30, 20, 10 이 왼쪽으로 곧게 선 모양, 곧 왼쪽-왼쪽 경우가 됩니다.

flowchart TD
    N30["30 · 균형 인수 2"] --> N20["20"]
    N20 --> N10["10"]

이제 30 에서 오른쪽 회전을 한 번 더 합니다. 「회전」의 첫 예와 같은 모양이 되어 20 이 루트에 섭니다.

넣기

AVL 트리에 키를 넣는 일은 두 단계입니다. 먼저 보통의 이진 탐색 트리처럼 찾다가 막힌 빈 곳에 새 노드를 매답니다. 그다음 매단 곳에서 루트 쪽으로 거슬러 오릅니다. 지나온 노드마다 높이를 고치고 균형 인수를 확인합니다.

거슬러 오르다 처음 만난 균형이 깨진 노드를 네 방법 가운데 하나로 고칩니다. 고치고 나면 그 서브트리의 높이가 새 키를 넣기 전과 같아집니다. 그래서 그 위의 노드들은 더 손볼 것이 없습니다. 넣기 한 번에 고치는 노드는 많아야 하나입니다.

「균형 조건」에서 본 일곱 노드 트리에 5 를 넣습니다. 5 는 10 의 왼쪽에 매달립니다. 거슬러 오르면 10 은 균형 인수가 1 이라 조건을 지킵니다. 20 에서 처음으로 균형 인수가 2 가 됩니다.

flowchart TD
    N50["50 · 균형 인수 2"] --> N30["30 · 균형 인수 2"]
    N50 --> N70["70"]
    N30 --> N20["20 · 균형 인수 2 · 처음 만난 균형이 깨진 노드"]
    N30 --> N40["40"]
    N20 --> N10["10 · 균형 인수 1"]
    N10 --> N5["5 · 새로 매단 노드"]
    N70 --> N60["60"]
    classDef bad stroke-width:4px
    class N20 bad

30 과 50 도 균형 인수가 2 가 됐습니다. 그래도 고치는 노드는 20 하나입니다.

20 의 깊은 쪽 자식 10 도 왼쪽으로 기울었으니 왼쪽-왼쪽 경우입니다. 20 에서 오른쪽 회전을 하면 10 이 올라섭니다. 5 와 20 은 10 의 양쪽 자식이 됩니다.

flowchart TD
    N50["50 · 균형 인수 1"] --> N30["30 · 균형 인수 1"]
    N50 --> N70["70"]
    N30 --> N10["10 · 올라선 노드 · 균형 인수 0"]
    N30 --> N40["40"]
    N10 --> N5["5"]
    N10 --> N20["20"]
    N70 --> N60["60"]

10 아래 서브트리의 높이는 5 를 넣기 전과 같은 2 로 돌아왔습니다. 그래서 30 과 50 의 균형 인수도 따로 손대지 않아도 1 로 돌아왔습니다.

넣기 코드

이 과정을 자바 코드로 옮겨 봅니다. 노드는 키와 두 자식에 더해 자기 높이를 들고 있습니다. 잎의 높이는 1 이고 빈 곳은 0 입니다.

class Node {
    int key;
    int height = 1;  // 잎이면 1
    Node left, right;
    Node(int key) { this.key = key; }
}

int height(Node n) {
    return n == null ? 0 : n.height;
}

int balance(Node n) {  // 균형 인수
    return height(n.left) - height(n.right);
}

void update(Node n) {
    n.height = 1 + Math.max(height(n.left),
                            height(n.right));
}

balance 는 균형 인수를 계산합니다. update 는 두 자식의 높이 가운데 큰 쪽에 1 을 더해 자기 높이를 다시 적습니다. 자식이 바뀐 노드는 이 함수를 불러 높이를 고칩니다.

회전은 연결 몇 개를 바꿔 거는 일이라 코드도 짧습니다. 아래 rotateRight 의 y 와 x 는 「회전」 그림의 30 과 20 입니다.

Node rotateRight(Node y) {
    Node x = y.left;
    y.left = x.right;  // B 를 y 에게
    x.right = y;
    update(y);  // 아래로 간 쪽 먼저
    update(x);
    return x;  // 새 서브트리 루트
}

Node rotateLeft(Node x) {
    Node y = x.right;
    x.right = y.left;
    y.left = x;
    update(x);
    update(y);
    return y;
}

높이는 아래로 내려간 노드부터 고칩니다. 위 노드의 높이가 아래 노드의 높이로 정해지기 때문입니다. rotateLeft 는 좌우만 바꾼 거울 모양입니다.

넣기는 재귀로 씁니다. 재귀는 함수가 자기 자신을 다시 부르는 방식입니다. 아래 insert 는 왼쪽이나 오른쪽 서브트리에 자신을 다시 불러 내려갑니다. 부른 함수가 끝나고 돌아오는 길이 곧 루트 쪽으로 거슬러 오르는 길입니다.

Node insert(Node n, int key) {
    if (n == null) return new Node(key);
    if (key < n.key)
        n.left = insert(n.left, key);
    else if (key > n.key)
        n.right = insert(n.right, key);
    else return n;  // 이미 있는 키
    update(n);
    int b = balance(n);
    if (b > 1) {  // 왼쪽이 깊다
        // 꺾였으면 먼저 편다
        if (balance(n.left) < 0)
            n.left = rotateLeft(n.left);
        return rotateRight(n);
    }
    if (b < -1) {  // 오른쪽이 깊다
        // 꺾였으면 먼저 편다
        if (balance(n.right) > 0)
            n.right = rotateRight(n.right);
        return rotateLeft(n);
    }
    return n;
}

돌아오는 길에 노드마다 update 로 높이를 고칩니다. 그다음 균형 인수를 봅니다. 균형 인수가 2 이상이면 왼쪽이 깊은 것입니다.

이때 왼쪽 자식의 균형 인수가 음수면 새 키가 왼쪽 자식의 오른쪽으로 들어간 것입니다. 꺾인 모양, 곧 왼쪽-오른쪽 경우라 먼저 폅니다. 오른쪽이 깊을 때는 좌우만 바뀝니다. 코드의 두 if 가 가르는 길은 아래와 같습니다.

flowchart TD
    Q1{"균형 인수가 2 이상인가"} -->|"예 · 왼쪽이 깊다"| Q2{"왼쪽 자식의 균형 인수가 음수인가"}
    Q2 -->|"예 · 왼쪽-오른쪽 경우"| R1["왼쪽 자식에서 왼쪽 회전"]
    R1 --> R2["이 노드에서 오른쪽 회전"]
    Q2 -->|"아니오 · 왼쪽-왼쪽 경우"| R2
    Q1 -->|"아니오"| Q3["균형 인수가 -2 이하면 좌우를 바꿔 같은 판정"]

정렬된 키를 차례로 넣은 결과

10 부터 70 까지 일곱 키를 작은 것부터 차례로 넣어 봅니다. 보통의 이진 탐색 트리라면 높이 7 의 한 줄이 되는 순서입니다.

Node root = null;
for (int k : new int[]{10, 20, 30, 40, 50, 60, 70})
    root = insert(root, k);

root.key        // 40
root.height     // 3
root.left.key   // 20
root.right.key  // 60

넣을 때마다 무슨 일이 일어났는지를 모으면 아래와 같습니다. 새 키가 늘 오른쪽 끝으로 들어가니 기울 때마다 오른쪽-오른쪽 경우입니다. 그래서 모두 왼쪽 회전 한 번으로 끝났습니다.

아래는 50, 60, 70 을 넣고 고친 뒤의 모양을 위에서부터 차례로 쌓은 것입니다. 60 을 넣을 때 루트가 20 에서 40 으로 바뀝니다.

flowchart TD
    subgraph S50["50 을 넣고 고친 뒤"]
        P1_20["20"] --> P1_10["10"]
        P1_20 --> P1_40["40"]
        P1_40 --> P1_30["30"]
        P1_40 --> P1_50["50"]
    end
    subgraph S60["60 을 넣고 고친 뒤"]
        P2_40["40"] --> P2_20["20"]
        P2_40 --> P2_50["50"]
        P2_20 --> P2_10["10"]
        P2_20 --> P2_30["30"]
        P2_50 --> P2_60["60 · 50 의 오른쪽 자식"]
    end
    subgraph S70["70 을 넣고 고친 뒤"]
        P3_40["40"] --> P3_20["20"]
        P3_40 --> P3_60["60"]
        P3_20 --> P3_10["10"]
        P3_20 --> P3_30["30"]
        P3_60 --> P3_50["50"]
        P3_60 --> P3_70["70"]
    end
    P1_50 ~~~ P2_40
    P2_60 ~~~ P3_40

마지막 트리는 높이 3 입니다. 키 일곱 개로 만들 수 있는 가장 낮은 모양입니다.

지우기

지우기도 두 단계입니다. 먼저 보통의 이진 탐색 트리처럼 노드를 지웁니다. 그다음 루트 쪽으로 거슬러 올라 균형을 고칩니다.

자식이 둘인 노드는 오른쪽 서브트리에서 가장 작은 키를 가져와 덮어씁니다. 그리고 그 키가 있던 노드를 대신 지웁니다. 이 키를 후계자라고 부릅니다. 후계자는 오른쪽 자식에서 출발해 왼쪽으로 끝까지 내려가면 나옵니다.

10 부터 70 까지 넣어 만든 트리에서 루트 40 을 지웁니다. 40 의 오른쪽 자식 60 에서 왼쪽으로 내려가면 50 이 나옵니다.

flowchart TD
    D40["40 · 지울 노드"] --> D20["20"]
    D40 --> D60["60"]
    D20 --> D10["10"]
    D20 --> D30["30"]
    D60 --> D50["50 · 후계자 · 오른쪽 서브트리의 가장 작은 키"]
    D60 --> D70["70"]

50 을 루트에 덮어씁니다. 원래 50 이 있던 노드는 잎이라 그냥 떼어 냅니다.

flowchart TD
    E50["50 · 40 을 덮어쓴 키"] --> E20["20"]
    E50 --> E60["60 · 균형 인수 -1"]
    E20 --> E10["10"]
    E20 --> E30["30"]
    E60 --> E70["70 · 60 의 오른쪽 자식"]

60 의 균형 인수는 -1, 루트 50 은 0 입니다. 균형이 깨진 노드가 없으니 이 예에서는 회전이 일어나지 않습니다.

균형 확인은 떼어 낸 노드의 부모에서 시작합니다. 거기서 루트 쪽으로 거슬러 오릅니다. 지나온 노드마다 균형 인수를 봅니다. 균형이 깨진 노드를 만나면 넣기와 같은 기준으로 모양을 보고 네 방법 가운데 하나로 고칩니다.

지우기에는 새 키가 없습니다. 그래도 깊은 쪽 자식이 어느 쪽으로 기울었는지는 똑같이 볼 수 있습니다. 그 자식이 어느 쪽으로도 기울지 않았으면 곧은 모양처럼 회전 한 번으로 고칩니다.

지우기에서는 고칠 노드가 여럿일 수 있습니다. 넣기는 고치고 나면 그 서브트리가 넣기 전 높이로 돌아갑니다. 지우기는 고치고 나서도 지우기 전보다 한 층 낮을 수 있습니다.

그러면 그 위의 노드가 새로 기웁니다. 그 노드도 고치면서 루트까지 올라갑니다.

잎을 지우는 예입니다. 20 의 왼쪽에 10, 오른쪽에 30 이 있습니다. 30 의 오른쪽에는 40 이 달려 있습니다. 이 트리에서 10 을 지웁니다.

flowchart TD
    N20["20 · 균형 인수 -1"] --> N10["10 · 지울 노드"]
    N20 --> N30["30"]
    N30 --> N40["40"]

10 이 빠지면 20 의 왼쪽 높이는 0, 오른쪽은 2 라 균형 인수가 -2 가 됩니다. 깊은 쪽 자식 30 도 오른쪽으로 기울었으니 오른쪽-오른쪽 경우입니다. 20 에서 왼쪽 회전을 하면 30 이 올라섭니다.

flowchart TD
    N30["30 · 균형 인수 0"] --> N20["20"]
    N30 --> N40["40"]

이 트리의 높이는 지우기 전에 3 이었습니다. 고친 뒤에는 2 입니다. 이 트리가 더 큰 트리의 서브트리였다면 한 층 낮아진 탓에 그 위 노드가 새로 기울 수 있습니다.

flowchart TD
    U["위 노드 · 균형 인수 -1 → -2"] --> L["방금 고친 서브트리 · 높이 3 → 2"]
    U --> R["다른 쪽 서브트리 · 높이 4"]

넣기에서는 고친 서브트리가 넣기 전 높이로 돌아와 이런 일이 없었습니다. 지우기에서는 이 일이 루트까지 거듭될 수 있습니다. 그래서 지우기 한 번에 회전이 높이만큼, 곧 O(log n) 번 일어날 수 있습니다.

비용

찾기, 넣기, 지우기는 모두 루트에서 한 길을 따라 내려갔다 올라오는 일입니다. AVL 트리는 높이를 O(log n) 에 묶어 두므로 세 연산 모두 넣는 순서와 상관없이 O(log n) 에 끝납니다.

균형을 챙기지 않는 이진 탐색 트리는 한 줄로 기울면 세 연산 모두 O(n) 이 됩니다. O(n) 은 데이터 수에 비례해 시간이 는다는 뜻입니다. 둘을 모으면 아래와 같습니다.

넣기 한 번에 회전이 많아야 두 번인 것은 고치는 노드가 하나뿐이기 때문입니다. 그 하나를 이중 회전으로 고치면 회전이 두 번입니다.

크기 순서대로 모두 꺼내는 일은 모양과 상관없이 O(n) 입니다. 어느 노드에서든 왼쪽 서브트리, 자기, 오른쪽 서브트리 순으로 훑으면 크기 순서가 나옵니다. 이 방법을 중위 순회라고 부릅니다. 중위 순회는 노드를 한 번씩만 들릅니다.

공간은 노드 수만큼인 O(n) 을 씁니다. 노드마다 키와 두 자식을 가리키는 참조에 더해 높이를 하나 더 듭니다. 높이 대신 균형 인수만 담아도 됩니다. 균형 인수는 -1·0·1 세 값뿐이라 2 비트면 담깁니다.

레드-블랙 트리와 가르는 기준

균형 이진 탐색 트리에서 AVL 트리와 가장 흔히 견주는 짝이 레드-블랙 트리입니다. 레드-블랙 트리는 노드마다 빨강이나 검정 색을 붙입니다. 그 색에 관한 규칙으로 균형을 지킵니다.

색 규칙은 AVL 트리의 조건보다 느슨합니다. 그래서 레드-블랙 트리는 조금 더 기울도록 둡니다. 레드-블랙 트리의 높이는 log₂ n 의 2 배까지 커질 수 있습니다. AVL 트리의 상한인 약 1.44 배보다 높습니다.

두 트리가 회전 수에서 갈리는 것은 지우기입니다. 넣기는 둘 다 회전을 많아야 두 번 합니다. 지우기에서 레드-블랙 트리는 회전을 많아야 세 번 안에서 끝냅니다. AVL 트리는 지우기 한 번에 루트까지 올라가며 회전할 수 있습니다.

그래서 찾기가 넣기·지우기보다 훨씬 잦으면 AVL 트리 쪽이 비교를 덜 합니다. 지우기가 잦으면 레드-블랙 트리 쪽이 회전을 덜 합니다. 세 연산을 모두 O(log n) 에 끝낸다는 점은 둘이 같습니다.

두 트리 모두 노드마다 키에 값을 짝지어 담으면 키 순서가 지켜지는 맵이 됩니다. 「이 시각 이후의 예약」이나 「가장 작은 키」처럼 순서로 묻는 일에 이런 맵을 씁니다.

관련 항목

AVL 트리가 속하는 상위 분류

자료구조 · 트리 · 이진 트리 · 이진 탐색 트리 · 균형 이진 탐색 트리 · 자가 균형 트리

AVL 트리를 이루는 구성 요소

노드 · 루트 노드 · 리프 노드 · 부모 노드 · 자식 노드 · 서브트리 · 트리 높이 · 균형 인수

AVL 트리가 균형을 되찾는 연산

트리 회전 · 왼쪽 회전 · 오른쪽 회전 · 이중 회전 · 재균형 · 후계자 노드

AVL 트리와 같은 일을 두고 겨루는 자료구조

레드-블랙 트리 · 스플레이 트리 · 트립 · AA 트리 · 스킵 리스트 · B-tree · 해시테이블 · 연결 리스트

AVL 트리로 만드는 추상 자료형

맵 · 집합 · 정렬된 맵 · 정렬된 집합 · 심볼 테이블

AVL 트리를 훑는 순회 방법

중위 순회 · 전위 순회 · 후위 순회 · 깊이 우선 탐색 · 재귀 · 범위 검색

AVL 트리의 비용을 재는 지표

시간 복잡도 · 공간 복잡도 · 빅오 표기법 · 로그 시간 · 최악 시간 복잡도

AVL 트리의 높이 상한을 따지는 수학 도구

피보나치 수열 · 황금비 · 점화식 · 수학적 귀납법