제 10강 트리와 이진트리

 

• 트리 (Tree)

계층적인 구조를 표현하는 데 사용한다.

예를 들면 조직도나 디렉토리와 서브디렉토리의 구조를 표현할 때, 가계도를 표현할 때 쓴다.

 

• 트리는 노드(node) 들과 노드들을 연결하는 링크(link)들로 구성된다.

 

• 루트(root) : 맨 위의 노드
• 링크(link) : 노드들을 연결하는 선 (=edge, branch)

 

 

• 트리의 부모-자식 관계

트리 구조 상에서 상대적으로 위에 있는 노드를 부모 노드라 하고, 아래에 있는 노드를 자식 노드라 한다.

 

 

• 트리의 형제 관계

부모가 동일한 노드들을 형제(sibling) 관계라고 한다.

루트 노드를 제외한 트리의 모든 노드들은 유일한 부모 노드를 가진다.

 

 

• 리프노드

자식이 없는 노드들을 리프(leaf) 노드라 한다.

리프노드가 아닌 노드들을 내부(internal)노드라 한다.

 

 

• 트리의 조상-자손 관계

부모-자식 관계를 확장한 것이 조상-자손 관계이다.

 

 

• 부트리(subtree)

트리에서 어떤 한 노드와 그 노드의 자손들로 이루어진 트리를 부트리(subtree)라고 부른다.

트리에서 어떤 일부분을 잘라내어 봤을 때 트리가 된다는 의미이다.

 

 

• 트리의 레벨

트리의 노드들은 레벨로 구분할 수 있다.

루트노드는 level 1 또는 level 0이 된다. (붙이는 사람 나름)

그리고 루트노드의 자식노드들은 루트노드가 level1인 경우에는 모두 level2가 되고, 루트노드가 level0인 경우에는 모두 level1이 된다.

 

 

• 트리의 높이

서로 다른 레벨의 갯수를 말한다.

 

 

• 트리의 기본적인 성질

- 노드가 N개인 트리는 항상 N-1개의 링크(link)를 가진다.

- 트리에서 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의의 두 노드간의 경로도 유일하다. (같은 노드를 두 번 이상 방문하지 않는다는 조건 하에!)

 

 

• 이진트리 (binary tree)

- 이진 트리에서 각 노드는 최대 2개의 자식을 가진다.

- 각각의 자식 노드는 자신이 부모의 왼쪽 자식인지, 오른쪽 자식인지가 지정된다. (자식이 한 명인 경우에도!!)

 

 

• 이진트리 응용의 예 1) Expression Tree

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

위의 이진트리는 다음과 같은 식을 표현한다.

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

 

 

 

• 이진트리 응용의 예 2) Huffman Code

: 어떤 테이터를 압축/인코딩하는 가장 기본적인 알고리즘 중 하나이다.

가변 길이를 인코딩할 때, 예를 들어 어떤 텍스트파일이 있는데, 그 파일의 내용이 알파벳 a~z 로 구성되어 있다고 할 때,

그 파일의 크기가 최소가 되도록 인코딩하는 방식이다.

ko.wikipedia.org/wiki/%ED%97%88%ED%94%84%EB%A8%BC_%EB%B6%80%ED%98%B8%ED%99%94

 

 

• Full Binary Tree

- 모든 노드들이 꽉꽉 차 있는 트리

- 높이가 h인 Full Binary Tree는 2^h-1개의 노드를 가진다.

- 노드가 N개인 Complete Binary Tree의 높이는 O(logN)이다. (노드가 N개인 이진트리의 높이는 최악의 경우, N이 될 수도 있다.)

 

 

• Complete Binary Tree

- 맨 마지막 레벨을 제외한 모든 노드들은 꽉꽉 차 있다. 단 오른쪽에서부터 빈다.

- 노드가 N개인 Complete Binary Tree의 높이는 O(logN)이다. (노드가 N개인 이진트리의 높이는 최악의 경우, N이 될 수도 있다.)

- Heap이 이에 해당한다.

 

 

• 이진트리의 표현 : 연결리스트

- 연결구조(Linked Structure)을 표현할 때 쓴다. 대표적인 예가 연결리스트. (Linked List)

- 각 노드에 하나의 데이터 필드와 왼쪽자식(left)의 주소, 오른쪽자식(right)의 주소, 그리고 부모노드(p)의 주소를 저장한다. (부모노드의 주소는 반드시 필요한 경우가 아니면 보통 생략한다..)

 

 

 

• 이진트리의 순회 (Traversal)

- 순회 : 이진 트리의 모든 노드를 방문하는 일

- 중순위(in-order) 순회

- 선순위(pre-order) 순회

- 후순위(post-order) 순회

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

 

중순위, 선순위, 후순위는 루트 노드를 몇 번째 방문하느냐를 기준으로 생각하면 된다.

 

중순위 순회는 루트노드를 왼쪽과 오른쪽 중간에 방문한다.

선순위 순회는 루트노드를 왼쪽, 오른쪽보다 가장 먼저 방문한다.

후순위 순회는 루트노드를 왼쪽, 오른쪽을 모두 방문한 후에 방문한다.

 

* 중순위 순회

1. 먼저 트리의 왼쪽을 inorder로 순회하고,

2. 루트를 순회하고,

3. 트리의 오른쪽을 inorder로 순회한다.

 

다음은 각각을 표현한 의사코드이다.

// 중순위 순회
INORDER-TREE-WALK(x){
	if x != null
    	then
        	INORDER-TREE-WALK(left[x])
        	print key[x]
        	then INORDER-TREE-WALK(rignt[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(rignt[x])
            print key[x]
}

 

 

• Expression Trees

위의 Expression Tree를 inorder 순회하면 다음과 같이 출력된다.

x + y * a + b / c

 

각 부트리를 순회할 때, 시작과 종료시에 괄호를 추가하면 다음과 같이 올바른 수식이 출력된다.

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

 

Postorder 순회하면 후위표기식이 출력된다.

x y + a b + c / *

 

 

• 레벨 오더 순회 (Level-Order)

- 레벨 순으로 방문, 동일 레벨에서는 왼쪽에서 오른쪽 순서로 방문한다.

- 큐(queue)를 이용하여 구현한다.

위의 트리를 예로 들면, * + / x y + c a b 이다.

// Level-Order 순회
LEVEL-ORDER-TREE-TRAVERSAL()
	visit the root;
    Q <- root;	// Q is a queue
    while Q is not empty, do
    	V <- dequeue(Q)	// dequeue 는, 큐에서 꺼낸다는 뜻
        visit children of v;
        enqueue children of v into Q;
    end
end