[자료구조] 이진트리 (Binary tree) 알아보기
이진트리(Binary tree)란 모든 노드들이 둘 이하의 자식을 가진 트리입니다.
이진트리 유형
전 이진트리 (Full Binary Tree or Strict Binary Tree)
전 이진 트리는 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리입니다.
완전 이진 트리 (Complete Binary Tree)
완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리입니다.
마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 합니다.
포화 이진 트리 (Perfect Binary Tree)
포화 이진 트리는 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 잎 노드가 동일한 깊이 또는 레벨을 갖습니다.
균형 이진 트리 (Balanced Binary Tree)
균형 이진 트리는 왼쪽과 오른쪽 트리의 높이 차이가 모두 1만큼 나는 트리입니다. 예를 들어 AVL 및 Red-Black 트리는 균형 이진 트리입니다.
이진트리 속성
이진트리는 다음과 같은 속성이 있습니다.
- 이진 트리의 레벨 l에서 노드의 최대 수는 \(2^l\) 입니다.
- 높이가 h이고 하나의 노드를 가진 트리의 높이가 1이라면 최대 노드 수는 \(2^h -1\) 이고 높이가 0이라면 \(2^{h+1}-1\) 입니다.
- 잎 노드 높이가 1이라면 최소 높이는 \(log_{2}(N+1)\) 입니다. 잎 노드의 높이가 0이라면 \(log_{2}(N+1) -1\) 입니다.
\(2^h-1 = n\)
\(2^h = n + 1 \)
\(log_{2}(2^h) = log_{2}(n+1)\)
\(h = log_{2}(n+1)\)
- 전 이진트리에서 리프 노드 수는 항상 자식이 두 개인 노드보다 하나 더 많습니다.
L = 리프 노드 수
T = 두 명의 자식을 가진 internal node 수
L = T + 1
이진트리 표현
이진트리는 배열 또는 연결 리스트로 표현이 가능합니다.
배열(순차) 표현
이진트리는 다음과 같은 속성 때문에 배열로 표현이 가능합니다.
루트 노드의 인덱스 i가 0인 경우
- 노드 i에 왼쪽 자식은 2*i+1 번째 노드이다.
- 노드 i에 오른쪽 자식은 2*i+2 번째 노드이다.
- 노드 i에 부모는 (i-1)/2 번째 노드이다.
루트 노드의 인덱스 i가 1인 경우
- 노드 i에 왼쪽 자식은 2*i 번째 노드이다.
- 노드 i에 오른쪽 자식은 2*i+1 번째 노드이다.
- 노드 i에 부모는 i/2 번째 노드이다.
배열을 사용하면 노드 접근이 빠르고 구현이 용이하다는 장점이 있지만,
편향 이진트리 같은 경우 많은 공간이 낭비될 수 있고 배열 크기 이상 노드를 추가할 수 없습니다.
연결 리스트 표현
포인터를 사용하여 이진트리를 표현할 수 있습니다.
노드들이 가지고 있는 데이터가 정수라고 한다면 다음과 같이 표현할 수 있습니다.
struct BinaryTreeNode {
int data;
struct BinaryTreeNode *left
struct BinaryTreeNode *right
}연결 리스트는 배열보단 접근 속도가 느리지만 삽입 삭제가 쉽고 노드를 포인터로 연결하기 때문에 노드 수에 제한이 없습니다.
이진트리 용도
다음은 이진트리가 중요한 역할을 수행하는 응용들입니다.
- 수식트리(Expression Tree)
- 허프만 코딩 트리(Huffman coding tree)
- 이진 검색 트리(Binary Search Tree, BST)
- 우선 순위 큐(PQ)
