[자료구조] 트리

1. 트리와 이진트리

(1) 트리의 개념

- 트리 : 계층적인 자료의 표현에 적합한 구조

- 루트 노드, 부모/자식/형제, 조상/자손, 간선(에지), 단말(자식이 없는 노드)/비단말 노드(자식이 있는 노드)

- 노드의 차수(자식의 개수), 트리의 차수(각 노드의 차수 중 MAX), 레벨(각 층), 트리의 높이(최대 층의 높이)

(2) 이진 트리

- 모든 노드가 2개의 서브 트리를 가진 트리

- 공집합이거나, 루트와 왼쪽 서브트리, 오른쪽 서브트리로 구성된 노드들의 집합(서브 트리들도 모두 이진트리)

- 포화 이진트리 : 각 레벨의 노드가 꽉 차있는 이진 트리

- 완전 이진트리 : 높이가 h이면 레벨 h-1까지는 노드가 꽉 차고, 마지막 레벨 h는 노드가 순서대로 채워진 트리

- 이진 트리의 성질 : 간선의 개수 = 노드의 개수 -1, 높이가 h일 때 최소 노드의 개수 = 2^h -1

                              n > 노드 n개인 이진 트리 높이 h > log(2)(n+1) 이상 

- 순회 연산 : 트리에 속하는 모든 노드를 한번씩 방문하는 것

- 전위 순회 : 레벨 계산, 문서 출력 = 루트 노드(V) 왼쪽 서브 쿼리(L) 오른쪽 서브 쿼시(R) 순으로 사용

- 중위 순회 : 정렬 = LVR

- 후위 순회 : 폴더 용량 계산 = LRV

- 레벨 순회 : 노드를 레벨 순으로 검사, 큐를 사용하고 순환을 사용하지 않음

class Node :     def __init__(self, elem, link=None) :         self.data = elem         self.link = link class circularQueue :     def __init__ (self) :         self.tail = None     def isEmpty(self) : return self.tail == None     def clear(self) : self.tail = None     def peek(self) :         if not self.isEmpty() :             return self.tail.link.data     def enqueue(self, item) :         node = Node(item, None)         if self.isEmpty() :             node.link = node             self.tall = node         else :             node.link = self.tail.link             self.tail.link = node             self.tail = node     def dequeue(self) :         if not isEmpty() :             data = self.tail.link.data             if self.tail.link == self.tail :                 self.tail = None             else :                 self.tail.link = self.tail.link.link             return data     def size(self) :         if self.isEmpty() : return 0         else :             count = 1             node = self.tail.link             while not node == self.tail :                 node = node.link                 count += 1             return count     def display(self, msg = 'que : ') :         print(msg, end ='')         if not self.isEmpty() :             n = self.tail.link             while not n == self.tail :                 print(n.data, end=' ' )                 n = n.link             print(n.date, end =' ' )         print()          class TNode :     def __init__(self, data, left, right) :         self.data = data         self.left = left         self.right = right          def preorder(n) :     if n is not None :         print(n.data, end=' ')         preorder(n.left)         preorder(n.right) def inorder(n) :     if n is not None :         inorder(n.left)         print(n.data, end=' ')         inorder(n.right) def postorder(n) :     if n is not None :         postorder(n.left)         postorder(n.right)         print(n.data, end=' ') def levelorder(root) :     queue = circularQueue()     queue.enqueue(root)     while not queue.isEmpty() :         n = queue.dequeue()         if n is not None :             print(n.data, end=' ' )             queue.enqueue(n.left)             queue.enqueue(n.right) d = TNode('D',None,None) e = TNode('E',None,None) b = TNode('B',d,e) f = TNode('F',None,None) c = TNode('C',f,None) root = TNode('A',b,c) print('In-order : ', end = ' ') inorder(root) print() print('Pre-order : ', end = ' ') preorder(root) print() print('post-order : ', end = ' ') postorder(root) print() print('level-order : ', end = ' ') levelorder(root) print() print("노드 개수 : %d 개" %count_node(root)) print("단말 개수 : %d 개" %count_leaf(root)) print("높이 : %d " %cal_height(root))

In-order :  D B E A F C  Pre-order :  A B D E C F  post-order :  D E B F C A  level-order :

- 노드 개수 및 높이 반환 함수

# 전체 노드의 수 def count_node(n) :     if n is None :         return 0     else :         return 1+count_node(n.left)+count_node(n.right) # 단말 노드의 수 def count_leaf(n) :     if n is None :         return 0     elif n.left is None and n.right is None :         return 1     else :         return 1+count_leaf(n.left)+count_leaf(n.right) # 높이 def cal_height (n) :     if n is None :         return 0     hLeft = cal_height(n.left)     hRight = cal_height(n.right)     if (hLeft > hRight) :         return hLeft+1     else :         return hRight+1

노드 개수 : 6 개 단말 개수 : 6 개 높이 : 3

2. 힙

(1) 힙의 개념과 연산

- 더미와 모습이 비슷한 완전 이진 트리 기반의 자료 구조

- 가장 큰, 작은 값을 빠르게 찾아내도록 만들어진 자료구조

- 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

- 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

- 삽입(upheap) : 일단 말단에 놓고 비교하며 위로 올림, 시간 복잡도 최악의 경우 O(log(2)n)

 > 루트까지 올라가야 하므로 트리 높이에 해당하는 비교 및 이동 연산

- 삭제(downheap) : 말단을 일단 위로 올리고 비교하며 아래로 내림 O(log(2)n) 

 > 가장 아래까지 내려가야 하므로 트리 높이에 해당하는 비교 연산이 필요

- 구조 : 보통 배열을 이용하여 구현, 완전 이진 트리는 각 노드에 번호를 붙여 배열의 인덱스로 표현

- 힙의 응용 : 허프만 코드 = 이진 트리를 이용하여 글자별 빈도가 다른 메시지의 내용을 압축