[알고리즘] Tree - 트리와 이진트리

Tree -  트리와 이진트리

트리라는 것은 쉽게 말해 계층적인 구조를 표현하기 위해서

사용하는 것이다.

일반적으로 조직도나 가계도, 파일 시스템 등에서 많이 사용된다.

tree에서 각각의 노드(node)라고 하며, 

노드에서 뻗어나오는 가지를 링크(link)라고한다.

그리고 맨 꼭대기에 있는 노드를 루트(root)라고한다.

마지막으로 마지막 레벨의 노드를 리프(leaf) 노드 라고한다.

또한 상위계층의 노드를 부모 노드 라고 하며

하위계층을 자식 노드 라고 하는데 이 명칭은 상대적이다.

예를 들어, 어떤 노드의 자식노드가 상대적으로 부모 노드가 될수있다는 것이다.

따라서 부모가 없는 노드를 루트 노드 라고 하거나, 

자식이 없는 노드를 리프 노드 라고 할수도 있다.

2단계 상위 노드를 조상(ancestor), 하위 노드를 자손(descendant) 노드 라고 한다.

계층에 따른 높이를 레벨로 표시하는데

root 부터 level 1이며 밑으로 갈수록 레벨이 높아진다.

root가 level 0이 되는 경우도 있는데, 취향에 따라 지정하면 된다.

위의 그림을 잘 관찰해보면 특징이 보이는데

바로, 노드의 개수가 n개이면 링크의 개수는 n-1개가 된다는 것이다.

또한, 루트에서 어떤 노드로 가는 경로는 유일하다. 

그리고 임의의 두 노드간의 경로도 유일하다.

(같은 노드를 두번 방문하지 않는다는 조건하에)

이진 트리라는 것은 각각의 노드가 최대 2명을 자식을 가지는 트리이다.

즉, 노드의 개수는 없거나 1개 이거나 2개일 수있다.

이진 트리의 노드가 왼쪽에 있는지, 오른쪽에 있는지에 따라 

서로 다른 이진 트리로써 구별이 되어진다.

이것이 이진 트리의 일반적인 정의 이다.

이진 트리는 많은곳에 사용할 수있는데

대표적인 예가 Expression Tree이다.

Expression Tree는 수식을 실제로 계산할 때 

어떤 순서로 계산해야 하는 지를 표현하고 있는 트리이다.

연산자들이 2진 연산자라면 이러한 이진 트리의 형태로 표현이 가능하다.

두번째로 Hoffman Code이다.

Hoffman Code는 어떤 데이터를 압축하거나 인코딩하는 기본적인 알고리즘이다.

어떤 텍스트 파일이 있을때, 그 파일에 있는 각각의 알파벳을 적절하게 인코딩해야한다.

이 때, 인코딩 된 파일의 길이가 최소가 되도록 하는 알고리즘이다.

밑의 텍스트 상자에 나왔듯이

c는 00000, d는 10110, e는 010으로 압축된다.

모든 레벨에서 노드들이 꽉 차있는 트리를 full binary tree 라고 하며,

마지막 레벨에서 오른쪽에서 부터 노드들이 차있는 트리를

complete binary tree라고한다.

이와 같은 이진 트리의 특징으로는

1) 높이가 h인 full binary tree는 (2^n)-1개의 노드를 가진다.

2) 노드가 n개인 full 혹은  complete 이진 트리의 높이는 O(logN)이다.

그렇다면 이진 트리는 어떤 자료구조로 표현 될수 있을까

heap의 경우는 규칙성이 있었으므로 1차원 배열에 저장이 가능했지만

일반적인 이진 트리는 규칙이 없으므로 연결 구조(linked list)에 저장해야한다.

트리에서 각각의 노드가 왼쪽 자식의 주소와 오른쪽 자식의 주소를 가지고 있어야 한다

그리고 가장 중요한 데이터를 보유해야하며

필요하다면 부모 노드의 주소도 저장할 수 있다.

트리에 대해서 첫번째 알고리즘은 순회(traversal)이다.

순회의 종류는 다음과 같은 다양한 방법이 있다.

1) 중순위(in-order) 순회

2) 선순위(pre-order) 순회

3) 후순위(post-order) 순회

4) 레벨오더(level-order) 순회

위의 그림과 마찬가지로 root와 왼쪽, 오른쪽 서브트리로 나눌 때

root, 왼쪽, 오른쪽으로 순회하는 것이 선순위(pre-order),

 왼쪽, 오른쪽, root로 순회하는 것이 후순위(post-order),

왼쪽, root, 오른쪽으로 순회하는것이 중순위(in-order)이다.

INORDER-TREE-WALK(x){
    if x != null    
        then INORDER-TREE-WALK(left[x]);
             print key[x]
             INORDER-TREE-WALK(right[x]);
}
 
PREORDER-TREE-WALK(x){
    if x != null    
        then print key[x]
             PREORDER-TREE-WALK(left[x]);
             PREORDER-TREE-WALK(right[x]);                                                                 
}
 
POSTORDER-TREE-WALK(x){
    if x != null    
        then POSTORDER-TREE-WALK(left[x]);
             POSTORDER-TREE-WALK(right[x]);
             print key[x]
}
 

각각의 순회 방식을 슈도 코드로 표현하면 다음과 같다.

순회를 하는 순서만 다를뿐 알고리즘은 동일하다.

기본적으로 서브 트리를 모두 탐색 해야 하므로 재귀적 속성을 가지고 있다.

위에서 보았던 expression tree이다.

각 노드들의 값을 중순위(in-order) 순회하면 다음과 같은 값이 나온다.

x+y*a+b/c 

각 서브트리를 순회할 때 시작과 종료시에 괄호를 추가하면

다음과 같은 올바른 식이 나온다.

(x+y) * ((a+b)/c) 

마지막으로 각 노드들의 값을 후순위(post-order) 순회 하면

다음과 같이 후위 표기법으로 표기한 값과 동일한 값이 나오게 된다.

x y + a b + c  / *

마지막으로 레벨오더(level order) 순회 이다.

이를 표현하는데 가장 적합한 자료구조는 큐이다.

하나의 큐를 이용해서 레벨 오더(level order) 순회를 표현할 수있다.

큐에 root 노드를 넣고, 꺼내면서 꺼낸 해당 노드들의 자식 노드를 순서대로 방문한다

방문후에 그 자식 노드를 큐의 뒤쪽으로 넣어준다.

이것이 반복되면 레벨 별로 순회가 가능하다.

LEVEL-ORDER-TREE-TRAVELSAL(){
    visit the root;
    Q <- root;
    while Q is not empty do
        v <- dequeue(Q);
        visit children of (v);
        enqueue children of v into Q;                                                                         
}