순회 (Traversal) 란 트리 또는 그래프 같은 연결된 구조에서 객체 (노드) 를 방문하는 데 사용되는 알고리즘이다. 순회 문제는 모든 노드를 방문하는 방법을 찾거나 특정 노드만 방문하는 방법을 찾는 것일 수도 있다.
깊이 우선 탐색
깊이 우선 탐색 (depth-first search, DFS) 란 그래프 또는 트리에서 깊이를 우선하여 탐색하는 알고리즘이다. 그래프의 경우는 방문한 노드를 표시해야 하는데. 그렇게 하지 않는다면 무한 반복에 빠질 수 있기 때문이다. 시간 복잡도는 O(V+E) 이다. V는 도달할 수 있는 노드 수 (vertext), E는 도달한 노드에서 나가는 간선 수 (edge) 다. 깊이 우선 탐색은 후입선출 (LIFO) 구조의 스택을 사용하여 구현한다. 깊이 우선 탐색의 세 가지 경우를 알아보자.
전위 순회
전위 순회 (pre-order traversal) 는 루트 노드 -> 왼쪽 노드 -> 오른쪽 노드 순으로 방문한다. 아래 그림의 노드 위의 숫자가 방문한 순서다.
아주 간단하게 다음 코드로 구현할 수 있다.
def preorder(root):
if root != 0:
yield root.value
preorder(root.left)
preorder(root.right)
후위 순회
후위 순회 (post-order traversal) 는 왼쪽 노드 -> 오른쪽 노드 -> 루트 노드 순으로 방문한다.
def postorder(root):
if root != 0:
postorder(root.left)
postorder(root.right)
yield root.value
중위 순회
중위 순회 (in-order traversal) 는 왼쪽 노드 -> 루트 노드 -> 오른쪽 노드 순으로 방문한다.
def inorder(root):
if root != 0:
inorder(root.left)
yield root.value
inorder(root.right)
너비 우선 탐색
너비 우선 탐색 (breath-first search, BFS) 은 트리 또는 그래프에서 너비를 우선하여 탐색하는 알고리즘으로, 더 깊은 노드를 순회하기 전 특정 깊이의 노드를 모두 먼저 순회한다. 너비 우선 탐색을 사용하는 문제는 일반적으로 시작 노드에서 특정 노드에서 도달하는 데 필요한 최단 경로를 찾는 문제다. 너비 우선 탐색의 구현은 방문한 노드를 저장하는 데 리스트를 사용하며, 아직 방문하지 않은 노드는 선입선출 (FIFO) 구조의 큐에 저장한다. 시간 복잡도는 똑같이 O(V+E) 이다.
트리 순회 구현
깊이 우선 탐색과 너비 우선 탐색을 구현해보자.
아래 코드는 트리 순회를 반복문으로 구현한다.
from collections import deque
from binary_search_tree import BinarySearchTree, NodeBST
class BSTwithTransversalIterative(BinarySearchTree):
def inorder(self):
current = self.root
nodes, stack = [], []
while stack or current:
if current:
stack.append(current)
current = current.left
else:
current = stack.pop()
nodes.append(current.value)
current = current.right
return nodes
def preorder(self):
current = self.root
nodes, stack = [], []
while stack or current:
if current:
nodes.append(current.value)
stack.append(current)
current = current.left
else:
current = stack.pop()
current = current.right
return nodes
def preorder2(self):
nodes = []
stack = [self.root]
while stack:
current = stack.pop()
if current:
nodes.append(current.value)
stack.append(current.right)
stack.append(current.left)
return nodes
def BFT(self):
current = self.root
nodes = []
queue = deque()
queue.append(current)
while queue:
current = queue.popleft()
nodes.append(current.value)
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
return nodes
아래 코드는 재귀 함수를 사용하여 구현한다.
from binary_search_tree import BinarySearchTree, NodeBST
class BSTwithTransversalRecursive(BinarySearchTree):
def __init__(self):
self.root = None
self.nodes_BFS = []
self.nodes_pre = []
self.nodes_post = []
self.nodes_in = []
def BFT(self):
self.root.level = 1
queue = [self.root]
current_level = self.root.level
while len(queue) > 0:
current_node = queue.pop(0)
if current_node.level > current_level:
current_level += 1
self.nodes_BFS.append(current_node.value)
if current_node.left:
current_node.left.level = current_level + 1
queue.append(current_node.left)
if current_node.right:
current_node.right.level = current_level + 1
queue.append(current_node.right)
return self.nodes_BFS
def inorder(self, node=None, level=1):
if not node and level == 1:
node = self.root
if node:
self.inorder(node.left, level+1)
self.nodes_in.append(node.value)
self.inorder(node.right, level+1)
return self.nodes_in
def preorder(self, node=None, level=1):
if not node and level == 1:
node = self.root
if node:
self.nodes_pre.append(node.value)
self.preorder(node.left, level+1)
self.preorder(node.right, level+1)
return self.nodes_pre
def postorder(self, node=None, level=1):
if not node and level == 1:
node = self.root
if node:
self.postorder(node.left, level+1)
self.postorder(node.right, level+1)
self.nodes_post.append(node.value)
return self.nodes_post
연습문제
이진 검색 트리에서 두 노드의 최소 공통 조상 (lowest common ancestor) 을 찾아보자.
from transversal_BST_recursive import BSTwithTransversalRecursive
def find_common_ancestor(path, low_value, high_value):
while path:
current_value = path[0]
if current_value < low_value:
try:
path = path[2:]
except:
return current_value
elif current_value > high_value:
try:
path = path[1:]
except:
return current_value
elif low_value <= current_value <= high_value:
return current_value
bst = BSTwithTransversalRecursive()
l = [10, 5, 6, 3, 8, 2, 1, 11, 9, 4]
for i in l:
bst.add_node(i)
path = bst.preorder()
print("전위 순회: ", path)
print("1과 6의 최소 공통 조상: ", find_common_ancestor(path, 1, 6))
결과
PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/14. 순회/eg_transversal_BST_common_ancestor.py"
5
전위 순회: [10, 5, 3, 2, 1, 4, 6, 8, 9, 11]
1과 6의 최소 공통 조상: 5
출처
파이썬 자료구조와 알고리즘 - 한빛미디어, 미아 스타인
