이전 포스팅
알고리즘 분석 | 이진 탐색트리 BST | inorder successor
이진 탐색 트리(BST) BST는 트리 구조를 사용하여 데이터를 저장하고 검색합니다. 각 노드는 하나의 키를 갖고 있으며, 루트 노드부터 시작하여 왼쪽 서브트리는 작은 값의 키를 갖는 노드로, 오른
jelong.tistory.com
이진트리의 개념과 종류
이진트리(Binary Tree)란, 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조를 말합니다. 이진트리에서는 각 노드는 하나의 값과, 왼쪽 자식 노드와 오른쪽 자식 노드를 가리키는 포인터를 가지며, 이러한 포인터를 이용해 트리를 탐색할 수 있습니다.
이진트리는 각 노드가 최대 두 개의 자식 노드를 가지는 이유 때문에, 트리의 높이가 낮아지게 됩니다. 즉, 트리의 높이는 log2(n) 이하가 되며, 이러한 특성 때문에 이진트리는 효율적인 탐색 및 정렬에 매우 유용합니다.
이진트리는 다양한 응용 분야에서 활용되며, 컴퓨터 과학에서는 이진트리를 기반으로 많은 자료구조와 알고리즘이 구현됩니다. 예를 들어, 이진검색트리(Binary Search Tree)는 이진트리를 이용하여 데이터를 정렬하고 탐색하는 자료구조이며, 힙(Heap)은 이진트리를 이용하여 우선순위 큐를 구현하는 자료구조입니다
풀 이진 트리 (Full Binary Tree)
Full binary tree는 모든 레벨에서 노드가 가득 찬 이진트리입니다. 즉, 모든 노드가 0개 혹은 2개의 자식 노드를 가지며, 모든 리프 노드의 레벨이 같은 이진트리입니다.
예를 들어, 다음과 같은 트리는 Full binary tree입니다
A level - 0
/ \
B C level - 1
/ \
D E level - 2모든 레벨에서 노드가 가득 차 있고, 모든 리프 노드의 레벨이 같기 때문에 이 트리는 full binary tree입니다.
반면에, 다음과 같은 예시는 Full binary tree가 아닙니다.
1
/ \
2 3
/ \ /
4 5 63의 왼쪽 자식인 6이 없으므로 모든 레벨에서 노드가 가득 차있지 않고, 모든 리프 노드의 레벨이 같지 않기 때문에 이 트리는 full binary tree가 아닙니다.
완전 이진트리(Complete binary Tree)
완전 이진트리(Complete Binary Tree)란 모든 레벨에서 노드가 가득 차 있고, 마지막 레벨에서는 노드가 왼쪽부터 채워지는 이진트리를 말합니다. 아래는 7개의 노드를 가지는 완전 이진트리의 예시입니다.
A
/ \
B C
/ \ /
D E F
반면에, 다음과 같은 예시는 Complete binary tree가 아닙니다.
1
/ \
2 3
/ \ \
4 5 7
대체로 완전한 이진트리(Almost or Near complete binary tree)
거의 완전한 이진트리(Nearly Complete Binary Tree)란 마지막 레벨을 제외한 모든 레벨에서 노드가 가득 차 있고, 마지막 레벨에서는 노드가 왼쪽부터 채워지는 이진트리를 말합니다.
A
/ \
B C
/ \ / \
D E F G
/ \
H I반면에, 다음과 같은 예시는 Near complete binary tree가 아닙니다
A
/ \
B C
/ \ \
D E G
/ \
H I마지막 레벨을 제외한 모든 레벨의 노드가 가득 차 있어야하지만, 노드 C의 왼쪽 자식 노드가 비어있으므로, 다음과 같은 예시는 Near complete binary tree 가 아닙니다.
