사전 이진 탐색 트리
자료구조

이진 탐색 트리

gabury1고친 사람 github-actions[bot]

이진 탐색 트리는 값을 크기 순서가 지켜지게 담아 두고 빨리 찾아 줍니다. 값마다 자기보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 둡니다. 그래서 찾을 때마다 한쪽 길만 따라 내려갑니다. 새 값을 넣어도 이 순서가 깨지지 않습니다.

쉽고 빠른 이해

이진 탐색 트리는 값을 크기 순서대로 담아 두고 몇 번의 비교만으로 찾아 줍니다. 회원 번호 백만 개를 한쪽으로 치우치지 않게 담아 두면 「1042 번이 있나」에 스무 번 남짓 비교하고 답합니다.

정렬된 배열도 빨리 찾을 수 있습니다. 하지만 중간에 값을 하나 넣으려면 그 뒤의 값을 전부 한 칸씩 밀어야 합니다. 이 트리는 새 값을 빈 곳에 매달기만 해서 넣을 때도 빨리 끝납니다.

  1. 값마다 자기보다 작은 값은 왼쪽 아래에, 큰 값은 오른쪽 아래에 둡니다
  2. 찾을 때는 맨 위부터 비교하며 왼쪽이나 오른쪽 한쪽으로만 내려갑니다
  3. 넣을 때는 찾다가 막힌 빈 곳에 새 값을 매답니다

대가는 넣는 순서가 모양을 정한다는 것입니다. 작은 값부터 차례로 넣으면 한 줄로 늘어서서 처음부터 훑는 것과 같아집니다. 이걸 막으려고 넣고 지울 때마다 모양을 고르게 다듬는 종류를 따로 씁니다.

상세

먼저 트리 용어와 크기 순서를 지키는 규칙을 세웁니다. 그다음 값 일곱 개를 담은 트리 하나로 찾기·꺼내기·넣기·지우기를 차례로 봅니다. 마지막으로 약점과 해시테이블과의 선택 기준을 봅니다.

노드와 두 자식

트리는 데이터를 위에서 아래로 갈라지게 담는 자료구조입니다. 값을 담은 상자 하나하나가 노드입니다.

맨 위 노드 하나가 루트입니다. 찾기도 넣기도 언제나 루트에서 시작합니다.

어떤 노드 바로 아래에 붙은 노드는 그 노드의 자식입니다. 바로 위 노드는 부모입니다. 자식이 하나도 없는 노드는 잎입니다.

이진 트리는 노드마다 자식을 둘까지만 두는 트리입니다. 두 자식은 왼쪽 자식과 오른쪽 자식으로 구별합니다. 자식이 없는 쪽은 비워 둡니다.

한 노드와 그 아래에 딸린 노드를 모두 묶은 것이 서브트리입니다. 왼쪽 자식 아래를 모두 묶으면 왼쪽 서브트리, 오른쪽 자식 아래를 모두 묶으면 오른쪽 서브트리입니다. 아래 그림은 이 이름들을 트리 하나에 붙인 것입니다.

flowchart TD
    R["루트"]
    subgraph 왼쪽["루트의 왼쪽 서브트리"]
        A["왼쪽 자식 · 아래 둘의 부모"] --> A1["잎"]
        A --> A2["잎"]
    end
    subgraph 오른쪽["루트의 오른쪽 서브트리"]
        B["오른쪽 자식 · 아래 둘의 부모"] --> B1["잎"]
        B --> B2["잎"]
    end
    R --> A
    R --> B

노드에 담겨 크기를 비교하는 값을 키라고 부릅니다. 회원 번호로 회원을 찾는다면 회원 번호가 키입니다. 키마다 회원 정보 같은 값을 짝지어 담으면 키로 값을 찾는 맵이 됩니다.

크기 순서를 지키는 규칙

이진 탐색 트리는 이진 트리에 규칙 하나를 더 겁니다. 어느 노드에서 봐도 왼쪽 서브트리의 키는 모두 그 노드의 키보다 작습니다. 오른쪽 서브트리의 키는 모두 그 노드의 키보다 큽니다.

이 편에서는 같은 키를 두 번 담지 않습니다. 이미 있는 키가 또 오면 새 노드를 만들지 않습니다. 맵으로 쓸 때는 그 키에 짝지은 회원 정보만 새것으로 바꿉니다.

아래는 키 일곱 개 20·30·40·50·60·70·80 을 이 규칙대로 담은 트리입니다. 찾기부터 지우기까지 이 트리로 설명합니다.

flowchart TD
    N50["50"] --> N30["30"]
    N50 --> N70["70"]
    N30 --> N20["20"]
    N30 --> N40["40"]
    N70 --> N60["60"]
    N70 --> N80["80"]

루트 50 의 왼쪽에는 50 보다 작은 20·30·40 이 모였습니다. 오른쪽에는 50 보다 큰 60·70·80 이 모였습니다. 30 과 70 에서 봐도 같은 규칙이 섭니다.

규칙은 바로 아래 자식만이 아니라 서브트리 전체에 걸립니다. 비어 있는 40 의 오른쪽에 55 를 매달았다고 해 봅시다. 55 는 40 보다도 30 보다도 크니 바로 위 두 노드와는 맞는 방향입니다. 그러나 55 는 루트 50 의 왼쪽 서브트리에 들어가 있습니다.

flowchart TD
    N50["50 · 루트"]
    subgraph 왼쪽["50 의 왼쪽 서브트리 · 모두 50 보다 작아야 함"]
        N30["30"] --> N20["20"]
        N30 --> N40["40"]
        N40 --> N55["55 · 50 보다 큼 · 규칙 깨짐"]
    end
    N50 --> N30
    N50 --> N70["70"]
    N70 --> N60["60"]
    N70 --> N80["80"]
    classDef bad stroke-width:4px
    class N55 bad

50 보다 큰 키가 50 의 왼쪽에 있으니 규칙이 깨진 것입니다. 55 를 찾으면 루트에서 오른쪽으로 가므로 이 노드에는 영영 닿지 못합니다.

코드로 적으면 노드 하나는 키 하나와 자식을 가리키는 포인터 둘입니다.

Java
class Node {
    int key;
    Node left;   // 작은 쪽 자식
    Node right;  // 큰 쪽 자식
}

자식이 없는 쪽은 null 입니다. 잎은 left 와 right 가 둘 다 null 인 노드입니다. 맵으로 쓰려면 짝지은 회원 정보를 담을 칸을 하나 더 둡니다. 이 편의 코드는 키만 다룹니다.

찾기

찾기는 루트에서 출발해 한 층씩 내려갑니다. 찾는 키가 지금 노드의 키보다 작으면 왼쪽 자식으로, 크면 오른쪽 자식으로 갑니다. 같으면 찾은 것입니다. 내려갈 자식이 없으면 그 키는 트리에 없습니다.

60 을 찾아 봅니다. 60 은 루트 50 보다 크니 오른쪽 70 으로 갑니다. 70 보다는 작으니 왼쪽 60 으로 갑니다. 세 번 비교하고 찾았습니다.

flowchart TD
    N50["50 · 1번째 비교"] --> N30["30"]
    N50 --> N70["70 · 2번째 비교"]
    N30 --> N20["20"]
    N30 --> N40["40"]
    N70 --> N60["60 · 3번째 비교 · 찾음"]
    N70 --> N80["80"]
    classDef skip stroke-dasharray: 4 4
    class N30,N20,N40,N80 skip

점선으로 그린 노드는 한 번도 보지 않았습니다. 첫 비교에서 왼쪽 서브트리의 노드 셋이 한꺼번에 빠졌습니다. 두 번째 비교에서 80 이 빠졌습니다.

코드로 옮기면 반복문 하나입니다.

Java
Node find(Node n, int key) {
    while (n != null && n.key != key) {
        n = key < n.key ? n.left : n.right;
    }
    return n;
}

반복문 한 바퀴가 한 층입니다. 키가 같은 노드를 만나거나 더 내려갈 노드가 없으면 멈춥니다. 앞의 트리에서 불러 본 결과가 아래입니다.

Java
find(root, 60).key  // 60
find(root, 65)      // null

65 는 50, 70, 60 을 거쳐 60 의 오른쪽에서 멈춥니다. 거기는 비어 있으니 65 는 없습니다. 이 빈 곳은 뒤의 「넣기」에서 다시 씁니다.

이 움직임은 정렬된 배열에서 하는 이진 탐색과 닮았습니다. 이진 탐색은 가운데 값과 비교해 답이 없는 쪽 절반을 버립니다. 20 부터 80 까지 일곱 키를 배열에 늘어놓고 이진 탐색을 하면 처음 보는 가운데 값이 50 입니다. 그다음은 30 이나 70 입니다.

앞의 트리는 그 가운데 값들을 미리 노드로 세워 둔 모양입니다. 이 트리처럼 층마다 노드가 빈 곳 없이 차 있는 모양을 고르게 퍼졌다고 합니다. 트리가 고르게 퍼져 있으면 한 번 비교할 때마다 남은 후보가 절반쯤으로 줄어듭니다.

크기 순서대로 꺼내기

이 트리는 키를 크기 순서대로 꺼낼 수 있습니다. 해시테이블과 갈리는 점이 이것입니다. 넣을 때 지킨 규칙, 곧 왼쪽은 작고 오른쪽은 크다는 것을 꺼낼 때 그대로 읽으면 됩니다.

어느 노드에서든 왼쪽 서브트리를 먼저 다 꺼냅니다. 그다음 그 노드를 꺼냅니다. 마지막으로 오른쪽 서브트리를 꺼냅니다. 이렇게 훑는 방법을 중위 순회라고 부릅니다.

왼쪽 키는 모두 그 노드보다 작습니다. 오른쪽 키는 모두 그 노드보다 큽니다. 그래서 이 순서가 곧 크기 순서입니다.

Java
void inorder(Node n, List<Integer> out) {
    if (n == null) return;
    inorder(n.left, out);
    out.add(n.key);
    inorder(n.right, out);
}

inorder 는 왼쪽과 오른쪽 서브트리에 자기 자신을 다시 부릅니다. 이렇게 함수가 자기를 다시 부르는 방식이 재귀입니다. 서브트리도 규칙을 지키는 이진 탐색 트리라서 같은 함수를 다시 쓸 수 있습니다.

Java
inorder(root, out);
out  // [20, 30, 40, 50, 60, 70, 80]

가장 작은 키는 루트에서 왼쪽 자식으로만 끝까지 내려가면 나옵니다. 앞의 트리에서는 50, 30 을 거쳐 20 입니다. 가장 큰 키는 오른쪽으로만 내려가서 80 입니다.

「40 이상 60 이하」처럼 범위로 찾을 때도 이 순서를 씁니다. 중위 순회를 하되 범위 밖이 확실한 서브트리에는 들어가지 않습니다.

30 은 40 보다 작으니 그 왼쪽의 20 은 볼 필요가 없습니다. 70 은 60 보다 크니 그 오른쪽의 80 도 볼 필요가 없습니다. 남는 답은 40·50·60 입니다. 아래 그림에서 점선이 들어가지 않은 노드입니다.

flowchart TD
    N50["50 · 답"] --> N30["30 · 들렀지만 범위 밖"]
    N50 --> N70["70 · 들렀지만 범위 밖"]
    N30 --> N20["20 · 건너뜀"]
    N30 --> N40["40 · 답"]
    N70 --> N60["60 · 답"]
    N70 --> N80["80 · 건너뜀"]
    classDef skip stroke-dasharray: 4 4
    class N20,N80 skip

넣기

넣기는 찾기와 같은 길을 갑니다. 넣을 키로 찾기를 해서 막힌 빈 곳에 새 노드를 매답니다. 이미 있는 노드는 하나도 움직이지 않습니다.

65 를 넣어 봅니다. 앞의 「찾기」에서 65 는 60 의 오른쪽 빈 곳에서 멈췄습니다. 거기에 65 를 매답니다.

flowchart TD
    N50["50"] --> N30["30"]
    N50 --> N70["70"]
    N30 --> N20["20"]
    N30 --> N40["40"]
    N70 --> N60["60"]
    N70 --> N80["80"]
    N60 --> N65["65 · 60 의 오른쪽에 새로 매단 노드"]

65 는 50 보다 큽니다. 70 보다는 작습니다. 60 보다는 큽니다. 지나온 세 노드와 맺어야 할 크기 관계를 모두 지키는 빈 곳은 그 하나뿐입니다.

정렬된 배열에 65 를 넣는다면 사정이 다릅니다. 60 과 70 사이에 칸을 내려면 70 과 80 을 한 칸씩 뒤로 밀어야 합니다. 값이 n 개일 때 맨 앞에 넣으면 n 개를 모두 밉니다.

트리는 루트에서 내려온 한 길만 거치고 끝납니다. 이진 탐색 트리가 있는 까닭이 이 차이입니다.

지우기

지우기는 넣기보다 손이 더 갑니다. 지운 노드 아래에 딸린 노드들이 옮겨 갈 곳을 정해 줘야 하기 때문입니다. 이 절은 앞에서 65 를 넣은 트리에서 루트 50 을 지우는 데까지 갑니다. 먼저 지울 노드의 자식 수에 따라 하는 일이 셋으로 갈립니다.

지울 노드 하는 일
자식이 없다 그 노드만 떼어 냅니다
자식이 하나다 그 자식을 지운 노드가 있던 곳으로 올립니다
자식이 둘이다 오른쪽 서브트리에서 가장 작은 키를 가져와 덮어씁니다. 그 키가 있던 노드를 대신 지웁니다

첫째 경우는 규칙을 깨지 않습니다. 잎을 떼어 내도 남은 노드들 사이의 크기 관계는 하나도 안 바뀝니다.

둘째 경우도 규칙을 깨지 않습니다. 한 칸 올라오는 자식의 서브트리는 원래도 조상 노드마다 같은 쪽에 있었습니다. 올라온 뒤에도 그 쪽을 떠나지 않으니 조상과 맺은 크기 관계가 그대로입니다.

셋째 경우에 가져오는 키를 후계자라고 부릅니다. 지울 키보다 큰 키 가운데 가장 작은 키입니다. 크기 순서로 늘어놓으면 지울 키 바로 다음에 옵니다. 오른쪽 자식으로 한 번 간 뒤 왼쪽 자식으로만 끝까지 내려가면 나옵니다.

후계자를 올려도 규칙은 지켜집니다. 왼쪽 서브트리의 키는 원래 지울 키보다 작았으니 후계자보다도 작습니다. 오른쪽에 남은 키는 모두 후계자보다 큽니다. 후계자가 오른쪽에서 가장 작은 키였기 때문입니다.

후계자가 있던 노드는 쉽게 지워집니다. 후계자는 왼쪽으로 끝까지 내려가 찾은 노드라서 왼쪽 자식이 없습니다. 그래서 첫째나 둘째 경우로 끝납니다.

이제 루트 50 을 지웁니다. 50 은 자식이 둘입니다. 오른쪽 자식 70 에서 왼쪽으로만 내려가면 60 에 닿으니 60 이 후계자입니다. 아래는 지우기 전의 트리입니다.

flowchart TD
    N50["50 · 지울 노드"] --> N30["30"]
    N50 --> N70["70 · 오른쪽 자식"]
    N30 --> N20["20"]
    N30 --> N40["40"]
    N70 -->|"왼쪽으로만"| N60["60 · 후계자"]
    N70 --> N80["80"]
    N60 --> N65["65 · 한 칸 올라갈 노드"]

60 을 루트로 올립니다. 60 이 있던 노드는 오른쪽 자식 65 하나만 있으니 둘째 경우입니다. 65 를 한 칸 올려 70 의 왼쪽 자식으로 만듭니다. 아래는 지운 뒤의 트리입니다.

flowchart TD
    N60["60 · 후계자가 루트로 올라옴"] --> N30["30"]
    N60 --> N70["70"]
    N30 --> N20["20"]
    N30 --> N40["40"]
    N70 --> N65["65 · 한 칸 올라옴"]
    N70 --> N80["80"]

지운 뒤에 중위 순회를 하면 20·30·40·60·65·70·80 이 나옵니다. 50 만 빠지고 크기 순서는 그대로입니다.

높이가 정하는 비용

찾기, 넣기, 지우기는 모두 루트에서 한 길을 따라 내려가는 일입니다. 그래서 드는 시간은 트리가 얼마나 깊은지가 정합니다.

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

노드가 층마다 꽉 차 있으면 한 층 내려갈 때마다 담기는 노드 수가 두 배로 늡니다. 높이가 20 이면 백만 개 넘게 담깁니다. 앞에서 고르게 퍼졌다고 부른 모양이 이것입니다. 이때 높이는 노드 수 n 의 로그, 곧 log n 언저리에 머뭅니다.

flowchart TD
    subgraph L1["1층 · 1개"]
        A1["노드"]
    end
    subgraph L2["2층 · 2개"]
        B1["노드"]
        B2["노드"]
    end
    subgraph L3["3층 · 4개"]
        C1["노드"]
        C2["노드"]
        C3["노드"]
        C4["노드"]
    end
    subgraph L4["4층부터 20층까지 · 층마다 두 배"]
        D["20층 한 층에만 약 52만 개 · 모두 합쳐 백만 개 남짓"]
    end
    A1 --> B1
    A1 --> B2
    B1 --> C1
    B1 --> C2
    B2 --> C3
    B2 --> C4
    C1 & C2 & C3 & C4 -.-> D

이때 드는 시간을 빅오 표기법으로 O(log n) 이라고 적습니다. 데이터가 두 배로 늘어도 비교는 한 번씩만 는다는 뜻입니다.

규칙은 크기 관계만 정합니다. 모양은 정하지 않습니다. 모양은 넣는 순서가 정합니다.

같은 일곱 키를 20, 30, 40 처럼 작은 것부터 차례로 넣으면 새 키가 늘 지금까지의 가장 큰 키보다 큽니다. 그래서 매번 오른쪽 끝에만 매달립니다.

flowchart TD
    subgraph 치우침["작은 키부터 차례로 넣은 트리 · 높이 7"]
        A["20"] --> B["30"] --> C["40"] --> D["50"] --> E["60"] --> F["70"] --> G["80"]
    end

이 트리는 높이가 7 입니다. 80 을 찾으려면 일곱 노드를 모두 거칩니다. 트리가 연결 리스트와 같은 한 줄이 되어 드는 시간이 O(n) 이 됐습니다. O(n) 은 데이터 수에 비례해 시간이 는다는 뜻입니다.

키가 무작위 순서로 들어오면 대개 고르게 퍼집니다. 이미 정렬된 데이터를 차례로 넣으면 위처럼 한 줄이 됩니다.

이를 막으려고 넣고 지울 때마다 노드 몇 개의 부모와 자식을 바꿔 걸어 높이를 낮게 붙잡는 종류가 따로 있습니다. 이런 트리를 균형 이진 탐색 트리라고 부릅니다. 레드-블랙 트리가 그 가운데 하나입니다.

두 모양의 비용을 모으면 이렇습니다.

연산 고르게 퍼졌을 때 한 줄로 치우쳤을 때
찾기 O(log n) O(n)
넣기 O(log n) O(n)
지우기 O(log n) O(n)
크기 순서대로 모두 꺼내기 O(n) O(n)

모두 꺼내기는 모양과 상관없이 노드를 한 번씩 들르니 O(n) 입니다. 공간도 노드 수만큼인 O(n) 을 씁니다. 노드마다 키 말고도 자식을 가리키는 포인터 둘을 더 들고 있습니다.

해시테이블과 가르는 기준

키로 값을 찾는 맵은 해시테이블로도 만듭니다. 둘 가운데 무엇을 고를지는 크기 순서가 필요한지로 갈립니다.

해시테이블은 키를 해시 함수로 번호로 바꿔 흩어 담습니다. 그래서 키 하나를 평균 O(1) 로 찾습니다. O(1) 은 데이터가 늘어도 걸리는 시간이 거의 늘지 않는다는 뜻입니다. 대신 흩어 담은 탓에 키 사이의 크기 순서가 남지 않습니다.

하려는 일 해시테이블 이진 탐색 트리
키 하나 찾기 평균 O(1) 고르게 퍼지면 O(log n)
크기 순서대로 모두 꺼내기 따로 정렬해야 한다 중위 순회 한 번
범위로 찾기 모두 훑어야 한다 필요한 서브트리만 내려간다
가장 작은 키 · 가장 큰 키 모두 훑어야 한다 한쪽 끝까지 내려간다

키 하나를 넣고 꺼내기만 하면 해시테이블 쪽이 비교를 덜 합니다. 「가장 이른 예약」이나 「이 시각 앞뒤의 기록」처럼 순서를 묻는 일이 있으면 이진 탐색 트리를 고릅니다.

데이터베이스 인덱스도 「이 날짜 이후의 주문」처럼 범위로 찾는 일이 잦습니다. 그래서 인덱스는 해시테이블보다 크기 순서를 지키는 트리 쪽을 흔히 씁니다.

디스크에 담는 인덱스가 흔히 쓰는 B-tree는 이 규칙을 넓힌 트리입니다. 노드 하나에 키를 여럿 담습니다. 키와 키 사이마다 자식을 하나씩 두어 자식이 수백 개까지 늡니다.

디스크에서는 노드 하나를 읽을 때마다 시간이 크게 듭니다. 층 수가 곧 읽는 횟수입니다. 자식을 많이 두어 높이를 낮추는 까닭이 이것입니다.

관련 항목

이진 탐색 트리가 속하는 상위 분류

자료구조 · 트리 · 이진 트리 · 비선형 자료구조 · 탐색 트리

이진 탐색 트리로 만드는 추상 자료형

맵 · 연관 배열 · 딕셔너리 · 집합 · 심볼 테이블

이진 탐색 트리를 이루는 구성 요소

노드 · 루트 노드 · 리프 노드 · 부모 노드 · 자식 노드 · 서브트리 · 포인터 · 후계자 노드

이진 탐색 트리의 하위 종류

균형 이진 탐색 트리 · AVL 트리 · 레드-블랙 트리 · 스플레이 트리 · 트립 · AA 트리

이진 탐색 트리를 훑는 탐색·순회 방법

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

이진 탐색 트리의 비용을 재는 지표

시간 복잡도 · 공간 복잡도 · 빅오 표기법 · 트리 높이 · 트리 균형

이진 탐색 트리와 겨루는 다른 담는 모양

해시테이블 · 정렬된 배열 · 연결 리스트 · 스킵 리스트 · B-tree · B+tree · 힙 · 트라이

이진 탐색 트리를 바탕으로 만든 정렬 컬렉션

TreeMap · TreeSet · 정렬된 맵 · 정렬된 집합

다른 이름: binary search tree · BST · 이진 검색 트리