트리

트리는 데이터를 「무엇이 무엇 아래에 딸렸나」로 묶어 담습니다. 맨 위 하나에서 출발해 아래로만 갈라집니다. 한 번 갈라진 쪽끼리는 다시 만나지 않습니다. 그래서 맨 위에서 어느 항목에 닿는 길도 하나뿐입니다.

상세

이 절은 노드 여섯 개짜리 작은 트리 하나를 놓고 넷을 정합니다. 트리를 이루는 부품의 이름, 트리를 트리이게 하는 제한 두 개, 트리의 크기를 재는 깊이와 높이, 그리고 트리를 짧게 적는 재귀 정의입니다.

트리가 필요한 까닭은 소속을 담는 데 있습니다. 줄 세운 목록은 순서만 담습니다. 「A 안에 B 가 있다」를 목록에 넣으려면 그 관계를 옆에 따로 적어야 합니다. 한 항목 아래 딸린 것을 모으려면 목록을 처음부터 끝까지 훑어야 합니다.

트리는 소속을 모양 자체로 담습니다. 폴더 안에 폴더가 든 파일 탐색기 화면이 그 모양입니다.

뿌리와 잎, 부모와 자식

트리는 노드와 간선으로 이루어집니다. 노드는 값을 담은 상자입니다. 값을 하나만 담는 트리가 흔하지만 여럿 담는 종류도 있습니다. 간선은 두 노드를 잇는 선입니다.

트리는 맨 위 노드 하나에서 출발해 읽습니다. 이 노드를 뿌리, 영어로 루트(root)라 합니다. 실제 나무와 반대로 대개 뿌리를 맨 위에 그리고 잎을 맨 아래에 그립니다.

간선으로 바로 아래에 매달린 노드가 자식입니다. 그 위 노드가 부모입니다. 부모가 같은 자식끼리는 형제입니다.

노드는 둘 중 하나입니다. 자식이 있으면 안쪽 노드, 없으면 잎(리프, leaf)입니다. 안쪽 노드는 자식을 하나 이상 둡니다. 노드가 뿌리 하나뿐인 트리에서는 그 뿌리가 곧 잎입니다.

서브트리는 어떤 노드의 자식을 뿌리로 삼는 트리입니다. 한 노드 아래 딸린 것을 모두 모으면 그것도 트리가 됩니다. 그 작은 트리는 큰 트리의 일부입니다.

flowchart TD
    R["뿌리 · A"] --> B["B"]
    R --> C["C"]
    subgraph SUB["A 의 서브트리 · 뿌리가 B"]
        B --> D["잎 · D"]
        B --> E["잎 · E"]
    end
    C --> F["잎 · F"]

그림에서 B 의 부모는 A 입니다. B 의 자식은 D 와 E 입니다. D 와 E 는 서로 형제입니다. D·E·F 는 자식이 없으니 잎이고, A·B·C 는 안쪽 노드입니다. 상자로 묶은 B·D·E 가 A 의 서브트리입니다.

트리를 트리이게 하는 제한 두 개

그래프는 노드와 간선을 아무렇게나 이어도 되는 모양입니다. 트리는 그 그래프에 제한 둘을 건 것입니다. 첫째, 뿌리를 뺀 노드마다 부모가 하나뿐입니다. 둘째, 간선을 따라가다 출발한 노드로 되돌아오는 길이 없습니다. 되돌아오는 이런 길을 사이클이라 합니다.

flowchart TD
    subgraph 두부모["부모가 둘 · 트리 아님"]
        A1["A"] --> C1["C"]
        B1["B"] --> C1
    end
    subgraph 되돌이["사이클이 있음 · 트리 아님"]
        A2["A"] --> B2["B"]
        B2 --> C2["C"]
        C2 --> A2
    end

「부모가 둘」 쪽은 C 의 부모가 A 와 B 둘입니다. 「사이클이 있음」 쪽은 A 에서 출발해 B·C 를 거쳐 A 로 돌아옵니다. 둘 중 하나라도 있으면 트리가 아니라 그래프입니다.

제한을 건 대가로 보장 하나를 얻습니다. 뿌리에서 어떤 노드까지 가는 길은 언제나 하나뿐입니다. 길이 하나뿐이라 트리를 훑는 쪽은 이미 다녀온 노드인지 표시해 두지 않아도 됩니다. 같은 노드를 두 번 세는 일도 생기지 않습니다.

거꾸로 보면 한 항목이 여러 곳에 동시에 속해야 할 때 트리는 맞지 않습니다. 부모가 하나라는 제한이 깨지기 때문입니다. 그때는 그래프로 담습니다.

깊이와 높이

깊이는 노드 하나에 붙는 값입니다. 그 노드에서 뿌리까지의 거리입니다. 거리는 지나는 간선 수로 셉니다. 뿌리의 깊이는 0 이고, 다른 노드의 깊이는 부모의 깊이에 1 을 더한 값입니다.

높이는 트리 전체에 붙는 값입니다. 뿌리에서 가장 먼 노드까지의 거리입니다. 가장 큰 깊이와 같은 값입니다. 노드가 뿌리 하나뿐이면 높이는 0 이고, 빈 트리의 높이는 정의되지 않습니다.

flowchart TD
    subgraph L0["깊이 0"]
        A["A"]
    end
    subgraph L1["깊이 1"]
        B["B"]
        C["C"]
    end
    subgraph L2["깊이 2"]
        D["D"]
        E["E"]
        F["F"]
    end
    A --> B
    A --> C
    B --> D
    B --> E
    C --> F

앞의 트리를 층으로 나눈 그림입니다. 가장 깊은 노드 D·E·F 의 깊이가 2 이므로 이 트리의 높이는 2 입니다.

높이를 간선 대신 노드 수로 세어 뿌리 하나짜리 트리를 1 로 치는 관례도 쓰입니다. 두 관례의 숫자는 1 씩 어긋납니다. 아래 그림과 코드는 모두 간선 수로 셉니다.

재귀로 쓰는 정의

트리를 정의하는 짧은 방법이 있습니다. 트리는 둘 중 하나입니다.

• 비어 있습니다. 노드가 하나도 없습니다
• 뿌리 하나와 서브트리 0개 이상으로 이루어집니다. 서브트리 사이에는 순서가 있습니다

이 정의는 트리를 설명하는 데 트리를 다시 씁니다. 서브트리도 트리이기 때문입니다. 그래서 트리를 다루는 코드는 대개 자기 자신을 다시 부르는 함수가 됩니다. 함수가 자기를 다시 부르는 것을 재귀라 합니다.

아래는 높이를 재는 함수입니다.

class Node:
    def __init__(self, v):
        self.v, self.kids = v, []

def height(n):
    if not n.kids:
        return 0                 # 잎이면 0
    return 1 + max(height(k) for k in n.kids)

root = Node("A")
b, c = Node("B"), Node("C")
root.kids = [b, c]
b.kids = [Node("D"), Node("E")]
c.kids = [Node("F")]

height(root)                     # 2
height(b)                        # 1

height 는 자식마다 높이를 구합니다. 그중 가장 큰 값에 자기 아래 간선 하나를 더합니다. 자식이 없는 잎에서는 0 을 돌려주고 멈춥니다.

flowchart TD
    HA["A · 2"] --> HB["B · 1"]
    HA --> HC["C · 1"]
    HB --> HD["D · 0"]
    HB --> HE["E · 0"]
    HC --> HF["F · 0"]

위 코드가 세운 트리입니다. 노드 옆 숫자가 그 노드를 뿌리로 삼은 서브트리의 높이입니다. 잎이 0 을 돌려줍니다. 한 층 올라갈 때마다 1 씩 붙어 뿌리 A 에서 2 가 됩니다.

트리를 남김없이 훑는 순서는 두 가지로 나뉩니다. 한쪽 서브트리를 끝까지 내려갔다가 되돌아 나오는 순서를 깊이 우선 탐색이라 합니다. 같은 깊이를 먼저 다 훑고 다음 깊이로 내려가는 순서를 너비 우선 탐색이라 합니다. 위 height 는 깊이 우선으로 내려갑니다.

flowchart TD
    subgraph 깊이["깊이 우선 · A B D E C F"]
        S1["1 · A"] --> S2["2 · B"]
        S2 --> S3["3 · D"]
        S2 --> S4["4 · E"]
        S1 --> S5["5 · C"]
        S5 --> S6["6 · F"]
    end
    subgraph 너비["너비 우선 · A B C D E F"]
        T1["1 · A"] --> T2["2 · B"]
        T1 --> T3["3 · C"]
        T2 --> T4["4 · D"]
        T2 --> T5["5 · E"]
        T3 --> T6["6 · F"]
    end

같은 A~F 트리에 방문 순서를 매긴 것입니다. 노드 앞 숫자가 몇 번째로 들르는지입니다.

복잡도

이 절은 값 일곱 개를 담은 이진 트리 둘을 놓고 찾기·넣기·지우기·공간에 드는 비용을 잽니다. 비용을 정하는 것은 둘입니다. 트리의 높이와, 값을 어디에 놓을지 미리 정한 규칙입니다.

「값을 놓는 규칙」은 어느 값을 어느 서브트리에 담을지 정해 둔 약속입니다. 아래 첫 소절에서 그 규칙 하나를 세워 봅니다. 이 절에서 n 은 노드 수, h 는 높이(간선 수)입니다. O(…) 는 빅오 표기법으로, 입력이 커질 때 비용이 무엇에 비례해 늘어나는지를 적습니다.

규칙이 있고 노드가 고르게 퍼져 있으면 높이가 log n 언저리라 찾기가 O(log n) 입니다. 같은 규칙이어도 노드가 한쪽으로 치우치면 높이가 n 에 가까워 O(n) 입니다. 규칙이 아예 없으면 높이와 무관하게 노드를 전부 봐야 해서 O(n) 입니다.

아래 표의 두 열은 평균과 최악이 아니라 트리의 모양으로 가른 것입니다. 고르게 퍼진 쪽이 최선이고, 한쪽으로 치우친 쪽이 최악입니다.

비교마다 떨어져 나가는 서브트리

값을 놓는 규칙을 하나 세워 봅니다. 자식을 둘까지만 둡니다. 왼쪽 서브트리에는 그 노드의 키보다 작은 값을 담고, 오른쪽 서브트리에는 그 노드의 키보다 큰 값을 담습니다. 이 규칙을 지키는 트리를 이진 탐색 트리라 합니다.

아래는 값 일곱 개(1~7)를 그 규칙대로 고르게 담은 트리입니다. 높이가 2 라서 어느 값을 찾아도 비교 세 번 안에 닿습니다.

flowchart TD
    subgraph D0["깊이 0 · 노드 1개"]
        A1["4"]
    end
    subgraph D1["깊이 1 · 노드 2개"]
        B1["2"]
        C1["6"]
    end
    subgraph D2["깊이 2 · 노드 4개"]
        E1["1"]
        F1["3"]
        G1["5"]
        I1["7"]
    end
    A1 --> B1
    A1 --> C1
    B1 --> E1
    B1 --> F1
    C1 --> G1
    C1 --> I1
    D2 -.-> D19["깊이 19 · 노드 524,288개 · 사이 층은 생략"]

자식이 둘인 트리가 층마다 꽉 차면 한 층 내려갈 때마다 그 층의 노드 수가 두 배가 됩니다. 위 그림의 층도 1개, 2개, 4개로 불어납니다. 그래서 노드가 백만 개여도 고르게 퍼져 있으면 높이는 19 입니다.

규칙이 있으면 비교 한 번에 서브트리 하나가 전부 후보에서 빠집니다. 아래는 위와 같은 트리에서 3 을 찾아 내려가는 길입니다.

flowchart TD
    P4["4 · 첫 비교"] -->|3 은 4 보다 작다| P2["2 · 둘째 비교"]
    P4 -->|노드 3개가 빠진다| P6["6"]
    P2 -->|노드 1개가 빠진다| P1["1"]
    P2 -->|3 은 2 보다 크다| P3["3 · 찾음"]
    P6 --> P5["5"]
    P6 --> P7["7"]

3 은 뿌리 4 보다 작습니다. 그래서 오른쪽 6 과 그 아래 5·7 이 한꺼번에 빠집니다. 3 은 2 보다 큽니다. 이번에는 왼쪽 1 이 빠집니다.

세 번째 비교에서 3 에 닿습니다. 노드 일곱 개 가운데 셋만 봤습니다.

한쪽으로 치우친 트리

같은 규칙으로 1 부터 7 까지를 넣습니다. 넣는 순서만 바꿔 봅니다. 작은 값부터 차례로 넣으면 모든 노드가 오른쪽 자식만 갖습니다. 트리가 연결 리스트와 같은 한 줄이 됩니다.

flowchart TD
    subgraph 치우침["차례로 넣어 치우친 트리 · 높이 6"]
        A2["1"] --> B2["2"] --> C2["3"] --> D2["4"] --> E2["5"] --> F2["6"] --> G2["7"]
    end

담긴 값은 같습니다. 높이만 2 와 6 으로 갈립니다. 치우친 쪽에서 7 을 찾으려면 노드를 전부 거쳐야 합니다. 찾는 비용이 O(n) 으로 올라갑니다. 최악은 이미 정렬된 순서로 값을 넣을 때 옵니다.

노드 수가 늘수록 두 모양의 높이는 이렇게 벌어집니다.

높이를 낮게 두는 균형

그래서 넣고 지울 때마다 모양을 손봐 높이를 낮게 유지하는 트리가 있습니다. 이런 종류를 균형 트리라 합니다. 어느 잎도 다른 잎보다 뿌리에서 훨씬 멀지 않게 유지합니다. 「훨씬」을 어떻게 정하느냐와 균형을 지키는 데 드는 일의 양은 방식마다 다릅니다.

「균형」은 대개 높이 균형, 곧 잎들의 깊이가 크게 벌어지지 않게 두는 것을 뜻합니다. 균형의 대가는 넣기·지우기 때 드는 그 손질입니다. 대신 높이가 최악에도 크게 늘어나지 않습니다. 어느 방식이 높이를 어디까지 묶어 주는지는 방식마다 다릅니다.

트리의 상당 부분이 디스크처럼 읽기 한 번이 오래 걸리는 저장 장치에 있으면 비용을 재는 단위가 바뀝니다. 비교 횟수보다 노드를 읽어 오는 횟수가 비용이 됩니다. 이때는 노드 하나에 자식을 많이 두어 높이를 낮춥니다.

자식을 여럿 둔 노드는 키도 여럿 담습니다. 그 키들이 자식 사이의 경계가 됩니다. 어느 자식으로 내려갈지는 찾는 값이 어느 키 사이에 드는지로 고릅니다. 자식 수를 크게 잡으면 높이와 읽기 횟수를 한두 번 정도로 낮게 유지할 수 있습니다.

B-tree 가 그렇게 만든 종류입니다. 생김새는 아래 「갈래」에서 봅니다.

예시

트리는 여러 제품 안에 박혀 있습니다. 성격이 다른 두 곳을 봅니다. 버전 관리 도구 Git 이 폴더를 담는 방식과, 웹 브라우저가 HTML(HyperText Markup Language) 문서를 담는 방식입니다.

Git 트리 객체

Git 은 폴더 한 층을 트리 객체 하나로 담습니다. 트리 객체 하나가 디렉터리 하나에 해당합니다. Git 은 보통 스테이징 영역, 곧 인덱스의 상태를 읽어 이런 트리 객체들을 써 냅니다.

트리 객체는 항목의 목록입니다. 항목 하나에는 모드(아래 출력의 100644·040000 같은 값)·종류·해시·파일 이름이 놓입니다. 항목은 파일 내용을 담은 blob 객체나 다른 트리 객체를 가리킵니다.

$ git cat-file -p master^{tree}
100644 blob a906cb2a4a904a152e80877d4088654daad0c859      README
100644 blob 8f94139338f9404f26296befa88755fc2598c289      Rakefile
040000 tree 99f1a6d12cb4b6f19c8655fca46c3ecf317074e0      lib

master^{tree} 는 master 브랜치의 마지막 커밋이 가리키는 트리 객체입니다. 가운데 긴 값은 SHA-1(Secure Hash Algorithm 1) 해시입니다. README 와 Rakefile 은 blob 입니다. lib 줄만 종류가 tree 입니다. lib 하위 폴더가 파일 내용이 아니라 또 다른 트리 객체를 가리킨다는 뜻입니다.

그 해시로 lib 트리 객체를 열면 한 층 아래가 나옵니다.

$ git cat-file -p 99f1a6d12cb4b6f19c8655fca46c3ecf317074e0
100644 blob 47c6340d6459e05787f644c2447d2595f5d3a54b      simplegit.rb

flowchart TD
    T0["트리 객체 · 맨 위 폴더"] --> R["blob · README"]
    T0 --> K["blob · Rakefile"]
    T0 --> L["트리 객체 · lib"]
    L --> S["blob · simplegit.rb"]

두 출력을 이으면 이 모양입니다. 트리 객체가 안쪽 노드입니다. blob 은 잎입니다. lib 트리 객체와 그 아래 simplegit.rb 가 맨 위 트리의 서브트리입니다.

DOM 노드 트리

웹 브라우저는 HTML 문서를 읽어 노드 트리로 담습니다. 이 트리를 다루는 모델이 DOM(Document Object Model, 문서 객체 모델)입니다. DOM 의 트리는 노드 수가 유한한 계층 구조입니다.

트리에 든 객체마다 부모를 가리키는 칸이 하나 있습니다. 그 칸이 비어(null) 있는 객체가 그 트리의 뿌리입니다. 자식은 순서가 정해진 모음입니다. 앞 상세에서 본 트리와 같은 짜임입니다.

<!DOCTYPE html>
<html class=e>
 <head><title>Aliens?</title></head>
 <body>Why yes.</body>
</html>

이 문서는 아래 노드 트리가 됩니다.

flowchart TD
    DOC["Document"] --> DT["Doctype: html"]
    DOC --> H["Element: html class=e"]
    H --> HE["Element: head"]
    HE --> TI["Element: title"]
    TI --> T1["Text: Aliens?"]
    H --> WS["Text: 줄바꿈과 공백"]
    H --> BO["Element: body"]
    BO --> T2["Text: Why yes. 와 줄바꿈"]

마크업이 들어가면 노드 트리가 나옵니다. html 요소 아래에 head·body 가 자식으로 매달립니다. 그 둘 사이의 줄바꿈과 공백은 Text 노드 하나가 됐습니다.

공백이 전부 노드가 되지는 않았습니다. <html class=e> 와 <head> 사이의 줄바꿈은 Text 노드로 남지 않았습니다. HTML 파싱 규칙 때문에 모든 공백이 Text 노드가 되지는 않습니다.

DOM 은 이 트리를 훑는 기본 순서도 정해 둡니다. 그 순서를 트리 순서(tree order)라 합니다. 깊이 우선으로 훑는 순서입니다. 그 가운데 부모를 자식보다 먼저 들르는 전위 순회입니다. 위 그림이면 Document, Doctype, html, head, title, 「Aliens?」 순으로 들릅니다.

경계

그래프 이론의 트리와 자료구조의 트리는 같은 것인가. 아닙니다. 담는 모양은 같습니다. 무엇을 서로 다른 트리로 세느냐가 갈립니다.

그래프 이론의 트리는 연결돼 있고 사이클이 없는 무방향 그래프입니다. 무방향은 간선에 방향이 없다는 뜻입니다. 부모에서 자식으로 내려가는 화살표가 아니라 두 노드를 잇는 선만 있습니다. 따로 밝히지 않으면 뿌리가 정해져 있다고 봅니다. 자식 순서도 있다고 봅니다. 뿌리마저 없는 것은 자유 트리(free tree)로 따로 다룹니다.

자료구조의 트리는 앞 상세의 재귀 정의를 따릅니다. 비어 있거나, 뿌리 하나와 순서 있는 서브트리들로 이루어집니다.

차이는 노드 둘짜리 이진 트리에서 드러납니다. 이진 트리는 노드마다 자식을 둘까지 둡니다. 그리고 왼쪽 자식과 오른쪽 자식을 가릅니다. 자료구조로는 두 가지가 나옵니다. 뿌리와 왼쪽 서브트리, 그리고 뿌리와 오른쪽 서브트리입니다.

flowchart TD
    subgraph 자료구조1["자료구조 · 첫째"]
        R1["뿌리"] -->|왼쪽| L1["자식"]
    end
    subgraph 자료구조2["자료구조 · 둘째"]
        R2["뿌리"] -->|오른쪽| L2["자식"]
    end
    subgraph 그래프["그래프 · 하나뿐"]
        R3["뿌리"] --- L3["자식"]
    end

그래프로는 하나뿐입니다. 뿌리와 서브트리 하나입니다. 간선에 방향이 없으니 그래프 쪽 그림에는 화살표가 없습니다. 그래프 정의에는 「이 서브트리는 오른쪽이고 왼쪽은 비었다」를 적을 방법이 없습니다. 그리고 그래프의 트리에는 「빈 트리」가 없습니다.

모든 노드의 자식에 첫째·둘째·셋째 순서가 매겨진 트리를 순서 트리(ordered tree)라 합니다. 순서가 없는 트리는 재귀적인 주머니로, 순서 트리는 재귀적인 리스트로 볼 수 있습니다. 주머니는 순서 없이 같은 것을 여럿 담는 모음입니다.

자료구조의 트리는 순서 트리입니다. 그래프 이론의 트리도 따로 밝히지 않으면 순서가 있다고 봅니다. 자식 순서는 두 뜻을 가르는 차이가 아니라 둘이 함께 두는 전제입니다. 두 뜻을 가르는 것은 위 표의 빈 트리와 한쪽이 빈 자식입니다.

갈래

트리의 종류는 두 축으로 갈립니다. 하나는 노드 하나가 자식을 몇 개까지 두나입니다. 다른 하나는 값을 어떤 규칙으로 놓나입니다. 여기에 높이나 모양에 조건을 더 거는 종류도 있습니다.

이 절에서 「키」는 노드가 담은 값 가운데 비교에 쓰는 값입니다.

이진 트리

노드마다 자식을 많아야 둘 두는 트리입니다. 자식 수 축에서 상한을 둘로 고정한 종류입니다. 정의도 재귀입니다. 이진 트리는 비어 있거나, 뿌리 하나와 왼쪽 이진 트리와 오른쪽 이진 트리로 이루어집니다.

값을 놓는 규칙은 따로 없습니다. 규칙을 얹으면 이진 탐색 트리나 이진 힙 같은 하위 종류가 됩니다.

다진 트리

노드마다 자식을 몇 개든 둘 수 있는 트리입니다. 앞 「예시」의 Git 트리 객체와 DOM 노드 트리가 이쪽입니다.

흔한 구현은 노드마다 자식 노드의 목록을 하나씩 두는 것입니다. 자식 칸을 고정 개수로 두는 구현도 있습니다. 그 구현에서는 자식이 고정 칸보다 많은 드문 노드만 넘친 자식을 연결 리스트로 매답니다.

탐색 트리

값을 놓는 규칙 축에 서는 종류입니다. 노드의 어느 서브트리든 그 오른쪽 서브트리들보다 작은 키만 담습니다. 노드 안의 키는 개념상 서브트리 사이에 놓입니다. 왼쪽 서브트리의 키보다 크고 오른쪽 서브트리의 키보다 작습니다.

flowchart TD
    N["노드 · 키 30 · 60"] --> S1["서브트리 · 키가 30 보다 작다"]
    N --> S2["서브트리 · 키가 30 과 60 사이"]
    N --> S3["서브트리 · 키가 60 보다 크다"]

그림의 노드는 키 둘을 담았습니다. 키 30 과 60 이 자식 셋을 가릅니다. 찾는 값이 30 보다 작으면 첫 자식으로, 30 과 60 사이면 가운데 자식으로, 60 보다 크면 마지막 자식으로 내려갑니다.

탐색 트리이면서 이진 트리이면 이진 탐색 트리입니다. 노드마다 키 하나와 자식 둘이 됩니다. 앞 「복잡도」에서 3 을 찾아 내려간 트리가 그것입니다.

균형 트리

어느 잎도 다른 잎보다 뿌리에서 훨씬 멀지 않은 트리입니다. 앞 「복잡도」의 치우친 트리를 막는 종류입니다. AVL(Adelson-Velskii and Landis) 트리와 레드-블랙 트리가 여기 듭니다. 이 둘은 이진 탐색 트리이기도 합니다.

B-tree

균형 트리이면서 탐색 트리입니다. 노드마다 자식을 ⌈m/2⌉ 개에서 m 개 사이로 둡니다. m 은 1 보다 큰 고정 정수입니다. m 을 트리의 차수라 합니다. 뿌리만은 자식이 둘뿐이어도 됩니다.

앞 「복잡도」에서 본 대로 트리의 상당 부분이 디스크에 있을 때 맞는 구조입니다. m 을 크게 잡아 높이와 읽기 횟수를 낮게 유지할 수 있기 때문입니다. 노드 하나가 키 여럿을 담고, 그 키들이 자식 사이의 경계가 됩니다.

힙

힙은 완전 트리에 키 규칙 하나를 더한 종류입니다. 완전 트리는 마지막 층을 뺀 모든 층이 꽉 차고, 마지막 층은 왼쪽부터 채운 트리입니다. 여기에 붙는 규칙은 하나입니다. 모든 노드의 키는 부모의 키와 같거나 정한 한 방향으로 부모보다 치우칩니다.

자식이 늘 부모보다 크거나 같으면 뿌리에 가장 작은 키가 옵니다. 반대로 정하면 뿌리에 가장 큰 키가 옵니다.

flowchart TD
    subgraph 힙모양["힙 · 뿌리에 가장 작은 키"]
        Q1["1"] --> Q2["2"]
        Q1 --> Q3["3"]
        Q2 --> Q4["4"]
        Q2 --> Q5["5"]
        Q3 --> Q6["6"]
        Q3 --> Q7["7"]
    end

같은 값 일곱 개를 이진 탐색 트리로 담았을 때는 뿌리가 4 였습니다. 힙으로 담으면 뿌리가 1 입니다. 담는 값이 같아도 놓는 규칙이 다르면 모양이 달라집니다.

그냥 힙이라 하면 대개 이진 힙을 뜻합니다. 우선순위 큐와 힙 정렬이 이 구조를 씁니다.

운영체제에서 말하는 힙은 다른 것입니다. 거기서는 메모리 덩어리를 떼어 나눠 주는 영역을 가리킵니다.

트라이

문자열을 담는 트리입니다. 공통 접두어마다 노드가 하나 있습니다. 문자열 자체는 끝에 덧붙인 잎 노드에 담깁니다.

flowchart TD
    TR["뿌리"] --> TC["c"]
    TC --> TCA["ca"]
    TCA --> TCAR["car"]
    TCA --> TCAT["cat"]
    TCAR --> TLR["잎 · car"]
    TCAT --> TLT["잎 · cat"]

car 와 cat 은 접두어 c 와 ca 를 함께 씁니다. 그래서 그 두 노드를 나눠 쓰고 그 아래에서 갈라집니다. 문자열은 맨 끝에 덧붙인 잎에 놓입니다.

이름은 reTRIEval 에서 왔습니다. 읽기는 「트리」와 같습니다.

관련 항목

트리가 속하는 상위 분류

자료구조 · 비선형 자료구조 · 그래프 · 계층 구조

트리를 이루는 구성 요소

노드 · 간선 · 루트 노드 · 리프 노드 · 부모 노드 · 자식 노드 · 형제 노드 · 서브트리 · 포인터

트리의 모양과 비용을 재는 지표

트리 높이 · 노드 깊이 · 차수 · 트리 균형 · 분기 계수 · 빅오 표기법 · 시간 복잡도 · 공간 복잡도

트리의 하위 종류

이진 트리 · 다진 트리 · 완전 트리 · 완전 이진 트리 · 탐색 트리 · 이진 탐색 트리 · 균형 트리 · 균형 이진 트리 · AVL 트리 · 레드-블랙 트리 · 스플레이 트리 · B-tree · B+tree · 2-3 트리 · 힙 · 이진 힙 · 피보나치 힙 · 트라이 · 패트리샤 트리 · 머클 트리 · LSM 트리 · 세그먼트 트리

그래프 이론에서 트리와 맞세워지는 개념

자유 트리 · 순서 트리 · 루트 트리 · 포레스트 · 사이클 · DAG · 신장 트리 · 최소 신장 트리

트리를 훑는 순회 방법

트리 순회 · 깊이 우선 탐색 · 너비 우선 탐색 · 전위 순회 · 중위 순회 · 후위 순회 · 재귀 · 백트래킹

트리를 안에 두고 동작하는 정렬과 자료형

힙 정렬 · 트리 정렬 · 우선순위 큐 · 심볼 테이블

트리로 데이터를 담는 시스템과 포맷

파일 시스템 · 디렉터리 · DOM · HTML · 추상 구문 트리 · Git · 트리 객체 · blob 객체 · 인덱스 · 네임스페이스 · XML · JSON

이름에 트리가 붙은 다른 개념

작업 트리 · 렌더 트리 · 박스 트리 · 결정 트리

트리와 겨루는 다른 담는 모양

배열 · 연결 리스트 · 해시테이블 · 스택 · 큐 · 집합 · 인접 리스트