- Binary tree
- ex) huffman coding tree, tree traverse, evaluation tree, threaded binary trees
- Heap
- ex) priority queue, insert, delete, sort
Introduction
tree
tree는 계층적인 데이터 구조를 나타내기 위한 자료 구조다.
tree는 root와 sub-trees로 이루어진다.
huffman coding tree
huffman coding tree는 텍스트를 압축하기 위한 알고리즘으로,
빈도가 높은 문자를 짧은 비트로 매칭되도록 트리를 구현한 것이다.
import copy
class Node:
def __init__(self, char, num):
self.right = None
self.left = None
self.data = char
self.freq = num
self.huff = []
class Huffman:
def __init__(self, char, num):
self.root = None
self.char = [char for _, char in sorted(zip(num, char))]
self.num = [num for num, _ in sorted(zip(num, char))]
self.nodes = []
def selectTwo(self, num):
minVal = num[0] + num[1]
minFir = 0
minSec = 1
for i in range(len(num)-1):
if num[i] + num[i+1] < minVal:
minVal = num[i] + num[i+1]
minFir = i
minSec = i+1
return minFir, minSec
def createTree(self):
print("Huffman coding tree")
# step 0. sort char and num
print(self.num)
# step 1. create terminal node
for i in range(len(self.char)):
tmp = Node(self.char[i], self.num[i])
self.nodes.append(tmp)
# step 2. create parent node
while True:
try:
if len(self.num) <= 1:
break
# 인접한 두 개를 더하는 것 중에 제일 작은 노드를 찾는다.
first, second = self.selectTwo(self.num)
# 단말 노드를 합해 부모 노드를 만든다
tmp = Node('', self.nodes[first].freq+self.nodes[second].freq)
tmp.left = self.nodes[first]
tmp.right = self.nodes[second]
# node 리스트, num 리스트를 재조정해준다
self.nodes.pop(first)
self.nodes.pop(second-1)
self.num.pop(first)
self.num.pop(second-1)
self.nodes.insert(first, tmp)
self.num.insert(first, tmp.freq)
# 현 상태 출력
print(self.num)
except:
pass
self.root = tmp
def createCode(self, root, code):
if root.left == None and root.right == None:
root.huff = code
print(root.data, root.huff)
return
else:
root.huff = code
left = copy.deepcopy(code)
left.append('0')
right = copy.deepcopy(code)
right.append('1')
self.createCode(root.left, left)
self.createCode(root.right, right)
# root 노드에서 시작한다.
# 탐색하면서 왼족에는 0, 오른족에는 1을 append 해준다.
def codes(self):
print("Huffman codes")
self.createCode(self.root, [])
# character
char = ['w', 'f', 'r', 'm', 'e', 'd', 'o', 't', 'i', 'a', 'n','\' \'']
# frequency
num = [3, 3, 2, 2, 6, 3, 3, 2, 1, 1, 2, 1]
# character
char = ['a', 'b', 'c', 'd', 'e', 'f']
# frequency
num = [6,5,4,3,2,1]
h = Huffman(char, num)
print()
h.createTree()
print()
h.codes()
Binary trees
binary trees
binary tree는 empty tree가 허용되고, child order를 좌/우로 구분한다.
아래는 이미 생성된 BinaryTree의 높이/깊이를 계산하는 프로그램이다.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
self.treeDepth = 0
self.treeHeight = 0
temp = Node('-')
self.root = temp
temp = Node('+')
self.root.left = temp
temp = Node('/')
self.root.right = temp
temp = Node('*')
self.root.left.left = temp
temp = Node('C')
self.root.left.right = temp
temp = Node('D')
self.root.right.left = temp
temp = Node('E')
self.root.right.right = temp
temp = Node('A')
self.root.left.left.left = temp
temp = Node('B')
self.root.left.left.right = temp
def printBT(self, tree):
if tree:
try:
print("%d" % tree.data)
except:
print("%s" % tree.data)
self.printBT(tree.left)
self.printBT(tree.right)
# 탐색
def inorderSearch(self, node, item):
if node:
if node.data == item:
return node
return None
def depth_node(self, node, item):
if node:
try:
print("%d %d" % (node.data, item))
except:
print("%s %d" % (node.data, item))
self.depth_node(node.left, item+1)
self.depth_node(node.right, item+1)
else:
return -1
def nodeCalculate(self, node):
if node.left or node.right:
return max(self.nodeCalculate(node.left), self.nodeCalculate(node.right)) + 1
else:
return 0
# 탐색
def height_node(self, node, item):
if node:
try:
print("%d" % (node.data), end=' ')
except:
print("%s" % (node.data), end =' ')
print("%d" % self.nodeCalculate(node))
self.height_node(node.left, item)
self.height_node(node.right, item)
else:
return 0
def depth(self, root):
self.finddepth(root, 0)
print(f'tree depth : {self.treeDepth}')
def finddepth(self, root, depth):
# return 조건
if not root:
return 0
else:
if self.treeDepth < depth:
self.treeDepth = depth
self.finddepth(root.left, depth+1)
self.finddepth(root.right, depth+1)
def height(self, root):
self.findheight(self.root, 0) # 결국 root의 depth를 찾는다
print(f'tree height : {self.treeHeight}')
return 0
def findheight(self, root, height):
if root:
if self.treeHeight < height:
self.treeHeight = height
self.findheight(root.left, height+1)
self.findheight(root.right, height+1)
else:
return 0
c = BinaryTree()
c.printBT(c.root)
print('DDDDDDD')
c.depth_node(c.root, 0)
print('HHHHHH')
c.height_node(c.root, 0)
print("TDTDTDTD")
c.depth(c.root)
print("HHHHDDDD")
c.height(c.root)
tree traversal
postorder
def postorder(self, node):
if node:
self.inorder(node.left)
self.inorder(node.right)
print(node.data)
traverse
postorder
A
*
B
+
C
D
/
E
-inorder
def inorder(self, node):
if node:
self.inorder(node.left)
print(node.data)
self.inorder(node.right)
traverse
inorder
A
*
B
+
C
-
D
/
Epreorder
def preorder(self, node):
if node:
print(node.data)
self.inorder(node.left)
self.inorder(node.right)traverse
preorder
-
A
*
B
+
C
D
/
Elevel order
level by level로 출력한다.
이는 Queue를 이용해서 (FIFO) 구현한다.
알고리즘을 생각해보자.
- enqueue : root를 Q에 넣는다.
- dequeue : dequeue하고 출력
- 다시 enqueue : root의 children을 Q에 enqueue
- queue가 empty 해질 때까지(종료 조건) 반복
def level_order(self, node):
queue = [] # FIFO
queue.insert(0, node)
while queue:
tmp = queue.pop(0)
print(tmp.data)
if tmp.left:
queue.insert(0, tmp.left)
if tmp.right:
queue.insert(0, tmp.right)
level_order
-
/
E
D
+
C
*
B
A
iterative inorder
재귀함수를 쓰지 않고 구현하려는 것이다. 잘 생각해보면 되는데, inorder traverse 방식은 왼쪽 -> root -> 오른쪽 순서대로 출력한다는 것을 고려해서 알고리즘을 구상해보자.
<알고리즘>
- 왼쪽 방향 노드를 모두 스택에 push한다.
- 한번 pop해주는데,
만약 스택이 비어있으면 => 종료 조건
그렇지 않으면 => 오른쪽을 탐색
<시간 복잡도>
O(n)
구현
def iterative_inorder(self, node):
stack = []
while True:
while node:
stack.append(node)
node = node.left
try:
node = stack.pop()
except:
break
print(node.data)
node = node.right
iterative_inorder
A
*
B
+
C
-
D
/
E
copy tree
tree를 카피해주는 함수
def copyTree(self, tree):
if tree:
node = Node(tree.data)
node.left = self.copyTree(tree.left)
node.right = self.copyTree(tree.right)
return nodeevaluation tree
수식 평가 트리를 만들어보자
스켈레톤 코드
class Node:
def __init__(self, data):
self.data = data
self.value = None
self.left = None
self.right = None
class EvalTree:
def __init__(self):
pass
def eval_tree(self, node):
pass
c = EvalTree()
c.eval_tree()
print()
구현 완료 :)
class Node:
def __init__(self, data):
self.data = data
self.value = None
self.left = None
self.right = None
class EvalTree: # inorder representation
def __init__(self):
self.root = None
self.value = 0
self.treeDepth = 0
self.treeHeight = 0
temp = Node('+')
self.root = temp
temp = Node('*')
self.root.left = temp
temp = Node('-')
self.root.right = temp
temp = Node('5')
self.root.left.left = temp
temp = Node('4')
self.root.left.right = temp
temp = Node('100')
self.root.right.left = temp
temp = Node('20')
self.root.right.right = temp
def eval_tree(self, node):
if node:
self.eval_tree(node.left)
self.eval_tree(node.right)
if node.data == '+':
node.value = node.left.value + node.right.value
elif node.data == '-':
node.value = node.left.value - node.right.value
elif node.data == '*':
node.value = node.left.value * node.right.value
elif node.data == '/':
node.value = node.left.value / node.right.value
else:
node.value = int(node.data)
print(node.value, end = ' ')
c = EvalTree()
c.eval_tree(c.root)
print(c.root.value)threaded binary tree
threaded binary tree란, 말단 노드에 대해 next node로 연결해준 binary tree의 형태를 말한다.
Binary trees에는 n+1개의 null 링크가 있다.
이 null 링크를 편리하게 다음 노드를 검색할 수 있도록 변경해준 것이 threaded binary tree이다.
특히 inorder-traversal 시퀀스로 탐색하는 경우, 그 전/다음 노드로 연결을 만들어주는 것이 가능하다.
<단말 노드에게 thread pointer를 만들어주는 법>
왼쪽 null link는 previous node에 연결해준다. 오른쪽 null link는 다음 node에 연결해준다. (inorder 기준)
Node Field 구성은?
한 노드의 thread field가 True이면, thread link를 이용하고,
False이면, normal link로 다음 노드로 이동한다.
Thread link를 쓰면, 탐색하다가 단말 노드를 구분해서 계산할 필요가 없다. 링크의 종류가 Normal link인지, Thread link인지만을 고려해주면 된다.
더 이상 탐색할 곳이 없는 '찐' 단말 노드의 경우, root(head)로 연결해준다.
<구현>
by following right link from the root, it is possible to traverse the tree by inorder
Tree를 읽을 때 불필요한 방문을 줄여준다.
Iterative implementation
* tbt_inorder() => main function
노드를 순서대로 읽는다.
특정 노드의 왼쪽 link가 비어있다면, Inorder predecessor로 연결해준다.
만약 오른쪽 link가 비어있다면, inorder successor로 연결해준다.
predecessor or successor가 없다면, root 노드로 연결해준다.
* successor() => find a successor node
predecessor : 자신의 왼쪽 subtree 중 가장 오른쪽 노드
successor : 자신의 subtree 중 가장 왼쪽 노드
def tbt_inorder(self, node):
temp = node
while True:
# 다음 노드를 찾아 출력한다.
temp = self.successor(temp)
if temp == node:
break
print("%3c " % temp.data)
def successor(self, node):
temp = node.right
if not (temp.rightFlag or temp.leftFlag):
while not temp.left_thread:
temp = temp.left
return temp
=> 시간 복잡도 : O(n)
heap
Heap이란?
우선순위 큐를 위해 만들어진 자료구조.
우선순위 큐란, 우선순위의 개념을 큐에 도입한 자료 구조를 의미한다.
데이터들은 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나간다.
우선순위 큐는 힙으로 구현하는 것이 가장 효율적이다 ( 삽입 O(logn), 삭제 O(logn) )
힙은 CBT Complete Binary Tree의 일종이다. (노드가 0개 혹은 2개를 가짐)
힙은 여러 개의 값 중에서 최댓값 / 최솟값을 빠르게 찾아내도록 만든 자료구조이다.
힙은 일종의 [반정렬 상태]를 유지한다.
이때 반정렬 상태는 부모 노드의 값 >= 자식 노드의 값인 정도로 정렬하는 것을 말한다.
힙은 중복된 값을 허용한다.
heap의 종류
<max heap>
부모 노드의 키 값 >= 자식 노드의 키 값인 CBT
<min heap>
max heap과 반대로,
부모 노드의 키 값 <= 자식 노드의 키 값인 CBT
heap으로 구현하는 priority Queue
Queue는 FIFO 자료구조인데,우선순위 큐는 말 그대로 큐에 우선순위를 부여해서 우선순위가 높은 요소를 빨리 내보내는 자료구조를 말한다.
그리고 우선순위 큐는 heap으로 구현하는 것이 가장 효율적이다. heap은 어떤 노드를 삽입할 때마다 재정비가 필요한데, 이 시간은 logn 즉, tree의 높이에 비례한다.
| Data Structure | Insert | Delete |
| Unordered array | O(1) | O(n) |
| Unordered linked list | O(1) | O(n) |
| Sorted array | O(n) | O(1) |
| Sorted Linked list | O(n) | O(1) |
| Max heap | O(logn) | O(logn) |
| Min heap | O(logn) : tree height | O(logn) : tree height |
heap 연산
<insertion to heap>
step 0. 노드를 힙의 마지막 노드에 이어서 삽입한다.
step 1. 부모 노드와 교환하면서 힙의 성질(부모 <= 자식 계층적 관계, CBT 노드당 0/2개)을 만족할때까지 반복한다.
class Heap:
def __init__(self, size):
self.size = size
self.heap = [None] * size
self.count = 0
def isEmpty(self):
return self.count == 0
def isFull(self):
return self.count == self.size
def add_heap(self, item):
if self.isFull():
return
i = self.count
# empty heap이 아니고,
# item이 부모 노드보다 큰 경우에는,
while i != 0 and item > self.heap[i//2]:
# temp 자리에 부모 노드의 값을 저장해두고
self.heap[i] = self.heap[i//2]
# 다시 부모 노드와 부부모 노드를 비교하는 것을 반복한다.
i//=2
# 마침에 부모 노드 >= 자식 노드의 관계가 성립한다면,
# i번째 item으로, item을 저장한다.
self.heap[i] = item
self.count += 1
print("HI1")
print("%2d " % item, end=' ')
print(self.heap)
c = Heap(10)
c.heap = [20,15,14,10,2,None, None, None, None, None]
c.count = 5
c.add_heap(5)
print(c.heap)=> 시간 복잡도는 O(log2n)
<deletion from heap>
> 목표 : 최댓값인 root 값을 힙에서 지우고, 힙을 재정비한다.
> 알고리즘
step 0. return하는 값인 root를 저장해두고 노드를 삭제한다.
step 1. 빈 root의 자리에 말단 노드를 임의로 저장해둔다.
step 2. 임시 root부터 차례로 탐색하면서, 임시 노드가 자식 노드보다 작은 경우가 있다면, swap(부모, 자식)을 해준다.
step 3. 임시 root가 자신의 자리를 찾았으면, 함수를 종료한다.
> 구현
def del_heap(self):
if self.count == 0:
print("Empty heap")
return
# root를 제거한다.
item = self.heap[0]
temp = self.heap[self.count]
self.heap[self.count] = None
self.count -= 1
parent = 1
child = 2
# rebuilding heap
while child <= self.count:
if child < self.count and \
self.heap[child] < self.heap[child+1]:
# child < parent
child += 1
try:
if temp >= self.heap[child]:
# 재구성 완료
break
except:
break
# swap 이 필요한 경우
self.heap[parent] = self.heap[child]
parent = child
child *= 2
if self.count != 0:
# 마지막 탐색 위치에 temp 저장
self.heap[parent] = temp
return item
c = Heap(10)
c.heap = [None,20,15,14,10,2, None, None, None, None]
c.count = 5
c.add_heap(5)
c.del_heap()
print(c.heap)
=> 시간 복잡도는 O(log2n)
heap sort
<heap을 max heap으로 정렬하는 방법>
step 0. 현재 원소로 binary tree / max heap를 생성한다.
step 2. max heap의 루트 노드(최댓값)과 말단 노드를 heap에 맞게 swap해준다.
step 3. 새 루트 노드에 대해 max heap을 rebuilding 해준다.
def heapSort(self):
n = self.size - 1
for i in range(n//2, 0, -1):
self.makeheap(i, n)
print(self.num)
for i in range(n-1, 0, -1):
self.swap(1, i+1)
self.makeheap(1, i)
print(self.num)
def makeheap(self, root, n):
temp = self.num[root]
child = 2 * root
while child <= n:
if child < n and self.num[child] < self.num[child + 1]:
child += 1
if temp > self.num[child]:
break
else:
self.num[child//2] = self.num[child]
child * 2
self.num[child//2] = temp
=> 시간 복잡도 : O(nlogn)
* O(n) : 최초로 max heap을 만드는 과정
* n * O(log2n) : 각 element에 대하여 heapify() 해주는 과정
'Computer Science > 자료구조' 카테고리의 다른 글
| 자료구조 | Shortest Path and Activity Network (0) | 2022.01.09 |
|---|---|
| 자료구조 | Binary Search Trees, AVL tree, B-Trees | python 구현 (0) | 2022.01.08 |
| 자료구조 구현 | selection sort, bubble sort, insertion sort, shell sort, quick sort (python 구현) | 정렬 (0) | 2022.01.08 |
| 자료구조 | Shortest Path and Activity Network | 숙명여대 학점교류 (0) | 2022.01.07 |
| 자료구조 | Graph | 숙명여대 학점교류 (0) | 2022.01.07 |