[자료구조] 7. 이진 트리(Binary tree)
이진 트리(Binary tree)
[이미지]
이진 트리는 특별한 트리로, 자식을 최대 2개 가질 수 있는 트리입니다. 이떄 두 자식을 left child, right child라고 합니다.
용어
n: 노드의 개수
m: internal node(자식이 있는 노드)의 개수
l: leaf node(자식이 없는 최하위 노드)의 개수
h: 트리의 높이
이진 트리의 특성
이진 트리의 성질은 수학적으로 몇가지 특정지을 수 있습니다.
[이미지]
이진트리의 특성상 높이는 log2(n+1) - 1 <= h <= n - 1 입니다. 즉, 높이가 h인 트리의 노드 n의 개수는 최소 h+1, 최대 2^(h+1)-1개가 됩니다.
Proper binary tree와 특성
[이미지]
Proper binary tree는 모든 internal 노드가 2개의 자식이 있는 트리입니다.
이런 구조로 인해 리프 노드의 개수 l이 항상 internal node보다 하나 많은 m+1개입니다(l = m + 1).
Arithmetic expression tree
[이미지]
Proper Binary Tree의 일종으로 산술식을 표현한 트리입니다.
Arithmetic Expressions(산술식)이 트리 형식으로 저장되어 있을때, in-order traversal로 탐색하면 순서에 맞게 실제 수학식으로 출력할 수 있습니다.
[출력 알고리즘]
또한 비슷한 방식으로 트리형식으로 저장된 산술식의 계산도 가능합니다. 이때는 post-order traversal을 사용합니다.
[계산 알고리즘]
완전 이진 트리(Complete binary tree)와 특성
[이미지]
완전 이진 트리란 마지막 레벨은 제외하고 모든 레벨이 차 있으며, 마지막 레벨도 왼쪽부터 체워져 있는 트리를 의미합니다.
탐색
이진 트리는 자식이 최대 2개라는 특성으로 기존의 트리에서의 전위 순회, 후위 순회말고도 다른 특별한 순회가 가능합니다.
중위 순회(In-order traversal)
왼쪽 자식 -> 자신 -> 오른쪽 자식 순으로 탐색을 하는 방식으로, 그 특성상 자식이 2개로 제한되는 이진 트리에서만 가능합니다.
오일러 투어(Euler tour traversal)
dfs방식으로 탐색을 하며 마주치는 모든 노드(이미 방문하여 되돌아간 노드라도)를 모두 탐색하는 방식입니다. 즉 모든 노드를 3번씩 방문하게 됩니다.
Level-order traversal
bfs처럼 트리의 각 단계별로 탐색해 나가는 것입니다. 구현에 큐를 사용합니다.
ADT
Node* p.left()
Node* p.right()
Node* p.parent()이진트리는 특성상 최대 2개의 자식만을 가지기에 자식을 배열로 나타낼 필요없이 left, right로 저장할 수 있습니다.
구현
배열을 이용한 구현
Binary tree의 구현에는 일반 tree와 달리 배열을 사용할 수 있는데, 방법은 다음과 같습니다.
[이미지]
우선 배열 0번은 비워둡니다. 이 비워둔 자리는 이후 트리 수정시 임시 메모리로 사용하기도 합니다.
그다음 다음 규칙으로 배열을 체웁니다. n번 배열의 자식의 위치는 2*n, 2*n+1입니다. n번 노드의 부모를 찾으려면 n/2(int형으로 바뀌니 소수점은 버린다)에 접근하면 됩니다.
이 경우에 complete binary tree라면 매우 높은 효율로 사용이 가능하지만 완전하지 않다면 공간의 낭비가 심할 수 있습니다.