트리 Tree
node(정점)와 edge(간선)를 이용하여 데이터의 배치 형태를 추상화한 자료구조
- 루트 노드 + 리프 노드 + 내부 노드
- 부모 노드 + 자식 노드
노드의 종류
- root node
맨 위 시작 노드 - leaf node
맨 아래 마지막 노드, 자식 노드가 없는 노드 - internal node
그 외의 중간 노드 - parent node
두 노드가 상하관계로 연결되어 있을때, 상대적으로 루트에서 가까운 노드 - child node
두 노드가 상하관계로 연결되어 있을때, 상대적으로 루트에서 먼 노드 - sibling node
같은 parent node를 갖는 노드 - ancestor node
parent node부터 root node까지 이어지는 모든 노드 - descendant node
child node부터 leaf node까지 이어지는 모든 노드
용어
-
level(수준)
루트에서 얼마나 멀리 떨어져 있는지를 나타낸 것
= 루트 노드 level 0으로 시작하여 거쳐온 edge의 수 -
height(높이) · depth(깊이)
루트에서 가장 멀리 있는 리프까지의거리
= 노드의 최대 level + 1 -
degree(차수)
각 노드가 갖는 자식의 수
= child node로 이어진 edge의 수 -
subtree(서브트리 · 부분트리)
어떤 노드를 루트로 하고, 그 자손으로 구성된 트리, leaf node의 degree = 0
= 노드의 degree
이진 트리 Binary Tree
모든 노드의 차수가 2 이하인 트리
- 재귀적으로 정의 가능
- empty tree
- root node + left subtree + right subtree
(단, 이때 왼쪽과 오른쪽 서브트리 또한 이진트리)
연산
- size() : 노드의 수
- depth() : 트리의 깊이
- traversal() : 순회
- 깊이 우선 순회 DFS (Depth First Traversal)
- 넓이 우선 순회 BFS (Breadth First Traversal)
구현
- 노드
class Node:
def __init__(self,item):
self.data = item
self.left = None
self.right = None- 트리
class BinaryTree:
def __init(self,r):
self.root = r- size()
전체 이진 트리의 size() = left subtree의 size() + right subtree의 size() + 1(자기 자신)
class Node:
def size(self):
l = self.left.size() if self.left else 0
r = self.right.size() if self.right else 0
return l + r + 1
class BinaryTree:
def size(self):
if self.root:
return self.root.size()
else:
return 0- depth()
전체 이진 트리의 depth() = left subtree의 depth()와 right subtree의 depth() 중 더 큰 것 + 1
class Node:
def depth(self):
l = self.left.depth() if self.left else 0
r = self.right.depth() if self.right else 0
return max(l,r) + 1
class BinaryTree:
def depth(self):
if self.root:
return self.root.depth()
else:
return 0깊이 우선 순회 DFS
- 중위 순회 in-order traversal
left subtree → 자기 자신 → right subtree
class Node:
def inorder(self):
traversal = []
if self.left:
traversal += self.left.inorder()
traversal.append(self.data)
if self.right:
traversal += self.right.inorder()
return traversal
class BinaryTree:
def inorder(self):
if self.root:
return self.root.inorder()
else:
return []- 전위 순회 pre-order traversal
자기 자신 → left subtree → right subtree
class Node:
def preorder(self):
traversal = []
traversal.append(self.data)
if self.left:
traversal += self.left.preorder()
if self.right:
traversal += self.right.preorder()
return traversal
class BinaryTree:
def preorder(self):
if self.root:
return self.root.inorder()
else:
return []- 후위 순회 post-order traversal
left subtree → right subtree → 자기 자신
class Node:
def postorder(self):
traversal = []
if self.leftr:
traversal += self.left.postorder()
if self.right:
traversal += self.right.postorder()
traversal.append(self.data)
return traversal
class BinaryTree:
def postorder(self):
if self.root:
return self.root.postorder()
else:
return []넓이 우선 순회 BFS
- level이 낮은 노드 우선 방문
- 같은 level일때, 부모 노드의 방문 순서에 따라 왼쪽 자식 노드부터 방문
→ 한 노드를 방문했을 때, 나중에 방문할 노드들을 순서대로 기록해야 함 => 큐 이용
class ArrayQueue:
def __init__(self):
self.data = []
def size(self):
return len(self.data)
def isEmpty(self):
return self.size() == 0
def enqueue(self):
self.data.append(item)
def dequeue(self):
return self.data.pop(0)
def peek(self):
return self.data[0]
class Node:
def __init__(self,item):
self.data = item
self.left = None
self.right = None
class BinaryTree:
def __init__(self,r):
self.root = r
def bft(self):
visitQueue = ArrayQueue()
traversal = []
if self.root: # 빈 트리가 아닐 때
visitQueue/enqueue(self.root)
while visitQueue.isEmpty() == False: # 큐가 비어있지 않을 때
node = visitQueue.dequeue()
traversal.append(node.data)
if node.left:
visitQueue.enqueue(node.left)
if node.right:
visitQueue.enqueue(node.right)
return traversal특수한 이진트리
- 포화 이진 트리 Full Binary Tree
모든 레벨에서 노드들이 모두 채워져 있는 이진트리
- 높이가 k이고 노드의 개수가 2^k - 1인 이진트리 - 완전 이진 트리 Complete Binary Tree
높이가 k인 완전 이진트리에서
레벨 k-2까지는 모든 노드가 2개의 자식을 가진 포화 이진트리
레벨 k-1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진트리
이진 탐색 트리 Binary Search Trees
(중복되는 데이터가 없다고 가정했을때)left subtree의 모든 값이 root node의 값보다 작고 right subtree의 모든 값이 root node의 값보다 큰 이진트리
- 배열을 이용한 이진트리와 비교했을 때 원소의 추가와 삭제가 용이하다는 장점이 있지만, 공산 소요가 크다는 단점이 있음
연산
- insert(key,data) : 원소 추가
- remove(key) : 원소 삭제
- lookup(key) : 원소 검색
- inorder() : key의 순서대로 나열
- min(), max() : 최소 key, 최대 key를 가지는 원소 탐색
구현
- 초기화
class Node:
def __init__(self,key,data):
self.key = key
self.data = data
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None- in-order traversal
class Node:
def inorder(self):
traversal = []
if self.left:
traversal += self.left.inorder()
traversal.append(self)
if self.right:
traversal += self.right.inorder()
return traversal
class BinarySearchTrer:
def inorder(self):
if self.root:
return self.root.inorder()
else:
return []- min()
class Node:
def min(self):
if self.left:
return self.left.min()
else:
return self
class BinarySearchTree:
def min(self):
if self.root:
return self.root.min()
else:
return None- max()
class Node:
def max(self):
if self.right:
return self.right.max()
else:
return self
class BinarySearchTree:
def max(self):
if self.root:
return self.root.max()
else:
return None- lookup()
입력 인자 : 찾으려는 대상 key
리턴 : 찾은 노드와 그것의 부모 노드(각각 없으면 None)
class Node:
def lookup(self,key,parent=None):
if key < self.key:
if self.left:
return self.left.lookup(key,self)
else:
return None, None
elif key > self.key:
if self.rignt:
return self.right.lookup(key,self)
else:
return None, None
else:
return self, parent
class BinarySearchTree:
def lookup(self,key):
if self.root:
return self.root.lookup(key)
else:
return None, None- insert()
입력 인자 : 키, 데이터 원소
리턴 : 없음
class Node:
def insert(self,key,data):
if key < self.key:
if self.key is key:
raise KeyError
if key < self.key:
if self.left:
self.left.insert(key, data)
else:
self.left = Node(key, data)
else:
if self.right:
self.right.insert(key, data)
else:
self.right = Node(key, data)
class BinarySearchTree:
def insert(self,key,data):
if self.root:
self.root.insert(key,data)
else:
self.root = Node(key,data)