[딩코딩코 2025 코딩테스트 필수 알고리즘] - 15.트리

본 글은 딩코딩코 님의 『38군데 합격 비법, 2025 코딩테스트 필수 알고리즘』
강의를 듣고 정리한 내용입니다.
강의와 수업 자료에 수록된 일부 코드와 이미지를 참고하여 발췌·활용하였습니다.
코딩테스트 준비를 체계적으로 하고 싶으시다면, 아래 링크에서 강의를 확인해 보세요
👉 『38군데 합격 비법, 2025 코딩테스트 필수 알고리즘』 보러 가기
본 게시물은 파트너스 활동의 일환으로 작성되었으며, 구매 시 소정의 수수료를 받을 수 있습니다.

---

트리

트리란?

트리란 뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조 이다.
비선형 구조는 선형구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어 있다.

선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고,
비선형구조는 표현에 초점이 맞춰져 있다.

트리 용어

1. Node : 트리에서 데이터를 저장하는 기본 요소
2. Root Node : 트리 맨 위에 있는 노드
3. Level : 최상위 노드를 0 으로 했을 때, 하위로 연결된 노드의 깊이를 나타냄
4. Parent Node : 어떤 노드의 사위 레벨에 연결된 노드
5. Child Node : 어떤 노드의 하위 레벨에 연결된 노드
6. Leaf Node(Terminal Node) : Child Node 가 하나도 없는 노드
7. Sibling : 동일한 Parent Node 를 가진 노드
8. Depth : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수

---

트리의 종류

트리는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등 다양한 트리가 있다.

이진 트리(Binary Tree)

이진 트리의 특징은 각 노드가 최대 두 개의 자식을 가진다 라는 것이다.
하위 노드가 4~5개가 아니라, 무조건 0,1,2 개 만 있어야 한다.

      o      Level 0 
    o o o    Level 1
   o  o  o   Level 2 # 이진 트리(X)

      o      Level 0 
    o   o    Level 1
   o o o     Level 2 # 이진 트리(O)

완전 이진 트리(Complete Binary Tree)

완전 이진 트리의 특징은 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 하는 것이다.

      o      Level 0
    o   o    Level 1
     o o     Level 2  # -> 이진 트리 O 완전 이진 트리 X

      o      Level 0
    o   o    Level 1
   o o o     Level 2  # -> 이진 트리 O 완전 이진 트리 O

완전 이진 트리를 배열로 표현

완전 이진 트리는 왼쪽부터 데이터가 쌓이게 되는데, 이를 순서대로 배열에 쌓으면서 표현할 수 있다.

      8      Level 0
    6   3    Level 1
   4 2 5     Level 2  # -> 이진 트리 O 완전 이진 트리 O

위와 같은 완전 이진 트리를 배열에 표현한다면, 다음과 같다.

1. 트리를 구현할 때는 편의성을 위해 0번째 인덱스는 사용되지 않는다.
   • 0번째 인덱스에는 None 값을 넣고 시작한다.
   • [None]
2. Level 0 -> [None, 8] 첫번째 레벨의 8을 넣고,
3. Level 1 -> [None, 8, 6, 3] 다음 레벨인 6, 3을 넣고
4. Level 2 -> [None, 8, 6, 3, 4, 2, 5] 다음 레벨인 4, 2, 5를 넣으면 된다.

그러면, [None, 8, 6, 3, 4, 2, 5] 배열이 되는데, 역으로 이 배열을 활용해서 트리 구조를 분석해보자.

1. 현재 인덱스 * 2 → 왼쪽 자식의 인덱스
2. 현재 인덱스 * 2 + 1 -> 오른쪽 자식의 인덱스 1 * 2 + 1 =3
3. 현재 인덱스 // 2 -> 부모의 인덱스

예를 들어 1번째 인덱스인 8의 왼쪽 자식은 6, 오른쪽 자식은 3이다.
그러면 12 = 2 번째 인덱스 = 6 , 12+1 = 3 번째 인덱스 = 3 이다.
부모를 찾아보면 3//2 = 1번째 인덱스 = 8 이므로 부모를 찾을 수 있다.

완전 이진 트리의 높이

트리의 높이는 루트 노트부터 가장 아래 리프 노드까지의 길이이다.

각 레벨에 노드가 꽉 차 있으면 몇 개가 있는지 생각해보자.
레벨을 k 라고 한다면, 각 레벨에 최대로 들어갈 수 있는 노드의 개수는 2^k 개임을 알 수 있다.

      1            Level 0 -> 1개
    2   3          Level 1 -> 2개 
   4 5 6 7         Level 2 -> 4개
 8 9....... 14 15  Level 3 -> 8개 
                   Level k -> 2^k 개

그럼 높이가 h 인데 모든 노드가 꽉 차 있는 완전 이진 트리라면 모든 노드의 개수는 몇 개일까?

1 + 2^1 + 2^2 + 2^3 + 2^4 ..... 2^h

즉, 이를 수식으로 표현하면 2^(h+1) - 1 이 된다.

등비수열의 합 공식

조건
-첫 항: a
-공비: r
-항의 개수: n (예: h + 1)

공식
S = a * r^n - 1 / r - 1

즉, 높이가 h 일 대 최대 노드의 개수는 2^(h+1) - 1 이 된다.

그러면 이 때 최대 노드의 개수가 N 이라면, h 는 뭘까?

2^(h+1) - 1 = N
h = log_2(N+1)-1

완전 이진 트리 노드의 개수가 N 일 때 최대 높이가 log_2(N+1)-1 이므로
이진 트리의 높이는 최대로 해봤자 O(log(N))이다.