이번 챕터에서는 트리 중 가장 대표적인 binary tree (이진 트리)를 기록할 예정이다. 순서는 다음과 같다.
- binary tree
- binary tree의 정의와 종류
- binary tree의 ADT
- binary tree를 linked list로 나타내면? - binary tree traversal
- tree algorithm 종류
1. Binary Tree
1-1. Binary Tree 정의와 종류
Binary Tree는 각 노드가 최대 2개의 자식노드만 갖는 트리를 의미하며, 정확히 2개만 갖는 트리는 proper binary tree라고 부른다.
참고로 트리의 종류를정짓는 요소는 크게 2가지로 structural property, relational property가 있다. structural property는 모양새를 결정짓고, relational property는 노드들의 값의 관계를 결정짓는다.
위에서 binary tree를 정의할 때 각 노드가 최대 2개의 자식 노드를 갖는다고 정의했으므로 이진트리는 모양을 중심으로 정의했다는 것을 알 수 있다.
트리의 종류는 Proper Binary Tree(Full binary tree), Complete Binary Tree, Perfect Binary Tree 총 세 가지가 있다.
Proper Binary Tree는 모든 노드들이 자식노드를 0개 또는 2개를 가지는 트리를 이야기 한다. Complete Binary Tree는 좌측 위에서부터 채워가는 트리로 자식 노드를 1개만 갖는 노드가 1개만 있거나 존재하지 않게 된다. Perfect Binary Tree는 모든 노드가 전부 자식 노드를 2개씩 갖는 트리이다.
1-2. binary tree의 ADT
tree 자체가 갖는 메소드에 아래 4개의 메소드를 추가로 갖는다.
- position left(p)
- position right(p)
- boolean hasLeft(p)
- boolean hasRight(p)
binary tree의 ADT는 다음과 같다.
ADT Binary_Tree(abbreviated BinTree) is
objects : a finite set of nodes either empty or consisting of a root node,
left Binary_Tree and right Binary_Tree.
function :
for all bt, bt1, bt2 ∈ BinTree, item ∈ element
BinTree Create() ::= create an empty binary tree
Boolean IsEmpty(bt) ::= if(bt == empty binary tree)
return TRUE else return FALSE
BinTree MakeBT(bt1, item, bt2) ::= return a binary tree whose left
subtree is bt1, whose right subtree
is bt2, and whose root node contains the
data item.
BinTree Lchild(bt) ::= if(IsEmpty(bt)) return error else
return the left subtree of bt.
element Data(bt) ::= if(IsEmpty(bt)) return error else
return the data in the root node of bt.
BinTree Rchild(bt) ::= if(IsEmpty(bt)) return error else
return the right subtree of bt.
1-3. Binary Tree by Linked List
트리를 배열로 나타내게 된다면 낭비되는 메모리가 상당할 것이다.
이진 트리를 array로 옮기는 방법은 다음과 같다.
- rank(root) = 1
- if node is the left child of parent(node), rank(node) = 2 * rank(parent(node))
- if node is the right child of parent(node), rank(node) = 2 * rank(parent(node)) + 1
이진 트리를 배열로 나타냈을 때, 시간 복잡도를 살펴보면 다음과 같다.
일반 트리랑 차이가 있는 부분은 children이다. 일반트리는 자식노드의 개수가 불확실한 반면, 이진트리는 자식노드가 많아봐야 2개라는 것을 알고 있기 때문에 O(1)으로 끝낼 수 있다.
이진 트리를 linked list로 구현할 때, 저장 공간을 element값, left child node(link), right child node(link), parent node (link) 총 4개로 두는 것이 일반적이다.
2. Binary Tree Traversals
traversals는 마치 트리를 여행하는 것처럼 트리 전체 노드를 스캔하는 알고리즘을 말한다. 따라서 모든 노드를 방문해야 하기 때문에 시간복잡도가 O(n)보다 작을 수 없다.
tree의 알고리즘 종류를 살펴볼 것인데, 그 전에 노드의 depth, 트리의 height를 구하는 알고리즘 먼저 알아보자.
Depth of a Node
depth를 구하는 것은 가장 아래 노드에서 시작한다. 트리의 노드를 v로 가정하자.
해당 노드가 root이면 그 노드의 부모노드는 없는 것이므로 0을 반환하고, root가 아니라면 1을 더해나가면 된다. 이를 반복하는 과정에서 재귀를 이용한다.
Algorithm depth(T,v)
if T.isRoot(v) then
return 0
else
return 1 + depth(T, T.parent(v))이의 worst case는 선형 리스트처럼 위아래 일렬로 이어져있는 트리로, 이 경우 시간복잡도는 O(n-1)이다.
Height of a Tree
Height를 구하는 것은 depth를 이용하면 간단해진다. 모든 노드를 돌며 자식이 더이상 없는 노드들의 depth값을 저장하면 된다. 이를 알고리즘으로 나타내면
Algorithm height1(T) :
h = 0
for each v ∈ T.positions() do
if T.isExternal(v) then
h = max(h, depth(T,v))
return h이 방법 말고 recursion을 사용하는 방법도 있을 수 있다.
Algorithm heightRecursion(T,v)
if T.isExternal(v) then
return 0
else
h = 0
for each w ∈ T.children(v) do
h = max(h, heightRecursion(T,w))
return 1 + h위 알고리즘은 재귀를 사용한 알고리즘으로, v를 루트로 하는 서브트리의 height를 구하라는 의미이다.
============================================================
이제 본격적으로 이진트리의 알고리즘 종류를 살펴볼 것이다. 종류는 스캔하는 노드의 순서에 따라 preorder, postorder, inorder, level-order이 있다.
Preorder Traversal
부모노드 먼저 스캔하는 알고리즘으로 부모->>자식->>형제 순으로 스캔하는 특징을 갖고있다. 알고리즘을 작성하면 다음과 같다.
Algorithm preOrder(v)
visit(v)
for each child w of v
preOrder(w)
러닝타임은 O(n)이다.
Postorder Traversal
이 알고리즘은 자식노드를 먼저 스캔하는 알고리즘으로 자식->>형제->>부모 순으로 스캔하는 특징을 갖고있다. 알고리즘을 작성하면 다음과 같다.
Algorithm postOrder(v)
for each child w of v
postOrder(w)
visit(v)
preorder 알고리즘과 visit의 순서만 다르다. 러닝타임은 preorder과 마찬가지로 O(n)이다.
Inorder Traversal
이 알고리즘은 좌->>부모->>우 순서로 스캔하는 알고리즘으로 그냥 왼쪽에서 오른쪽 노드 순으로 스캔한다는 특징을 가지고 있다. 이러한 특징때문에 binary tree에서 적용된다.
Algorithm inOrder(v)
if hasLeft(v)
inOrder(ledft(v))
visit(v)
if hasRight(v)
inOrder(right(v))
세 가지를 다음 사진으로 한 눈에 비교할 수 있다.
위 세 가지 알고리즘은 stack(후입선출)을 이용한 것이라고 할 수 있다.
반면 이제 설명할 level-order은 선입선출인 queue를 이용한 것이다.
Level-order traversal
이 알고리즘은 자료가 들어온 순서 그대로 나간다.
이를 코드로 작성하면 다음과 같다.
void levelOrder(trreePointer ptr) {
int front,rear = 0;
treePointer queue[MAX_QUEUE_SIZE];
if (!ptr) return;
addq(ptr);
for( ; ; ) {
ptr = deletq();
if (ptr) {
printf("%d",ptr -> data);
if (ptr -> leftChild)
addq(ptr -> leftChild);
if (ptr -> rightChild)
addq(ptr -> rightChild);
}
else break;
}
}