🌳 트리(Tree)
트리는 ‘나무 거꾸로 세운 모양’처럼 보이는 계층형 비선형 자료 구조.
맨 위에 root(루트, 뿌리)가 있고, 그 아래로 자식 노드(children)**들이 뻗어나가는 구조.
2. 비교
앞서 보인 큐(Queue), 스택(Stack) 은 자료구조에서 선형 구조라고 합니다.
선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미.
트리는 바로 비선형 구조입니다!
비선형 구조는 선형구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어있다.
선형구조와 비선형구조의 차이점은 형태뿐만 아니라 용도에서도 차이점이 많다!
선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고,
비선형구조는 표현에 초점이 맞춰져 있다.
A(루트)
/ \
B C
/ \
D E
- B, C는 A의 자식(child)
- D, E는 B의 자식
- A는 B의 부모(parent)
🌿 트리에서 나오는 용어
Node: 트리에서 데이터를 저장하는 기본 요소
Root Node: 트리 맨 위에 있는 노드
Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
Child Node: 어떤 노드의 하위 레벨에 연결된 노드
Leaf Node(Terminal Node): Child Node가 하나도 없는 노드
Sibling: 동일한 Parent Node를 가진 노드
Depth: 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
🌿 트리의 특징
- 계층적 구조 (회사 조직도, 폴더 구조 같은 느낌)
- 루트(root)는 하나만 있어요.
- 사이클(순환)이 없어요. → “부모 → 자식 → 다시 부모” 이런 순환은 안 돼요.
- 노드(node): 데이터 하나하나
- 간선(edge): 노드 사이 연결선
🌳 트리의 종류
- 이진 트리 (Binary Tree)
→ 한 노드가 가질 수 있는 자식이 최대 2개 (왼쪽, 오른쪽)
→ 막 하위의 노드가 4~5개 일 수 없습니다. 무조건 0, 1, 2 개만 있어야 합니다!
→ 완전 이진 트리(Complete Binary Tree)의 특징은 바로
노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다는 것 입니다!
예:
10
/ \
5 20
- 이진 탐색 트리 (Binary Search Tree, BST)
→ 왼쪽 자식 < 부모 < 오른쪽 자식
예
10
/ \
5 15
→ 이렇게 하면 탐색(search) 속도가 매우 빠름
🌿 완전 이진 트리를 배열로 표현
- 완전 이진 트리(Complete Binary Tree)의 특징은 바로
노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다는 것! - 트리 구조를 표현하는 방법은
직접 클래스를 구현해서 사용하는 방법이 있고,
배열로 표현하는 방법이 있습니다.
⁉️ 트리 구조를 어떻게 배열에 저장할 수 있을까요?
→ 바로 완전 이진 트리를 쓰는 경우에 사용할 수 있다!
→ 완전 이진 트리는 왼쪽부터 데이터가 쌓이게 되는데,
이를 순서대로 배열에 쌓으면서 표현할 수 있습니다.
→ 예를 들어 아래와 같은 완전 이진 트리를 배열에 표현한다면, 다음과 같습니다!
8 Level 0
6 3 Level 1
4 2 5 Level 2 # -> 이진 트리 O 완전 이진 트리 O
트리를 구현할 때는 편의성을 위해 0번째 인덱스는 사용되지 않는다!
그래서 None 값을 배열에 넣고 시작합니다! [None]
8 Level 0 -> [None, 8] 첫번째 레벨의 8을 넣고,
6 3 Level 1 -> [None, 8, 6, 3] 다음 레벨인 6, 3을 넣고
4 2 5 Level 2 -> [None, 8, 6, 3, 4, 2, 5] 다음 레벨인 4, 2, 5를 넣으면 됩니다!
그러면, [None, 8, 6, 3, 4, 2, 5] 라는 배열이 되는데
0 1 2 3 4 5 6
[None, 8, 6, 3, 4, 2, 5]
level 0 / 1 / 2
0 / 1 /2 3 /4 5 6
[None, 8, 6, 3, 4, 2, 5]
1. 현재 인덱스 * 2 -> 왼쪽 자식의 인덱스
2. 현재 인덱스 * 2 + 1 -> 오른쪽 자식의 인덱스 1 * 2 + 1 =3
3. 현재 인덱스 // 2 -> 부모의 인덱스
예를 들어서 1번째 인덱스인 8의 왼쪽 자식은 6, 오른쪽 자식은 3 입니다.
그러면 1 * 2 = 2번째 인덱스! 6!
그러면 1 * 2 + 1 = 3번째 인덱스! 3! 입니다!
부모를 찾아보면, 3 // 2 = 1번째 인덱스 8 이므로 부모를 찾을 수 있습니다.
이를 다시 생각해보면
[None, 8, 6, 3, 4, 2, 5] 는
8 밑에 6, 3 이 있고, 6, 3 밑에 4, 2, 5가 있는 완전 이진 트리구나! 생각할 수 있습니다.
📌 장점
- 완전이진트리 -> 배열로 쉽게 트리구조를 나타낼 수 있어 배열을 통해 트리에 있는 노드간의 관계를 쉽게 찾아갈 수 있다.🌿 완전 이진 트리의 높이
트리의 높이(Height)는, 루트 노드부터 가장 아래 리프 노드까지의 길이 입니다!
예를 들어 다음과 같은 트리의 높이는 2라고 할 수 있습니다.
o Level 0 # 루트 노드
o o Level 1
o o o Level 2 # 가장 아래 리프 노드
이 트리의 높이는 ? 2 - 0 = 2!
예시를 보면, 레벨을 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 이 됩니다!
입력값의 개수를 N이라고 가정했을 때, 시간복잡도가 얼마나 걸리냐?
2^(h+1) -1 =N
h = log_2(N+1)-1
h = 8 이라고 했을 때, N = 2^(9)-1 = 511
N = 511 이라고 했을 때, 완전 이진트리로 노드들을 쌓아놓는다면, h는 몇이야?
h = log_2(N+1)-1 => h = log_2(511+1)-1 => 8
