트리란?
- 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조
- 트리 관련 용어
- 루트 노드: 부모가 없는 최상위 노드
- 단말 노드: 자식이 없는 노드
- 크기: 트리에 포함된 모든 노드의 개수
- 깊이: 루트 노드부터의 거리
- 높이: 깊이 중 최댓값
- 차수: 각 노드의 (자식 방향) 간선 개수
- 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1개
이진 트리
- 이진 트리의 정의
- (서브 트리가) 공집합이거나
- 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 집합, 이진 트리의 서브 트리들은 모두 이진 트리이어야 함
- 이진 트리의 분류
- 포화 이진 트리
- 트리의 각 레벨에 노드가 꽉 차있는 이진 트리
- 전체 노드의 수: 높이가 h일 때, 2ʰ-1
- 완전 이진 트리
- 높이가 h일 때, 레벨 1부터 h-1까지 노드가 모두 채워짐
- 마지막 레벨 h에서는 노드가 순서대로(왼쪽부터 차례로) 채워짐
- 전체 노드의 수: 높이가 h일 때, 2ʰ⁻¹ ~ 2ʰ-1
- 이진 트리의 성질
- 노드의 개수가 n개 이면 간선의 개수는 n-1
- 높이가 h이면 h ~ 2ʰ-1개의 노드를 가짐
- n개 노드의 이진 트리 높이: ⌈log₂(n+1)⌉ ~ n
- 이진 트리의 표현
- 배열 표현법
- 노드 i의 부모 노드 인덱스 = i//2
- 노드 i의 왼쪽 자식 노드 인덱스 = i*2
- 노드 i의 오른쪽 자식 노드 인덱스 = i*2+1
- 링크 표현법
- 2개의 링크를 통해 왼쪽 자식과 오른쪽 자식과 연결
- 해당 링크의 자식이 없을 때는 None을 갖음
- 이진 트리의 기본 순회
- 전위 순회: 루트 → 왼쪽 서브트리 → 오른쪽 서브트리
- 중위 순회: 왼쪽 서브트리 → 루트 → 오른쪽 서브트리
- 후위 순회: 왼쪽 서브트리 → 오른쪽 서브트리 → 루트
- 레벨 순회: 노드를 레벨 순으로 검사
순회 구현
from collections import deque
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): # 레벨 순회
que = deque() # 큐
que.append(root)
while que:
node = que.popleft()
if node is not None:
print(node.data, end=' ')
que.append(node.left)
que.append(node.right)
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 count_leaf(n.left) + count_leaf(n.right)
def calc_height(n): # 트리의 높이 계산
if n is None:
return 0
hLeft = calc_height(n.left)
hRight = calc_height(n.right)
if hLeft > hRight:
return hLeft + 1
else:
return hRight + 1
if __name__ == '__main__':
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('\n In-Order: ', end='')
inorder(root)
# In-Order: D B E A F C
print('\n Pre-Order: ', end='')
preorder(root)
# Pre-Order: A B D E C F
print('\n Post-Order: ', end='')
postorder(root)
# Post-Order: D E B F C A
print('\nLevel-Order: ', end='')
levelorder(root)
# Level-Order: A B C D E F
print()
print('노드의 개수 = {}개'.format(count_node(root)))
# 노드의 개수 = 6개
print('단말의 개수 = {}개'.format(count_leaf(root)))
# 단말의 개수 = 3개
print('트리의 높이 = {}'.format(calc_height(root)))
# 트리의 높이 = 3
힙 트리
- 힙 트리의 정의
- 완전 이진 트리 기반의 자료구조
- 가장 큰(또는 작은) 값을 빠르게 찾아내도록 만들어진 자료구조
- 최대 힙, 최소 힙의 정의
- 최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
- 최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
- 힙의 연산: 삽입
- 삽입
- 삽입을 하더라도 힙의 특성과 완전 이진 트리는 유지해야 함
- Upheap(shift-up)
- 새로운 항목을 힙의 마지막 노드의 다음 위치에 삽입
- 부모 노드와 비교하여 힙의 순서 특성을 만족
- 시간 복잡도: O(log₂n)
- 힙의 연산: 삭제
- 삭제
- Downheap(shift-down)
- 루트 노드를 삭제하고 빈 루트 자리에 마지막 노드를 가져옴
- 루트 노드와 그 자식 노드가 힙의 순서 특성을 만족
- 시간 복잡도: O(log₂n)
- 힙의 구현: 배열 구조
- 힙은 보통 배열을 이용하여 구현
- 완전 이진 트리 → 각 노드에 번호를 붙임 → 배열의 인덱스
- 부모 노드와 자식 노드의 관계
- 부모 노드 인덱스 = (자식 인덱스)//2
- 왼쪽 자식 노드 인덱스 = (부모의 인덱스)*2
- 오른쪽 자식 노드 인덱스 = (부모의 인덱스)*2+1
최대 힙 구현
class MaxHeap: # 최대 힙 클래스
def __init__(self): # 생성자
self.heap = [] # 배열을 이용한 힙
self.heap.append(0) # 0번 항목은 사용 X
def size(self): # 힙의 크기
return len(self.heap) - 1
def isEmpty(self): # 공백 검사
return self.size() == 0
def Parent(self, i): # 부모노드 반환
return self.heap[i//2]
def Left(self, i): # 왼쪽 자식노드 반환
return self.heap[i*2]
def Right(self, i): # 오른쪽 자식노드 반환
return self.heap[i*2+1]
def display(self, msg='힙 트리:'):
print(msg, self.heap[1:])
def insert(self, n):
self.heap.append(n) # 맨 마지막 노드로 일단 삽입
i = self.size() # 노드 n의 위치
while i != 1 and n > self.Parent(i): # 부모보다 큰 동안 계속 업힙
self.heap[i] = self.Parent(i) # 부모를 끌어내림
i = i // 2 # i를 부모의 인덱스로 올림
self.heap[i] = n # 마지막 위치에 n 삽입
def delete(self):
parent = 1
child = 2
if not self.isEmpty():
hroot = self.heap[1] # 삭제할 루트를 저장
last = self.heap[self.size()] # 마지막 노드
while child <= self.size(): # 마지막 노드 이전까지
# 오른쪽 노드가 더 크면 child를 1 증가 (기본은 왼쪽 노드)
if child < self.size() and self.Left(parent) < self.Right(parent):
child += 1
# 마지막 노드가 더 큰 자식보다 크면 삽입 위치를 찾음
if last >= self.heap[child]:
break
self.heap[parent] = self.heap[child] # 아니면 다운힙 계속
parent = child
child *= 2
self.heap[parent] = last # 맨 마지막 노드를 parent위치에 복사
self.heap.pop(-1) # 맨 마지막 노드 삭제
return hroot # 저장해두었던 루트 반환
if __name__ == '__main__':
heap = MaxHeap()
data = [2, 5, 4, 8, 9, 3, 7, 3]
print("[삽입 연산]:", data)
# [삽입 연산]: [2, 5, 4, 8, 9, 3, 7, 3]
for elem in data:
heap.insert(elem)
heap.display('[ 삽입 후 ]:')
# [ 삽입 후 ]: [9, 8, 7, 3, 5, 3, 4, 2]
heap.delete()
heap.display('[ 삭제 후 ]:')
# [ 삭제 후 ]: [8, 5, 7, 3, 2, 3, 4]
heap.delete()
heap.display('[ 삭제 후 ]:')
# [ 삭제 후 ]: [7, 5, 4, 3, 2, 3]
최소 힙 구현
class MinHeap: # 최소 힙 클래스
def __init__(self): # 생성자
self.heap = [] # 배열을 이용한 힙
self.heap.append(0) # 배열을 이용한 힙
def size(self): # 힙의 크기
return len(self.heap) - 1
def isEmpty(self): # 공백 검사
return self.size() == 0
def Parent(self, i): # 부모노드 반환
return self.heap[i//2]
def Left(self, i): # 왼쪽 자식노드 반환
return self.heap[i*2]
def Right(self, i): # 오른쪽 자식노드 반환
return self.heap[i*2+1]
def display(self, msg='힙 트리: '):
print(msg, self.heap[1:])
def insert(self, n):
self.heap.append(n) # 맨 마지막 노드로 일단 삽입
i = self.size() # 노드 n의 위치
while i != 1 and n < self.Parent(i): # 부모보다 작은 동안 계속 업힙
self.heap[i] = self.Parent(i) # 부모를 끌어내림
i = i // 2 # i를 부모의 인덱스로 올림
self.heap[i] = n # 마지막 위치에 n 삽입
def delete(self):
parent = 1
child = 2
if not self.isEmpty():
hroot = self.heap[1] # 삭제할 루트를 저장
last = self.heap[self.size()] # 마지막 노드
while child <= self.size(): # 마지막 노드 이전까지
# 오른쪽 노드가 더 작으면 child를 1 증가 (기본은 왼쪽 노드
if child < self.size() and self.Left(parent) > self.Right(parent):
child += 1
# 마지막 노드가 더 작은 자식보다 작으면 삽입 위치를 찾음
if last <= self.heap[child]:
break
self.heap[parent] = self.heap[child] # 아니면 다운힙 계속
parent = child
child *= 2
self.heap[parent] = last # 맨 마지막 노드를 parent위치에 복사
self.heap.pop(-1) # 맨 마지막 노드 삭제
return hroot # 저장해두었던 루트 반환
if __name__ == '__main__':
heap = MinHeap()
data = [2, 5, 4, 8, 9, 3, 7, 3]
print("[삽입 연산]:", data)
# [삽입 연산]: [2, 5, 4, 8, 9, 3, 7, 3]
for elem in data:
heap.insert(elem)
heap.display('[ 삽입 후 ]:')
# [ 삽입 후 ]: [2, 3, 3, 5, 9, 4, 7, 8]
heap.delete()
heap.display('[ 삭제 후 ]:')
# [ 삭제 후 ]: [3, 5, 3, 8, 9, 4, 7]
heap.delete()
heap.display('[ 삭제 후 ]:')
# [ 삭제 후 ]: [3, 5, 4, 8, 9, 7]
