7. Tree

 

 

Tree

정의: Direct Acyclic Graph

노드로 구성된 자료구조

Term

• level( =degree): 
• leaf nodes( =internal nodes): 자식이 없는 노드
• height(=depth): 루트 노드에서 가장 깊숙히 있는 노드의 깊이
• root: 첫 번째 노드 
• sibling: 같은 부모를 가지는 노드

 

List representation: (A (B (E (K, L), F), C (G), D (H (M), I, J) ) )

 

Binary Tree

각 노드에 왼쪽 child and/or 오른쪽 child가 있는 트리

(정확히 두 자녀는 중간 아이가 아닌 왼쪽 아이와 오른쪽 아이를 의미하기 때문에)

 

즉 얘들도 binary tree 이다.

 

 

Full Binary Tree

: depth가 $k$ 일 때, 총 노드의 갯수가 $ 2^k -1$ 인 이진트리

 

• Level i 의 노드 갯수: $2^{i-1}$

• Depth k 일때 트리의 총 노드 갯수: $ 2^k-1$

 

=> n개 노드의 전체 이진 트리의 깊이는 $\theta(\log n)$이다. 트리를 사용하는 많은 작업에는 트리 내 일부 경로의 깊이와 일치하는 실행 시간이 있다. 만약 완전한 이진 트리(또는 그 근처에 있는 트리)가 있다면, 우리는 그러한 작업이 $O(\log n)$에서 실행된다는 것을 안다.

 

$$ n = 2^k - 1 \\ n+1 = 2^k \\ \log_2(n+1) = \log_2(2^k) \\ \log_2(n+1) = k \\ \theta(\log n) = k \\ O(\log n) \\ $$

 

 

Complete Binary Tree

마지막 레벨을 제외한 모든 레벨의 node가 완전히 채워져 있으며 마지막 레벨의 node들은 가능한 한 왼쪽부터 채워져 있는 구조

 

• n개의 노드를 가진 완전 이진 트리의 높이: $ \lceil \log_2 (n+1) \rceil, \ \lceil x \rceil \ is \ the \ smallest \ integer \ \geq x $

 

Proof)

 

$ n = 2^k-1, for \ k \geq 1, \\ 2^k = n+1 \\ \log_2(2^k) = \log_2(n+1) \\ k = \log_2(n+1) \\ k = \lceil \log_2(n+1) \rceil \\ $

 

 

Binary Tree in Memory

• Left child(i) = 2i
• Right child(i) = 2i + 1
• Parent(i) = $ \lfloor i / 2 \rfloor $

 

한계

이 트리는 12개의 노드를 가지고 있으며 32개의 요소를 배열해야 한다.

노드 K의 자식으로 노드 하나를 추가하면 어레이에 필요한 메모리가 두 배로 증가함!

최악의 경우 깊이 $k$의 기울어진 트리는 $O(2^k)$인 $2^k – 1$ 공간이 필요하다. 하지만 그 중 $k$만 사용하게 된다.

 

 

구현

• 트리 구조체 생성

typedef struct node *pTree;
typedef struct node{
    int item;
    pTree left;
    pTree right;
}node;

 

 

트리 순회 (DFS, Depth-First-Traversal)

BFS 사용: 레벨 순서(level-order)대로 방문

 

체계적인 방식으로 트리의 각 노드를 정확히 한 번 방문하는 프로세스를 나타냅니다.

L과 R에 대한 V(방문 노드)의 위치 때문에 inorder, postorder 및 preorder라고 부른다.

 

DFS 사용: LVR (inorder), LRV(postorder), VLR(preorder)

 

 

LVR (inorder)

1. 왼쪽 서브 트리를 순회
2. 서브 트리의 루트를 방문 (printf)
3. 오른쪽 서브 트리를 순회

 

void inorder(pTree ptr) {
	if (ptr) {
		inorder(ptr->left); // left L
		printf("%c", ptr->item); // visit V
		inorder(ptr->right); // right R
	}
}

 

 

스택을 사용한 inorder 탐색 (재귀 X)

1. 빈 스택 S를 선언한다.
2. 탐색을 시작할 노드를 설정한다.
3. S에 노드를 push하고 노드가 NULL이 될 때까지 node = node->left
4. 노드가 NULL이고 스택이 비어 있지 않으면

a) 스택에서 상단 항목을 pop한다.

b) pop한 노드의 node->item을 출력하고 node = node->right

c) 3단계로 이동.

 

1. 노드가 NULL이고 스택이 비어 있으면 완료

void iterativeInorder(pTree node) { // node to start
    int top = -1; // initialize stack
    pTree stack[MAX_STACK_SIZE];// get a stack
    for (;;) {
        for (; node; node = node->left)
            push(node);
        
        node = pop();
        if (!node) break;
        printf("%d", node->item);
        node = node->right;
    }
}

 

 

LRV (postorder)

1. 왼쪽 서브 트리를 순회
2. 오른쪽 서브 트리를 순회
3. 서브 트리의 루트를 방문 (printf)

void postorder (pTree ptr) {
    postorder(ptr->left);
    postorder(ptr->right);
    printf("%c", ptr->item);
}

Output(LVR): A B / C * D * E +

 

 

VLR (preorder)

1. 서브 트리의 루트를 방문 (printf)
2. 왼쪽 서브 트리를 순회
3. 오른쪽 서브 트리를 순회

void preorder (pTree ptr) {
    printf("%c", ptr->item);
    preorder(ptr->left);
    preorder(ptr->right);
}

 

Output(VLR): F B A D C E G I H

 

 

결론

1. 다른 leaf들을 검사하기 전에 루트를 방문해야 한다는 것을 알고 있다면 pre-order (VLR) 방식을 차용한다.
2. 다른 노드보다 먼저 leaf들을 탐색해야한다는 것을 알고 있다면 post-order (LRV) 을 선택합니다.
3. 그 외의 경우 in-order(LVR) 를 사용해야합니다.