[3. 검색트리] 이진트리 검색 (1)

0. 트리(Tree)

트리는 계층적인 구조를 표현하기 위한 자료구조(조직도, 파일시스템, 가계도 등)로, 노드(node)들과 노드들을 연결하는 링크(link)들로 구성된다.

 

(1) 관련용어

• 부모, 자식 관계
• 형제관계: 루트노드를 제외한 트리의 모든 노드들은 유일한 부모 노드를 가지며, 부모가 동일한 노드들을 형제관계라고 부름
• 리프(leaf) 노드: 자식이 없는 노드들
• 조상-자손 관계
• 부트리(sub-tree): 트리에서 어떤 노드와 그 노드의 자손들로 이루어진 트리(원래 트리의 일부분)
• 레벨(level): 트리에서 각 계층을 의미
• 높이: 트리의 높이는 레벨의 수를 의미

 

(2) 트리의 기본적인 성질

• 노드가 N개인 트리는 항상 N-1개의 링크(link)를 가진다.
• 루트에서 어떤 노드로 가는 경로는 항상 유일하다.
• 임의의 두 노드간의 경로도 유일하다.(같은 노드를 두번 이상 방문하지 않을 때)

 

1. 이진트리(binary tree)

이진 트리는 각 노드가 최대 2개의 자식만을 가지며, 각각의 자식 노드가 부모의 왼쪽 자식인지, 오른쪽 자식인지가 구분되는 트리이다.

 

서로 다른 이진 트리

 

이진 트리의 응용

• Huffman Code: 파일압축 알고리즘 중 가장 유명함. 각각의 알파벳에 이진코드를 부여하는 방법
• Expression Tree: 수식을 이진트리로 표현

 

i. Full Binary Tree

• 모든 층의 노드가 꽉 차있는 이진트리
• 높이가 $h$인 full binary tree는 $2^{h}-1$개의 노드를 가짐

ii. Complete Binary Tree

• 마지막 층을 제외한 모든 층의 노드가 꽉 차있는 이진트리(=Heap 구조)
• 일차원 배열로 데이터를 표현하고 데이터를 배열의 index로 트리구조를 표현할 수 있음!

노드가 $N$개인 Full Binary Tree, Complete Binary Tree 이진 트리의 높이는 $O(logN)$이다(최악의 경우는 한쪽으로만 자식이 연결되어 있다면 $O(N)$임)

 

 

(1) 연결구조(Linked Structure) 표현

일반적인 이진트리는 연결구조를 사용하여 표현한다. 연결구조는 왼쪽&오른쪽 자식의 주소, 부모노드의 주소, 노드의 데이터를 저장한다.

연결구조를 활용한 이진트리의 표현

 

 

(2) 이진트리의 순회(traversal)

이진 트리의 모든 노드를 방문하는 일을 순회(traversal)이라고 하며 알고리즘의 종류는 다음과 같다.

• 중순위(inorder), 선순위(preorder), 후순위(postorder) 순회
• 레벨오더(level-order) 순회

 

i. 중순위(inorder) 순회

먼저 전체 이진트리를 루트노드 $r$, 왼쪽 부트리 $T_{L}$, 오른쪽 부트리 $T_{R}$로 나누어 생각한다. 이때

i. 먼저 $T_{L}$을 inorder로 순회하고

ii. $r$을 순회하고

ii. $T_{R}$을 inorder로 순회한다.

 

 

즉 recursive하게 이진트리를 순회할 수 있으며, 루트노드를 먼저 방문하면 preorder traversal, 오른쪽 부트리를 먼저 방문하면 preorder traversal이라 한다.

 

#inorder traversal pseudo code

inorder_tree_walk(x):
	if x != null:
    	inorder_tree_walk(left[x])
        print(x)
        inorder_tree_walk(right[x])

 

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

이진트리를 각 층(레벨) 순으로 방문하며, 동일 레벨에서는 왼쪽에서 오른쪽 순서로 순회하는 방법이다. Queue를 사용하여 구현할 수 있다.

level-order traversal 개념

 

#inorder traversal pseudo code

level_order_treee_traversal():
	visit root
    Q <- root
    while Q:
    	V <- dequeue(Q)
        visit childeren of V
        Q <- childeren of V

 

 

 

 

[References]

• 권오흠 교수, 알고리즘(강의 링크)