자료구조와 알고리즘

트리(Tree)

begin-play 2026. 9. 1. 21:14

트리(Tree)

1. Tree란?

이번 학습에서는 Tree(트리) 자료구조에 대해 공부하였다.

지금까지 학습했던 배열, 연결 리스트, 스택, 큐 등의 자료구조는 데이터를 일렬로 표현하는 형태가 많았다. 반면 Tree는 데이터를 계층적인 구조로 표현할 수 있다는 특징이 있다.

대표적으로 컴퓨터의 폴더 구조를 생각할 수 있다.

Root
├── Folder A
│   ├── File A
│   └── File B
└── Folder B
    ├── File C
    └── File D

Root 아래에 Folder가 있고, Folder 아래에 다시 File이 존재하는 것처럼 상위 데이터와 하위 데이터 사이에 부모-자식 관계가 존재하는 구조이다.

따라서 Tree는 다음과 같은 계층 구조를 표현하는 데 적합하다.

파일 시스템
폴더 구조
조직도
게임 오브젝트의 계층 구조
탐색 구조
우선순위 구조

2. Tree의 기본 용어

Tree를 이해하기 위해서는 먼저 기본적인 용어를 이해해야 한다.

다음과 같은 Tree가 있다고 가정한다.

Node

Tree를 구성하는 각각의 데이터를 Node(노드)라고 한다.

위 Tree에서는 다음이 각각 Node이다.

A
B
C
D
E

Root

Tree에서 가장 위에 있는 Node를 Root(루트)라고 한다.

        A
       / \
      B   C

여기에서는 A가 Root이다.

일반적인 Tree에서는 Root가 하나 존재한다.

Parent

어떤 Node의 바로 아래에 Child를 가지고 있는 Node를 Parent(부모)라고 한다.

        A
       / \
      B   C

이 경우 A는 B와 C의 Parent이다.

Child

Parent 바로 아래에 연결된 Node를 Child(자식)라고 한다.

        A
       / \
      B   C

여기에서는 B, C가 A의 Child이다.

Sibling

같은 Parent를 가지고 있는 Node들을 Sibling(형제)이라고 한다.

        A
       / \
      B   C

B와 C는 모두 A를 Parent로 가지고 있으므로 Sibling 관계이다.

Leaf

자식이 없는 Node를 Leaf(리프)라고 한다.

이 Tree에서는:

C
D
E

가 자식을 가지고 있지 않으므로 Leaf이다.

Edge

Node와 Node를 연결하는 선을 Edge(간선)라고 한다.

A
|
B

A와 B 사이의 연결이 하나의 Edge이다.

3. Depth와 Height

Tree에서는 Node가 얼마나 깊은 위치에 있는지를 나타내기 위해 Depth라는 개념을 사용한다.

        A       Depth 0
       / \
      B   C     Depth 1
     /
    D           Depth 2

Root인 A에서 시작한다고 하면:

A = Depth 0
B = Depth 1
C = Depth 1
D = Depth 2

즉, Root에서 해당 Node까지 내려가는 Edge의 개수를 기준으로 Depth를 표현할 수 있다.

반대로 Height는 해당 Node에서 가장 깊은 Leaf까지의 거리를 의미한다.

A에서 C까지 Edge가 2개이므로 A의 Height는 2이다.

다만 Height는 자료구조를 설명하는 방식에 따라 Node 개수를 기준으로 정의하는 경우도 있으므로, 실제 문제를 풀 때는 해당 문제에서 사용하는 정의를 확인할 필요가 있다.

4. Tree의 특징

Tree는 일반적으로 다음과 같은 특징을 가진다.

계층 구조

Tree는 Parent와 Child 관계를 이용해서 데이터를 계층적으로 표현한다.

Parent
  ↓
Child
  ↓
Child

따라서 단순히 데이터를 순서대로 저장하는 것보다 상하 관계가 중요한 데이터를 표현하는 데 적합하다.

순환이 없음

일반적인 Tree에는 Cycle이 존재하지 않는다.

예를 들어:

A → B → C

와 같이 연결되어 있을 때 C에서 다시 A로 돌아가는 연결이 존재한다면 일반적인 Tree 구조라고 보기 어렵다.

A
↓
B
↓
C
↘
 A

이러한 순환 구조는 Graph에서 중요한 개념이다.

5. Binary Tree

Tree에는 여러 종류가 있는데, 이번 학습에서는 특히 Binary Tree(이진 트리)를 중요하게 다루었다.

Binary Tree는 하나의 Node가 가질 수 있는 Child의 개수가 최대 2개인 Tree이다.

각 Node는 최대 두 개의 Child를 가질 수 있다.

여기서 중요한 점은 Binary Tree라는 것만으로 값의 크기 관계가 정해지는 것은 아니라는 것이다.

예를 들어:

        10
       /  \
      50   2

이 구조도 Binary Tree이다.

각 Node가 최대 두 개의 Child를 가지고 있기 때문이다.

하지만 이것은 BST의 규칙에는 맞지 않는다.

따라서 다음을 구분해야 한다.

Binary Tree
→ Child가 최대 2개

BST
→ Binary Tree의 조건
+ 값의 크기 규칙

6. Binary Tree의 형태

Binary Tree에는 여러 형태가 존재한다.

Full Binary Tree

모든 Node가 Child를 정확히 0개 또는 2개 가지는 형태이다.

A와 B는 각각 Child를 2개 가지고 있고, C/D/E는 Child가 없다.

따라서 Full Binary Tree 조건을 만족한다.

Complete Binary Tree

Complete Binary Tree는 위에서부터 Level을 채워나가며, 마지막 Level을 제외하면 모든 Level이 가득 차 있고 마지막 Level도 왼쪽부터 빈틈없이 채워지는 형태이다.

마지막 Level에 D, E, F가 왼쪽부터 채워져 있기 때문에 Complete Binary Tree이다.

이 개념은 이후 학습하는 Heap에서 매우 중요하게 사용된다.

Perfect Binary Tree

모든 Level이 완전히 채워져 있는 Binary Tree를 Perfect Binary Tree라고 한다.

          A
        /   \
       B     C
      / \   / \
     D  E  F   G

모든 Leaf가 같은 Depth에 존재하고 모든 내부 Node가 Child를 2개씩 가지고 있다.

7. Binary Search Tree

다음으로 Binary Search Tree, 즉 BST를 학습하였다.

BST는 Binary Tree의 한 종류이지만 단순히 Child가 최대 2개라는 것에서 끝나지 않고 값의 크기에 대한 규칙을 가진다.

기본적인 BST의 구조는 다음과 같다.

        50
       /  \
     30    70
    / \    / \
   20 40  60 80

여기서 핵심 규칙은:

왼쪽 Subtree < 현재 Node < 오른쪽 Subtree

이다.

따라서 50을 기준으로 보면:

왼쪽
20, 30, 40
→ 50보다 작음

오른쪽
60, 70, 80
→ 50보다 큼

30을 기준으로 보더라도:

20 < 30 < 40

이라는 관계가 성립한다.

8. BST가 검색에 유리한 이유

BST가 중요한 이유는 값의 크기를 이용하여 탐색 범위를 줄일 수 있기 때문이다.

예를 들어 다음 BST에서 60을 찾는다고 가정한다.

        50
       /  \
     30    70
    / \    / \
   20 40  60 80

먼저 Root인 50과 60을 비교한다.

60 > 50

따라서 50보다 작은 값들이 존재하는 왼쪽 Subtree는 탐색할 필요가 없다.

        50
          \
           70

70과 비교한다.

60 < 70

따라서 오른쪽이 아니라 왼쪽으로 이동한다.

        70
       /
      60

60을 찾았다.

즉 BST는 다음과 같은 방식으로 탐색한다.

찾는 값 < 현재 Node
→ 왼쪽으로 이동

찾는 값 > 현재 Node
→ 오른쪽으로 이동

찾는 값 == 현재 Node
→ 탐색 성공

이렇게 값의 크기를 이용해 탐색 범위를 계속 줄일 수 있다는 것이 BST의 핵심이다.

9. BST의 시간 복잡도

BST가 균형 있게 구성되어 있다면 Tree의 높이가 대략 log N 수준이 된다.

따라서 평균적인 경우:

Search
O(log N)

정도의 시간 복잡도를 기대할 수 있다.

하지만 BST가 항상 균형을 유지하는 것은 아니다.

예를 들어 데이터가 다음과 같은 순서로 들어간다고 생각해보았다.

이렇게 한쪽으로만 치우치게 되면 Tree가 사실상 Linked List와 비슷한 형태가 된다.

이 경우 탐색할 때 최대 N개의 Node를 확인해야 할 수 있기 때문에:

Worst Case
O(N)

이 된다.

따라서 일반적인 BST의 탐색 성능은:

Average
O(log N)

Worst
O(N)

으로 정리할 수 있다.

이러한 문제를 해결하기 위해 AVL Tree나 Red-Black Tree처럼 Tree의 균형을 유지하는 자료구조도 존재한다.

10. Tree Traversal

Tree의 데이터를 실제로 사용하려면 Tree 안의 Node들을 순서대로 방문해야 한다.

이것을 Traversal(순회)이라고 한다.

대표적인 Tree Traversal은 다음 네 가지이다.

Preorder
Inorder
Postorder
Level Order

이 네 가지는 단순히 이름을 외우기보다는 Node를 어떤 순서로 방문하는지를 이해하는 것이 중요하다.

11. Preorder Traversal

Preorder는:

Root
→ Left
→ Right

순서로 방문한다.

즉:

현재 Node
→ 왼쪽 Subtree
→ 오른쪽 Subtree

이다.

예를 들어:

Preorder로 순회하면:

A → B → D → E → C

가 된다.

A를 먼저 방문하고, B로 이동한다.

B에서도 B를 먼저 방문한 후 왼쪽 D, 오른쪽 E를 방문한다.

마지막으로 C를 방문한다.

12. Inorder Traversal

Inorder는:

Left
→ Root
→ Right

순서로 방문한다.

즉:

왼쪽 Subtree
→ 현재 Node
→ 오른쪽 Subtree

이다.

같은 Tree를 사용하면:

Inorder 결과는:

D → B → E → A → C

가 된다.

13. BST에서 Inorder가 중요한 이유

이번 Tree 학습에서 가장 중요하게 이해한 부분 중 하나이다.

BST에서 Inorder Traversal을 수행하면 값이 오름차순으로 정렬된 결과를 얻을 수 있다.

다음 BST를 살펴보면:

        50
       /  \
     30    70
    / \    / \
   20 40  60 80

Inorder는:

왼쪽
→ 현재
→ 오른쪽

이므로:

이 된다.

결과가 정확히 오름차순으로 정렬되어 있다.

이것은 우연이 아니다.

BST 자체가:

왼쪽 < 현재 < 오른쪽

이라는 규칙을 가지고 있기 때문이다.

그리고 Inorder가:

왼쪽
→ 현재
→ 오른쪽

순서로 방문하기 때문에 자연스럽게 작은 값부터 큰 값 순으로 방문하게 된다.

따라서 다음 관계를 확실하게 이해해야 한다.

BST
+
Inorder Traversal
↓
오름차순 정렬된 순서

이번 단계에서 단순 암기해야 하는 공식이라기보다 BST의 구조와 Inorder의 방문 순서가 만나서 만들어지는 결과라는 점을 이해하는 것이 중요하다.

14. Postorder Traversal

Postorder는:

Left
→ Right
→ Root

순서로 방문한다.

즉:

왼쪽 Subtree
→ 오른쪽 Subtree
→ 현재 Node

이다.

예를 들어:

Postorder 결과는:

D → E → B → C → A

이다.

특징은 부모 Node를 마지막에 처리한다는 것이다.

따라서 하위 Node들을 먼저 처리한 후 부모 Node를 처리해야 하는 작업에서 활용할 수 있다.

15. Level Order Traversal

Level Order는 DFS 방식과 조금 다르다.

Tree를 깊게 들어가는 것이 아니라 Level 단위로 순회한다.

        A        Level 0
       / \
      B   C      Level 1
     / \
    D   E        Level 2

Level Order 결과는:

A → B → C → D → E

이다.

즉:

Level 0
→ Level 1
→ Level 2
→ ...

순으로 방문한다.

16. Level Order와 Queue

Level Order를 이해할 때 Queue와 연결하면 매우 쉽게 이해할 수 있다.

Queue는 이전에 학습했던 것처럼:

FIFO
First In First Out

구조이다.

다음 Tree가 있다고 하자.

먼저 A를 Queue에 넣는다.

Queue
[A]

A를 꺼내서 처리하고 A의 Child인 B와 C를 Queue에 넣는다.

Queue
[B, C]

B를 꺼낸다.

B의 Child인 D와 E를 Queue 뒤에 넣는다.

Queue
[C, D, E]

C를 꺼낸다.

Queue
[D, E]

이후 D, E 순서로 처리한다.

결과적으로:

A → B → C → D → E

가 된다.

따라서 다음 연결을 기억할 수 있다.

Level Order
↓
BFS
↓
Queue

17. DFS와 Tree Traversal

Preorder, Inorder, Postorder는 모두 DFS(Depth First Search) 방식으로 볼 수 있다.

DFS는:

깊이를 우선하여 탐색하는 방식

이다.

Tree에서는 한쪽 방향으로 깊게 내려간 다음 다시 올라와 다른 경로를 탐색한다.

DFS
├── Preorder
├── Inorder
└── Postorder

반면 Level Order는:

BFS
└── Level Order

로 연결할 수 있다.

18. Tree와 Recursion의 관계

Tree Traversal을 공부하면서 이전에 배운 재귀(Recursion)와도 연결할 수 있었다.

예를 들어 Inorder Traversal은 다음과 같은 형태로 구현할 수 있다.

void Inorder(Node* Node)
{
    if (Node == nullptr)
        return;

    Inorder(Node->Left);
    Visit(Node);
    Inorder(Node->Right);
}

코드의 구조 자체가 Inorder의 정의와 동일하다.

Inorder(Node->Left)
→ Visit(Node)
→ Inorder(Node->Right)

즉 Tree Traversal을 공부하면서:

Tree
+
Recursion
+
DFS

가 자연스럽게 연결된다.

Tree는 자기 자신과 비슷한 작은 Subtree로 계속 나눌 수 있기 때문에 재귀적인 사고방식과 잘 맞는다는 것도 이해할 수 있었다.

19. 네 가지 Traversal 비교

하나의 Tree를 기준으로 정리하면 다음과 같다.

Preorder

Root → Left → Right

1 → 2 → 4 → 5 → 3

Inorder

Left → Root → Right

4 → 2 → 5 → 1 → 3

Postorder

Left → Right → Root

4 → 5 → 2 → 3 → 1

Level Order

Level → Level → Level

1 → 2 → 3 → 4 → 5

따라서 다음 세 가지는 특히 구분해서 기억해야 한다.

Preorder
→ Root Left Right

Inorder
→ Left Root Right

Postorder
→ Left Right Root

그리고 Level Order는 Level을 기준으로 처리한다.

20. Heap

Tree에서 다음으로 학습한 것은 Heap이다.

Heap은 일반적으로 Complete Binary Tree 형태를 기반으로 하며, 추가적인 규칙인 Heap Property를 유지하는 자료구조이다.

대표적으로 두 가지 종류가 있다.

Max Heap
Min Heap

21. Max Heap

Max Heap에서는 부모 Node가 자식 Node보다 크거나 같아야 한다.

예:

각 부모와 자식을 비교하면:

이라는 관계가 성립한다.

따라서 Max Heap에서는 항상 Root에 가장 큰 값이 위치한다.

Max Heap
→ Root = Maximum

22. Min Heap

Min Heap은 반대이다.

부모 Node가 자식 Node보다 작거나 같아야 한다.

Root에는 가장 작은 값이 위치한다.

Min Heap
→ Root = Minimum

23. BST와 Heap의 차이

BST와 Heap은 모두 Tree를 기반으로 하기 때문에 비슷해 보이지만 목적과 규칙이 다르다.

BST

BST의 핵심 규칙:

왼쪽 < 현재 < 오른쪽

따라서 전체적인 값의 위치 관계가 중요하다.

BST는 특정 값을 찾는 검색에 유리하다.

Heap

Heap의 핵심 규칙:

Parent >= Child

또는

Parent <= Child

이다.

Heap에서는 부모와 자식 사이의 관계가 중요하다.

Max Heap에서는 Root가 최대값이고, Min Heap에서는 Root가 최소값이다.

따라서 Heap은 가장 큰 값이나 가장 작은 값을 빠르게 꺼내는 작업에 적합하다.

24. Heap은 왜 Complete Binary Tree를 사용하는가?

Heap은 일반적으로 Complete Binary Tree 형태를 유지한다.

Complete Binary Tree는 구조가 빈틈없이 채워지기 때문에 배열로 표현하기 좋다.

예를 들어:

        A
       / \
      B   C
     / \ /
    D  E F

이 Tree를 배열로 표현하면:

[A, B, C, D, E, F]

처럼 저장할 수 있다.

따라서 Heap은 Node마다 별도의 포인터를 사용해 Tree를 구성하지 않고 배열 기반으로 효율적으로 구현할 수 있다.

25. Heap의 배열 Index

0부터 Index를 사용한다고 할 때 다음 공식이 성립한다.

Parent(i) = (i - 1) / 2

Left Child = 2 * i + 1

Right Child = 2 * i + 2

예를 들어:

          A(0)
        /     \
      B(1)    C(2)
      / \      /
    D(3) E(4) F(5)

B의 Index는 1이다.

B의 왼쪽 Child:

2 * 1 + 1
= 3

실제로 D의 Index가 3이다.

B의 오른쪽 Child:

2 * 1 + 2
= 4

실제로 E의 Index가 4이다.

이러한 공식이 성립하는 이유는 Complete Binary Tree의 구조가 빈틈없이 채워져 있기 때문이다.

26. Heap의 Insert

Heap에 데이터를 추가할 때는 단순히 아무 위치에 넣는 것이 아니다.

Complete Binary Tree 구조를 유지하기 위해 가장 마지막 위치에 새로운 값을 추가한다.

그 후 Heap의 규칙을 만족할 때까지 부모와 비교하며 위로 이동시킨다.

이 과정을:

Heapify Up
또는
Bubble Up

이라고 한다.

27. Heapify Up

Max Heap에 새로운 값을 추가한다고 생각해보자.

기존 Heap:

        100
       /   \
      50    80

여기에 120을 추가한다.

Complete Binary Tree 구조를 유지하기 위해 마지막 위치에 넣는다.

120은 부모인 50보다 크다.

따라서 둘을 교환한다.

그런데 120은 다시 부모인 100보다 크다.

다시 교환한다.

이제 Max Heap 조건을 만족한다.

이처럼 새로운 Node를 위쪽으로 올려가면서 Heap 조건을 만족시키는 것이 Heapify Up이다.

28. Heap의 Remove

Max Heap에서 가장 중요한 데이터는 Root에 있는 최대값이다.

        120
       /   \
     100    80

Root인 120을 제거하면 빈 공간이 생긴다.

이때 일반적으로 마지막 Node를 Root 위치로 가져온 후 Heap 조건을 다시 맞춘다.

그 과정에서 자식 Node와 비교하면서 아래쪽으로 이동시킨다.

이것을:

Heapify Down

이라고 한다.

29. Heap의 시간 복잡도

Heap은 Complete Binary Tree이므로 높이가 O(log N) 수준이다.

따라서 대표적인 연산의 시간 복잡도는:

Insert
O(log N)

Remove
O(log N)

Peek
O(1)

이다.

Peek가 O(1)인 이유는 최댓값 또는 최솟값이 항상 Root에 있기 때문이다.

Root만 확인하면 되므로 다른 Node들을 탐색할 필요가 없다.

30. Priority Queue

마지막으로 Priority Queue(우선순위 큐)를 학습하였다.

일반적인 Queue는:

FIFO
First In First Out

방식으로 동작한다.

즉 먼저 들어온 데이터가 먼저 나간다.

하지만 Priority Queue는 이름에 Queue가 들어가더라도 단순한 FIFO 구조가 아니다.

우선순위가 높은 데이터가 먼저 처리되는 자료구조이다.

예를 들어:

A → 우선순위 1
B → 우선순위 10
C → 우선순위 5

라고 한다면 일반 Queue에서는 들어온 순서대로:

A → B → C

가 될 수 있다.

하지만 Priority Queue에서는 우선순위가 높은 순서대로:

B → C → A

처럼 처리할 수 있다.

31. Priority Queue와 Heap의 관계

Priority Queue를 구현하는 대표적인 방법이 Heap이다.

Heap은 최댓값 또는 최솟값을 Root에 유지할 수 있기 때문에 Priority Queue의 동작과 잘 맞는다.

예를 들어 Max Heap에서는:

        100
       /   \
      50    80

항상 가장 큰 값인 100이 Root에 존재한다.

따라서 Priority Queue에서 가장 높은 우선순위의 데이터를 가져올 때 Root만 확인하면 된다.

즉:

Heap
↓
최댓값 / 최솟값을 Root에 유지
↓
Priority Queue 구현에 활용

이라는 관계가 성립한다.

32. C++의 std::priority_queue

C++에서는 Priority Queue를 직접 Heap으로 구현하지 않고 다음 자료구조를 사용할 수 있다.

std::priority_queue

기본적으로 std::priority_queue는 Max Heap 방식으로 동작한다.

std::priority_queue<int> PQ;

PQ.push(30);
PQ.push(10);
PQ.push(50);
PQ.push(20);

데이터가 다음과 같이 들어가더라도:

top()을 확인하면 가장 큰 값인:

이 나온다.

그 후 pop()을 하면 50이 제거되고 다음으로 큰 값이 Top에 위치한다.

33. std::priority_queue의 주요 함수

push()

데이터를 추가한다.

PQ.push(50);

Heap의 구조와 우선순위를 유지하면서 데이터를 추가한다.

top()

현재 가장 우선순위가 높은 데이터를 확인한다.

PQ.top();

중요한 점은 top()은 데이터를 제거하지 않는다는 것이다.

단순히 현재 가장 높은 우선순위의 값을 확인한다.

pop()

현재 Top에 있는 데이터를 제거한다.

PQ.pop();

단, pop() 자체가 제거되는 값을 반환하지는 않는다.

따라서 값을 사용하면서 제거하려면:

int Value = PQ.top();
PQ.pop();

과 같은 방식으로 사용할 수 있다.

empty()

Priority Queue가 비어 있는지 확인한다.

PQ.empty();

size()

현재 들어 있는 데이터의 개수를 확인한다.

PQ.size();

34. Min Heap으로 사용하기

std::priority_queue는 기본적으로 Max Heap이다.

std::priority_queue<int> PQ;

이 경우:

큰 값
↓
작은 값

순으로 꺼낼 수 있다.

반대로 작은 값을 먼저 꺼내는 Min Heap 형태로 사용하고 싶다면 비교 기준을 변경할 수 있다.

std::priority_queue<int, std::vector<int>, std::greater<int>> PQ;

이 경우:

작은 값
↓
큰 값

순으로 처리된다.

35. 이번 학습에서 다른 자료구조와 연결한 내용

이번 Tree 학습은 지금까지 공부했던 자료구조들과도 많이 연결되었다.

Tree + Recursion

Tree Traversal은 재귀적인 구조로 구현하기 좋다.

Tree
↓
Subtree
↓
Subtree
↓
...

따라서 이전에 공부했던 Recursion과 연결된다.

Level Order + Queue

Level Order는 같은 Level을 순서대로 처리하기 때문에 Queue의 FIFO 특성을 활용할 수 있다.

Level Order
↓
BFS
↓
Queue

라는 관계로 연결된다.

Heap + Priority Queue

Heap은 최대값 또는 최소값을 빠르게 확인할 수 있기 때문에 Priority Queue를 구현하는 데 활용된다.

Heap
↓
최댓값 / 최솟값 관리
↓
Priority Queue

BST + Inorder

BST의 값의 크기 규칙과 Inorder의 순회 순서가 결합되면 정렬된 결과를 얻을 수 있다.

BST
↓
Left < Root < Right
↓
Inorder
↓
오름차순

이 관계가 이번 학습에서 특히 중요했다.

36. BST와 Heap 비교

BST와 Heap은 모두 Tree를 기반으로 하지만 목적이 다르다.

구분BSTHeap

기본 구조	Binary Tree	Complete Binary Tree
핵심 규칙	Left < Root < Right	Parent와 Child의 크기 관계
Root의 의미	특정 값이 보장되지 않음	Max 또는 Min
주요 목적	검색	우선순위 처리
검색	유리	일반적인 검색에는 불리
최댓값/최솟값	구조에 따라 탐색	Root에서 확인
Inorder	BST라면 오름차순	정렬을 보장하지 않음
대표 활용	탐색 구조	Priority Queue

따라서:

BST
→ 값을 찾는 데 유리

Heap
→ 가장 큰 값 또는 가장 작은 값을 빠르게 꺼내는 데 유리

라고 구분할 수 있다.

37. 시간 복잡도 정리

이번 단계에서 학습한 대표적인 시간 복잡도를 정리하면 다음과 같다.

BST

균형이 잡힌 경우:

Search → O(log N)
Insert → O(log N)
Delete → O(log N)

최악의 경우:

Search → O(N)
Insert → O(N)
Delete → O(N)

이다.

Heap

Peek   → O(1)
Insert → O(log N)
Remove → O(log N)

이다.

Heap의 높이가 O(log N)이기 때문에 Insert와 Remove에서 위아래로 이동하는 비용도 O(log N)이 된다.

38. 이번 단계에서 배운 내용을 전체적으로 연결

이번 학습을 통해 Tree라는 하나의 자료구조에서 여러 가지 형태와 활용 방법이 파생되는 것을 확인할 수 있었다.

Tree
│
├── Binary Tree
│   │
│   └── BST
│       │
│       └── Inorder
│           ↓
│        오름차순
│
└── Heap
    │
    ├── Max Heap
    │
    └── Min Heap
         ↓
    Priority Queue

Traversal은 별도로:

Tree Traversal
│
├── Preorder
│   └── Root → Left → Right
│
├── Inorder
│   └── Left → Root → Right
│
├── Postorder
│   └── Left → Right → Root
│
└── Level Order
    └── Level 순서
        ↓
       BFS
        ↓
      Queue

로 연결된다.

39. 이번 단계에서 가장 중요했던 내용

이번 학습에서 단순히 Tree의 종류를 외우는 것보다 다음의 관계를 이해하는 것이 중요했다.

① Tree

계층적인 데이터 구조

② Binary Tree

하나의 Node가 가질 수 있는 Child
→ 최대 2개

③ BST

Left < Root < Right

값의 크기를 이용해서 탐색 범위를 줄일 수 있다.

④ BST + Inorder

BST
+
Inorder
↓
오름차순 정렬

BST의 구조적 특징과 Inorder의 방문 순서가 결합해서 발생하는 결과이다.

⑤ Level Order

Level Order
↓
BFS
↓
Queue

Queue의 FIFO 특성을 이용해서 같은 Level부터 순서대로 처리할 수 있다.

⑥ Heap

Complete Binary Tree
+
Heap Property

Max Heap에서는:

가장 큰 값 → Root

Min Heap에서는:

가장 작은 값 → Root

가 된다.

⑦ Heap + Priority Queue

Heap
↓
최댓값 / 최솟값을 빠르게 확인
↓
Priority Queue 구현

C++에서는:

std::priority_queue

를 이용할 수 있다.

40. 최종 정리

이번 9단계에서는 Tree 자료구조의 기본 개념부터 Binary Tree, BST, Tree Traversal, Heap, Priority Queue까지 학습하였다.

Tree는 배열이나 연결 리스트처럼 데이터를 단순히 일렬로 저장하는 것이 아니라 Parent와 Child 관계를 통해 계층적으로 데이터를 표현하는 자료구조이다.

Binary Tree는 하나의 Node가 최대 2개의 Child를 가질 수 있는 Tree이고, BST는 여기에:

Left < Root < Right

라는 값의 크기 규칙이 추가된 구조이다.

BST는 값의 크기를 비교하면서 왼쪽 또는 오른쪽 Subtree만 선택하여 탐색할 수 있기 때문에 균형이 잘 잡혀 있다면 O(log N)의 탐색 성능을 기대할 수 있다. 하지만 한쪽으로 치우친다면 최악의 경우 O(N)까지 성능이 떨어질 수 있다.

Tree Traversal에는:

Preorder
Inorder
Postorder
Level Order

가 있으며, Preorder/Inorder/Postorder는 DFS 방식으로 생각할 수 있고 Level Order는 BFS 방식으로 생각할 수 있다.

특히 BST에서 Inorder Traversal을 수행하면 오름차순으로 정렬된 결과가 나온다는 관계가 매우 중요하다.

BST
→ Left < Root < Right

Inorder
→ Left → Root → Right

따라서
→ 작은 값부터 큰 값 순서

Level Order는 Queue의 FIFO 특성을 활용하여 구현할 수 있기 때문에:

Level Order
→ BFS
→ Queue

라는 관계로 이해할 수 있었다.

Heap은 Complete Binary Tree를 기반으로 하며, Max Heap에서는 부모가 자식보다 크거나 같고 Min Heap에서는 부모가 자식보다 작거나 같다. 이를 통해 Max Heap은 최댓값을, Min Heap은 최솟값을 Root에서 O(1)에 확인할 수 있다.

그리고 Heap은 Priority Queue를 구현하는 대표적인 방법으로 사용된다. C++에서는 std::priority_queue를 통해 이러한 우선순위 기반 처리를 쉽게 사용할 수 있다.

결국 이번 단계에서 배운 내용을 하나의 흐름으로 정리하면 다음과 같다.

Tree
│
├── Binary Tree
│   │
│   └── BST
│       │
│       └── Inorder
│           ↓
│        오름차순
│
├── Traversal
│   ├── Preorder
│   ├── Inorder
│   ├── Postorder
│   └── Level Order
│                ↓
│               BFS
│                ↓
│              Queue
│
└── Heap
    ├── Max Heap
    └── Min Heap
          ↓
    Priority Queue
          ↓
std::priority_queue

이번 학습을 통해 Tree는 단순히 하나의 자료구조가 아니라 탐색을 위한 BST와 우선순위 처리를 위한 Heap 등 여러 목적의 자료구조로 확장되는 기본 구조라는 것을 이해하였다.

'자료구조와 알고리즘' 카테고리의 다른 글

힙(Heap) / 우선순위 큐(Priority Queue) (0)	2026.09.04
해시 (0)	2026.08.31
정렬 알고리즘 (0)	2026.08.28
탐색 알고리즘 (0)	2026.08.27
재귀 (0)	2026.08.26

현재글트리(Tree)

begin-play 님의 블로그

begin-play 님의 블로그 입니다.

Today :
Yesterday :

« 2026/10 »
일	월	화	수	목	금	토
				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

트리(Tree)

트리(Tree)

1. Tree란?

2. Tree의 기본 용어

Node

Root

Parent

Child

Sibling

Leaf

Edge

3. Depth와 Height

4. Tree의 특징

계층 구조

순환이 없음

5. Binary Tree

6. Binary Tree의 형태

Full Binary Tree

Complete Binary Tree

Perfect Binary Tree

7. Binary Search Tree

8. BST가 검색에 유리한 이유

9. BST의 시간 복잡도

10. Tree Traversal

11. Preorder Traversal

12. Inorder Traversal

13. BST에서 Inorder가 중요한 이유

14. Postorder Traversal

15. Level Order Traversal

16. Level Order와 Queue

17. DFS와 Tree Traversal

18. Tree와 Recursion의 관계

19. 네 가지 Traversal 비교

Preorder

Inorder

Postorder

Level Order

20. Heap

21. Max Heap

22. Min Heap

23. BST와 Heap의 차이

BST

Heap

24. Heap은 왜 Complete Binary Tree를 사용하는가?

25. Heap의 배열 Index

26. Heap의 Insert

27. Heapify Up

28. Heap의 Remove

29. Heap의 시간 복잡도

30. Priority Queue

31. Priority Queue와 Heap의 관계

32. C++의 std::priority_queue

33. std::priority_queue의 주요 함수

push()

top()

pop()

empty()

size()

34. Min Heap으로 사용하기

35. 이번 학습에서 다른 자료구조와 연결한 내용

Tree + Recursion

Level Order + Queue

Heap + Priority Queue

BST + Inorder

36. BST와 Heap 비교

37. 시간 복잡도 정리

BST

Heap

38. 이번 단계에서 배운 내용을 전체적으로 연결

39. 이번 단계에서 가장 중요했던 내용

① Tree

② Binary Tree

③ BST

④ BST + Inorder

⑤ Level Order

⑥ Heap

⑦ Heap + Priority Queue

40. 최종 정리

'자료구조와 알고리즘' 카테고리의 다른 글

'자료구조와 알고리즘'의 다른글