트리

트리 구조는 부모-자식 관계를 기반으로 하나의 최상위(root) 노드를 기준으로 최하위(leaf) 노드 까지 계층적인 관계를 가지고 있다.

mermaid

graph TD
  A["root"]
  B[" "]
  C[" "]
  D[" "]
  E["leaf"]
  F[" "]
  G["leaf"]
  H["leaf"]
  I["leaf"]
  J["leaf"]
  K["leaf"]

  A --> B
  A --> C
  B --> D
  B --> E
  D --> H
  D --> I
  C --> F
  C --> G
  F --> J
  F --> K

용어는 다음과 같다.

루트(Root): 트리의 최상단에 위치한 노드를 말한다.
리프(Leaf): 자식이 없는 말단 노드를 말한다.
내부 노드(Internal): 하나 이상의 자식 노드를 가진 노드를 말한다.
서브트리(Subtree): 특정 노드를 루트로 하는 하위 트리구조를 말한다.
깊이(Depth): 루트 노드로부터 해당 노드까지의 간선 수를 말한다.
높이(Height): 트리의 최대 깊이를 말한다.
형제(Sibling): 동일한 부모를 공유하는 노드들을 말한다.

트리 구조의 종류

트리 구조는 용도에 따라 다양한 형태가 존재한다.

이진 트리(binary tree)

이진 트리란?

각 노드가 최대 2개의 자식을 가지는 트리로, 포화 이진 트리, 완전 이진 트리, 이진 탐색 트리 등이 있다.

포화 이진 트리 :

mermaid

graph TD
  A["root"]
  B[" "]
  C[" "]
  D[" "]
  E[" "]
  F[" "]
  G[" "]
  H["leaf"]
  I["leaf"]
  J["leaf"]
  K["leaf"]
  L["leaf"]
  M["leaf"]
  N["leaf"]
  O["leaf"]

  A --> B
  A --> C
  B --> D
  B --> E
  D --> H
  D --> I
  C --> F
  C --> G
  E --> N
  E --> O
  F --> J
  F --> K
  G --> L
  G --> M

모든 트리의 자식이 0개나 2개인 트리이다. 모든 leaf 노드의 높이가 같고, 리프 노드가 아닌 노드는 모두 2개의 자식을 가진다. 높이가 n일 때 노드의 수는 2^n - 1개가 된다. 모든 포화 이진 트리는 완전 이진 트리이다.

완전 이진 트리 :

mermaid

graph TD
  A["root"]
  B[" "]
  C[" "]
  D[" "]
  E[" "]
  F[" "]
  G[" "]
  H["left"]
  I["right"]
  J["left"]
  N["left"]
  O["right"]

  A --> B
  A --> C
  B --> D
  B --> E
  D --> H
  D --> I
  C --> F
  C --> G
  E --> N
  E --> O
  F --> J

모든 leaf 노드의 높이가 최대 1 차이나고, 모든 노드의 오른쪽 자식이 있으면 왼쪽은 반드시 있는 이진트리이다. 쉽게 말하자면 모든 층이 왼쪽부터 오른쪽으로 순서대로 채워나간 형태이다.

이진 탐색 트리 (BST) :
모든 노드가 아래와 같은 특정 순서를 따르는 속성이 있는 이진 트리
- 모든 왼쪽 자식들 <= N < 모든 오른쪽 자식들 (모든 노드에 대해서 반드시 참임)
- 왼쪽, 오른쪽 서브트리도 BST임

트리의 구현 방법

일반적인 트리를 구현하는 방법의 예로는 구조체를 활용하는 방법이 있다.

java

struct Node {
		int value;
		vector<Node*> children;
		Node(int val) : value(val) {}
};

장점
- 자식 수 제한 없음
단점
- 메모리 관리가 복잡해짐

이진 트리의 구현 방법

이진 트리를 구현하는 방법은 여러 가지가 있다.