개념
순서 트리(ordered tree)의 일종으로서 각 노드의 차수가 2이하인 트리이다. 모든 노드의 차수가 0, 1 또는 2인 트리는 모두 해당이 된다.
성질
- 임의의 이진 트리에서 단말 노드(terminal node)의 수 n0와 차수가 2인 간 노드(nonterminal node)의 수 n2 사이에는 n0 = n2 + 1 의 관계가 성립한다.
- 모든 노드의 수가 n인 완전 이진 트리의 i번째 노드에 대해 다음 성질이 있다.
- parent(i)는 i=1이 아니면 i/2에 위치한다. i=1일 때는 근을 나타내므로 부모 노드가 존재하지 않는다.
- lchild(i)가 2i≤n이면 2i번째에 위치한다. 만약 2i>n이면, i의 왼쪽 밑에 존재하는 노드는 없다.
- rchild(i)가 2i+1≤n이면 2i+1번째에 위치한다. 만약 2i+1>n이면 i의 오른쪽 밑에 존재하는 노드가 없다.
- 노드의 수가 n인 임의의 이진 트리를 두 개의 링크를 사용하여 기억 공간에 저장했을 때 링크의 내용이 0인 링크(null link)의 전체 개수는 n+1이 된다.
추상 데이터 타입(ADT)
- p.left(): p의 왼쪽 자식을 반환한다. p가 외부 노드이면 에러가 발생한다.
- p.right(): p의 오른쪽 자식을 반환한다. p가 외부 노드이면 에러가 발생한다.
- p.parent(): p의 부모를 반환한다. p가 루트이면 에러가 발생한다.
- p.is_root(): p가 루트이면 true를 그렇지 않으면 false를 반환한다.
- p.is_external(): p가 외부노드이면 true를 그렇지 않으면 false를 반환한다.
- size(): 트리에 있는 노드의 개수를 반환한다.
- empty(): 트리가 비었으면 true를 그렇지 않으면 false를 반환한다.
- root(): 트리의 루트에 대한 위치를 반환한다. 트리가 비었으면 에러가 발생한다.
- positions(): 트리의 모든 노드의 위치 리스트를 반환한다.
구현
C++에서 배열(array)이나 연결 리스트(linked list)를 이용해서 구현할 수 있다.
배열(array)를 이용해서 구현하는 경우 노드에 접근하는 시간이 짧고, 노드에 번호를 붙여 수학적으로 활용하기 쉽다. 그러나 전이진 트리가 아니면 기억 공간이 낭비되고, 노드의 삽입, 제거에 시간을 낭비할 수 있다. 연속된 기억 공간에 저장해야하는 제약 때문에 전체적인 기억 공간 활용도가 낮아질 수 있다.
연결 리스트(linked list)에 저장할 경우 각 노드에 data, 왼쪽 링크, 오른쪽 링크를 저장하는 방법과, data, 왼쪽 링크, 오른쪽 링크, 부모 링크를 저장하는 방법이 있다. 이 경우 기억 장소를 절약할 수 있고, 노드의 삽입과 삭제가 용이하다. 그러나 첫번째 방법에 의하면 부모 노드를 찾는 것이 쉽지 않다.
운행(traversal) 방식
트리의 운행(tree traversal)이란 트리에 있는 모든 정점을 한 번씩 방문하는 것을 말한다. 트리의 순회, 트리의 검색, 트리의 탐색이라고도 한다. 트리는 비선형 자료구조이므로 운행 알고리즘이 필요하다.
전위 운행(preorder travelsal)
ROOT, LEFT, RIGHT 순으로 진행한다. 재귀함수나 스택을 이용하여 구현할 수 있다. 아래의 C++ 코드는 재귀함수를 이용한 방법이다.
void preorder(tree T)
{
if (T != nullptr)
{
cout << T->data << "\n";
preorder(T->lchild);
preorder(T->rchild);
}
}중위 운행(inorder travelsal)
LEFT, ROOT, RIGHT 순으로 진행한다. 재귀함수나 스택을 이용하여 구현할 수 있다. 아래의 C++ 코드는 재귀함수를 이용한 방법이다.
void inorder(tree T)
{
if (T != nullptr)
{
inorder(T->lchild);
cout << T->data << "\n";
inorder(T->rchild);
}
}후위 운행(postorder travelsal)
LEFT, RIGHT, ROOT 순으로 진행한다. 재귀함수나 스택을 이용하여 구현할 수 있다. 아래의 C++ 코드는 재귀함수를 이용한 방법이다.
void postorder(tree T)
{
if (T != nullptr)
{
posteorder(T->lchild);
postorder(T->rchild);
cout << T->data << "\n";
}
}허프만 이진트리(Huffman Tree)
가중 외부 경로 길이가 최소인 이진 트리를 찾는 자료구조이다.
스레드 이진트리(Threaded Binary Tree)
이진 트리에서 자신의 가지에 붙은 것이 없으면 NULL 값으로 표현되는데 이러한 NULL 값들을 효율적으로 이용하기 위하여 NULL값들 대싱네 트리를 운행하는 데 필요한 포인터 정보를 집어넣어 사용하도록 한 것을 말한다.
힙(Heap)
힙은 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙은 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 완전 이진 트리(Complete Binary Tree)를 말한다. 힙 트리에서는 중복된 값을 허용한다.
댓글