3 min to read
자료구조(9) - 이진 트리
이진 트리의 성질과 종류 설명
🔚 짧게 하는 복습
✅ 1. 트리의 정의를 안다.
✅ 2. 트리의 용어들을 안다.
✅ 3. k-ary tree, 그 중 이진 트리에 대해서 정확하게 안다.
혹시 기억이 안 난다면, 다시 돌아가자
이번 시간은 저번 시간에 배웠던 이진 트리에 대해 더 깊게 다루어 보겠다.
이진 트리란 저번 시간에 했듯이, 모든 서브 트리가 자식 노드를 최대 2개까지만 가지는 트리이다.
이러한 특징 때문에, 많은 수학적 성질을 가진다.
이진 트리의 성질
1. 이진 트리에서 level i에서는 최대 2i만큼의 노드를 가진다.
pf) 수학적 귀납법을 통해 알 수 있다. (수학적 귀납법을 모른다면, 읽어볼 거리 참고)
level 0 -> 최대 node 1개
level 1 -> 최대 node 2개
level 2 -> 최대 node 4개
level 3 -> 최대 node 8개
…
level i -> 최대 node 2i
2. level i의 이진 트리는 최대 2i+1-1만큼의 노드를 가진다.
pf) 등비수열의 합을 이용한다. (등비수열의 합을 모른다면, 읽어볼 거리 참고)
20 + 21 … + 2i = 1 x (2i+1-1)/ (2-1) = 1
3. i개의 노드를 가진 이진 트리는 최대 높이, i-1을 가진다.
pf) 일직선으로 연결하면, 트리의 높이는 i-1을 가진다. 예를 들어, 아래와 같이 만들면 된다.
이렇게 모든 노드가 한 방향으로만 뻗어 나가는 특별한 형태의 이진 트리를 skewed-tree라고 한다.
4. i개의 노드를 가진 이진 트리는 최소 높이, log2(i+1)을 가진다.
pf) 루트 노드부터 왼쪽 위에서부터 오른쪽 아래로 순서대로 채우면, 항상 높이가 log2(i+1)를 가진다.
5. i개의 노드를 가진 이진 트리의 종류는 2xi C i/(n+1)개이다.
pf) 설명 생략, 참고로 저 조합식은 카탈란 수라는 수로, 조합론 문제에 자주 나온다.(읽어볼 거리 참고)
이제 이진 트리의 다양한 종류에 대해 알아보자.
크게 완전 이진 트리(CBT), 포화 이진 트리(FBT), 이진 검색 트리(BST)를 알아본다.
완전 이진 트리란?
마지막 level을 제외한 모든 level의 노드가 2개의 자식을 가졌으며, 마지막 level에서 노드가 왼쪽에서 오른쪽으로 순서대로 채워진 이진 트리를 완전 이진 트리(Complete Binary Tree)라고 한다.
아래 그림을 다시 한번 보자.
이러한 성질 때문에, 완전 이진 트리를 만들려면 왼쪽 위부터 아래쪽 하단까지 순서대로 노드를 삽입하면 된다.
또한, 이렇게 삽입 순서가 정해져 있다는 성질을 이용하면, 배열로 표현할 수 있다.
인덱싱으로 표현하면 A(0) B(1) C(2) D(3) E(4) F(5) G(6) H(7) I(8) J(9) K(10) L(11)이다.
여기서 잘 보면, i번째 노드의 2i+1은 왼쪽 자식 노드, 2i+2는 오른쪽 자식 노드임을 알 수 있다.
포화 이진 트리란?
리프 노드를 제외한 모든 노드가 2개의 자식을 가진 트리를 포화 이진 트리(Full Binary Tree)라고 한다.
모든 노드는 0개 또는 2개의 자식 노드를 가진다는 성질이 있다.
예제로 확인해보자.
아래에 나오는 트리들이 완전 이진 트리, 포화 이진 트리인지 알아보자.
위 트리는 맨 마지막 노드가 왼쪽에서 오른쪽으로 순서대로 차있지도 않고, 다 차있지도 않기에 완전 이진 트리도, 포화 이진 트리도 아니다..
위 트리는 왼쪽에서 오른쪽으로 순서대로 차 있지는 않지만, 리프 노드를 제외하고 자식 노드를 2개씩 가진다.
즉, 완전 이진 트리는 아니지만, 포화 이진 트리이다.
이진 검색 트리란?
이진 검색 트리(Binary Search Tree)는 각 노드의 값이 해당 노드의 왼쪽 서브 트리에 속한 모든 값보다 작고, 오른쪽 서브 트리에 속한 모든 값보다 큰 특성을 가진 이진 트리이다.
즉, 트리 전체를 위에서 아래로 정사영 했을 때, 아래에 나오는 배열이 오름차순으로 배열된 모습으로 나온다.
(b) 트리의 정사영 : 2 4 6 12 14 16 18
(c) 트리의 정사영 : 5 10 15 20 25
이러한 특성 덕분에 이진 검색 트리에서는 값을 효과적으로 검색할 수 있다.
또한, 최솟값과 최댓값을 찾는 것도 간단하게 가능하다.
왼쪽으로 이동하면서 나타나는 첫 번째 Null이 최솟값이 되고, 오른쪽으로 이동하면서 나타나는 첫 번째 Null이 최댓값이 된다.
오늘은 여러 가지 이진 트리의 수학적 성질과 종류에 대해서만 잠깐 알아보았다.
다음 시간에는 위 이진 트리 중 완전 이진 트리와 이진 검색 트리의 본격적인 구현에 대해 다루어 보겠다.
📖 오늘의 핵심(다 알기 전까지는 넘어가지 말자❗)
✅ 1. 이진 트리의 정의와 성질을 안다.
✅ 2. 완전 이진 트리의 정의와 성질을 안다.
✅ 3. 포화 이진 트리의 정의와 성질을 안다.
✅ 4. 이진 검색 트리의 정의와 성질을 안다.
⚠️ 앞으로는 완전 이진 트리, 포화 이진 트리, 이진 검색 트리를 각각 CBT, FBT, BST로 줄여서 이야기할 것이다.
💣 과제, 없음.
🔜 더 공부해보기,
Comments