15. 트리(Tree)#
지금까지 리스트, 큐, 스택 등 선형 자료구조만 살펴보았다. 여기서는 트리(tree)라는 비선형 자료구조의 정의와 주요 활용예제를 살펴본다.
15.1. 트리 활용 예제#
생물 분류 트리
18세기 스웨덴 생물학자 린네(Linne)가 고안한 생물 분류 트리는 다음과 같다.
계(Kingdom)
문(Phylum)
강(Class)
족(Cohort)
목(Order)
과(Family)
류(Tribe)
속(Genus)
종(Species)
파일 시스템
루트(/)부터 임의의 폴더까지 유일한 경로(path)가 존재한다.
웹페이지 소스코드
웹 브라우저는 HTML 프로그래밍언어로 작성된 웹페이지 소스코드의 태그(tag) 트리로부터 웹페이지 구성에 대한 정보를 읽어낸다.
HTML 소스코드
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type"
content="text/html; charset=utf-8" />
<title>simple</title>
</head>
<body>
<h1>A simple web page</h1>
<ul>
<li>List item one</li>
<li>List item two</li>
</ul>
<h2><a href="https://www.cs.luther.edu">Luther CS </a><h2>
</body>
</html>
태그 트리: 위 소스코드에 사용된 태그들은 다음, 같다.
<html>,</html><head>,</head><meta/><title>,</title><body>,</body><ul>,</ul><li>,</li><h1>,</hw><a>,</a>
15.2. 트리 구성 요소#
트리 구성요소와 트리 관련 주요 개념은 다음과 같다.
마디(Node)
트리의 주요 구성요소이다. 이름을 가질 수 있으며, 경우에 따라 값(value)이라는 정보도 추가적으로 가질 수 있다.
이음선(Edge)
트리의 또 다른 주요 구성요소이며, 두 개의 마디를 연결하여 부모-자식 관계를 보여준다. 연결된 마디를 기준으로 진입 이음선(incoming edge) 또는 진출 이음선(outgoing edge)으로 나뉜다. 진입과 진출의 기준은 루트이며, 루트 쪽에서 오는 이음선을 진입 이음선, 루트와 멀어지는 이음선을 진출 이음선이라 한다. 루트(root)를 제외한 모든 마디는 진입 이음선를 갖는다. 또한 모든 마디는 0개 이상 임의의 수만큼 진출 이음선를 가질 수 있다.
루트(Root)
트리에 포함된 마디 중에서 진입 이음선을 갖지 않는 유일한 마디를 가리킨다.
경로(Path)
두 마디를 잇는 여러 개의 이음선으로 이루어진 리스트이다. 예를 들어, 아래 경로는 생물 분류 트리의 경로이다.
자식(Children)
하나의 마디와 진입 이음선으로 연결된 마디를 가리킨다.
부모(Parent)
자식 마디를 갖는 마디이다.
형제자매(Sibling)
부모를 공유하는 마디들이다.
자손(descendant)
하나의 부모에서 출발하여 자식관계로 연결된 마디를 가리킨다.
서브트리(Subtree)
임의의 마디를 루트로 하면서 해당 마디의 모든 자손으로 이루어진 트리이다.
잎(Leaf Node)
자식이 없는 마디이다. 즉, 진출 이음선을 갖지 않는다.
레벨(Level)
마디의 레벨은 루트로부터 연결된 이음선의 개수이다. 루트의 레벨은 따라서 0이다.
높이(Height)
트리에 포함된 마디의 레벨 중에서 최댓값이다. 앞서 예제로 사용된 파일 시스템 트리의 경우 높이는 2이며, HTML 소스코드의 태크 트리의 높이는 3이다.
15.2.1. 트리의 정의#
(루트 지정) 트리rooted tree는 아래 성질을 만족하는 마디와 이음선들로 이루진다.
루트로 사용되는 하나의 마디가 있다.
루트를 제외한 모든 마디는 부모 마디로부터 오는 진입 이음선으로 연결된다.
루트로부터 임의의 노트로 연결되는 경로가 유일하게 존재한다.
이진트리(binary tree)
모든 마디가 최대 2 개의 자식을 갖는 트리이다.
트리의 제귀적 정의
트리는 그 자체로 비어있거나 또는 하나의 루트에 연결된 (0 개 이상의) 서브트리로 구성된다. 각 서브트리의 루트는 부모 트리의 루트에 자식 마디로 연결된다. 앞으로 트리를 구현할 때 재귀적 정의를 활용한다.
15.3. 이진 트리 구현#
15.3.1. 중첩 리스트 활용#
다음 이진 트리를 중첩 리스트를 이용하여 구현할 수 있다.
my_tree = [
"a", # 루트
["b", # 왼쪽 서브트리
["d", [], []],
["e", [], []]
],
["c", # 오른쪽 서브트리
["f", [], []],
[]
]
]
중첩 리스트를 활용하여 임의의 트리를 생성하고 활용하는 함수들을 구현할 수 있다. 자세한 내용은 Problem Solving with Algorithms and Data Structures using Python, 7.4절을 참조하면 된다.
15.3.2. 클래스 활용#
클래스를 이용하여 아래 그림 형태의 이진 트리 자료구조를 구현한다.
여기서는 편의상 이진트리 자료구조를 구현한다. 클래스에 사용된 속성은 다음과 같다.
key: 마디 이름left_child: 왼쪽 서브트리(참조 활용)right_child: 오른쪽 서브트리(참조 활용)
이외에 왼쪽/오른쪽 서브트리를 추가 및 확인하고 루트의 이름을 지정 및 확인하는 메서드를 추가하면 최종적으로 아래 모양의 클래스를 선언한다.
class BinaryTree:
# 생성자
def __init__(self, root_obj, left_child=None, right_child=None):
self.key = root_obj
self.left_child = left_child
self.right_child = right_child
# 왼쪽 서브트리 추가
def insert_left(self, new_node):
if self.left_child is None:
self.left_child = BinaryTree(new_node)
else:
new_left_child = BinaryTree(new_node, self.left_child, None)
self.left_child = new_left_child
# 오른쪽 서브트리 추가
def insert_right(self, new_node):
if self.right_child == None:
self.right_child = BinaryTree(new_node)
else:
new_right_child = BinaryTree(new_node, None, self.right_child)
self.right_child = new_right_child
# 루트 이름 확인
def get_root_val(self):
return self.key
# 루트 이름 지정
def set_root_val(self, new_obj):
self.key = new_obj
# 왼쪽 서브트리 확인
def get_left_child(self):
return self.left_child
# 오른쪽 서브트리 확인
def get_right_child(self):
return self.right_child
15.3.2.1. 탑다운 방식과 바텀업 방식#
(이진)트리를 구성하기 위해 두 가지 방식을 활용할 수 있다.
탑다운(top-down) 방식: 루트에서 출발하여 자식 마디 추가 반복
insert_left()와insert_right()함수 활용
바텀업(bottom-up) 방식: (최대 두 개의) 자식 트리와 루트 마디를 이용하여 새로운 (이진)트리 생성
BinaryTree클래스의 생성자(__init__()메서드)가 루트 마디, 자식 트리를 인자로 받음.
예제
아래 모양의 트리를 구현해보자.
example_tree1 = BinaryTree("b")
example_tree1.insert_right("d")
example_tree2 = BinaryTree("c")
example_tree2.insert_left("e")
example_tree2.insert_right("f")
example_tree = BinaryTree("a", example_tree1, example_tree2)
아래 코드를 실행할 때 오류가 발생하지 않으면 제대로 구현된 것이다.
assert (example_tree.get_right_child().get_root_val() == "c")
assert (example_tree.get_left_child().get_right_child().get_root_val() == "d")
assert (example_tree.get_right_child().get_left_child().get_root_val() == "e")
15.4. 파스 트리#
파스 트리(parse tree) 또는 파싱 트리(parsing tree)는 문장이나 수식을 이진 트리로 구현한 것을 가리킨다. 예를 들어 \(((7 + 3) * (5 - 2))\)의 파스 트리는 다음과 같다.
여기서는 정수와 사칙연산으로 이루어진 수식의 파스 트리를 BinaryTree 클래스의 객체로 구현한 후에
수식 계산을 진행하고, 주어진 수식의 파스 트리로부터 수식을 복원하는 과정을 살펴본다.
즉, 아래 세 과정을 차례대로 구현한다.
수식으로부터 파스 트리 구현하기
수식의 파스 트리가 나타내는 값 계산하기
수식의 파스 트리로부터 수식 복원하기
15.4.1. 수식 파스 트리 구현#
먼저 수식을 파싱(parsing)하는 방법을 살펴본다. 전제 조건은 수식에 사용되는 모든 연산은 괄호로 감싸이도록 하는 것이다. 즉, 아래 예제에서처럼 연산자의 우선순위를 사용하는 대신에 괄호를 중첩으로 사용한다.
\((7 + 3) * (5 - 2) = ((7 + 3) * (5 - 2))\)
\(8 + 2 * 9 = (8 + (2 * 9))\)
따라서 정수와 사칙연산으로 이루어진 수식은 다음 네 종류의 기호로 구성된다.
여는 괄호:
"("닫는 괄호:
")"연산자:
"+","-","*","/"정수
여는 괄호는 새로운 수식이 시작됨을, 닫는 괄호는 하나의 수식이 완료됨을 의미한다. 그리고 연산자는 이진 트리의 마디로, 정수들은 해당 연산자의 자식으로 사용된다. 또한, 수식의 경우 자식은 항상 좌우 모두 존재한다.
이 정보에 따르면 수식에 사용된 토큰(token, 기호)을 왼쪽에서부터 읽어 나가면서 파스 트리를 생성할 때 다음 네 가지 규칙이 사용된다.
현재 토큰이 여는 괄호
"("인 경우 왼쪽 자식 마디를 추가한 후에 해당 마디로 이동한다.현재 토큰이 연산자 기호
["+", "-", "/", "*"]중에 하나인 경우 현재 위치의 마디의 키(key)를 해당 연산자 기호로 지정한다. 이후 오른쪽 자식 마디를 추가한 후에 해당 마디로 이동한다.현재 토큰이 정수인 경우, 현재 위치의 마디의 키(key)를 해당 정수로 지정한 후에 부모 마디로 이동한다.
현재 토큰이 닫는 괄호
")"인 경우 부모 마디로 이동한다.
예제
\((3 + (4 * 5))\)의 파스 트리를 생성하는 과정을 살펴본다. 이를 위해 수식의 토큰으로 이루어진 아래 리스트를 사용한다.
["(", "3", "+", "(", "4", "*", "5", ")", ")"]
키를 갖지 않는 하나의 마디로 시작한 후에 위 네 규칙을 적절하게 적용하여 파스 트리를 구현내 나간다.
구현
앞서 언급된 네 규칙을 알고리즘으로 구현하려면 현재 마디의 부모 마디를 기억해 두어야 한다. 부모 마디를 기억해 두기 위해 4장 1부에서 정의한 스택(stack)을 활용한다.
class Stack:
def __init__(self):
self._items = []
def __repr__(self):
return f"<{self._items}>"
def is_empty(self):
return not bool(self._items)
def push(self, item):
self._items.append(item)
def pop(self):
return self._items.pop()
def peek(self):
return self._items[-1]
def size(self):
return len(self._items)
자식 마디로 이동할 때마다 부모 노드를 스택에 저장하고, 다시 돌아오면 스택의 탑(top)을 삭제하면서 동시에 해당 부모 마디를 사용한다.
다음 build_parse_tree() 함수가 수식으로부터
방금 설명한 알고리즘을 이용하여 이진 트리를 생성한다.
함수에 사용된 변수들의 역할은 다음과 같다.
fp_expr: 모든 연산은 괄호로 감싸이고 모든 토큰은 공백으로 구분된 수식 문자열fp_list: 수식에 사용된 토큰(기호)들의 리스트. 공백 기준으로 쪼개짐.p_stack: 부모 마디를 루트로 갖는 서브트리들의 스택expr_tree: 생성되는 이진 트리. 계속 업데이트됨.current_tree: 현재 생성과정에 있는 서브트리insert_left(""): 왼쪽 자식 마디 생성. 아직 마디에 들어갈 값은 미정.insert_right(""): 오른쪽 자식 마디 생성. 아직 마디에 들어갈 값은 미정.
def build_parse_tree(fp_expr):
# 수식으로부터 토큰들의 리스트 생성
fp_list = fp_expr.split()
# 부모 마디를 루트로 갖는 서브트리들의 스택
p_stack = Stack()
# 생성 대상 이진트리. 하나의 비어 있는 마디로 시작.
expr_tree = BinaryTree("")
p_stack.push(expr_tree)
# 현재 토큰을 루트로 갖는 구현 대상 서브트리
current_tree = expr_tree
for i in fp_list:
# 토큰: 여는 괄호
if i == "(":
current_tree.insert_left("")
p_stack.push(current_tree)
current_tree = current_tree.left_child
# 토큰: 연산 기호
elif i in ["+", "-", "*", "/"]:
current_tree.key = i
current_tree.insert_right("")
p_stack.push(current_tree)
current_tree = current_tree.right_child
# 토큰: 닫는 괄호
elif i == ")":
current_tree = p_stack.pop()
# 토큰: 정수 및 기타
elif i not in ["+", "-", "*", "/", ")"]:
try:
current_tree.key = int(i)
parent = p_stack.pop()
current_tree = parent
# 정수가 아닌 경우 오류 발생시킴
except ValueError:
raise ValueError("token '{}' is not a valid integer".format(i))
return expr_tree
\((3 + (4 * 5))\)의 파스 트리는 다음과 같이 구현된다.
pt = build_parse_tree("( 3 + ( 4 * 5 ) )")
연습문제
아래 수식을 파스 트리로 만드는 과정을 추적하라.
15.4.2. 수식 파스 트리 해석#
파스 트리로 구현된 수식을 계산하는 수식 파스 트리 해석 함수는 다음과 같이 재귀를 이용하여 간단하게 구현할 수 있다.
import operator
def evaluate(parse_tree):
operators = {
"+": operator.add,
"-": operator.sub,
"*": operator.mul,
"/": operator.truediv,
}
# 재귀 적용 대상: 좌우 자식 서브트리
left_child = parse_tree.left_child
right_child = parse_tree.right_child
# 자식 서브트리 먼저 계산 후 연산자 적용. 왼쪽 먼저.
if left_child and right_child:
left_eval = evaluate(left_child)
right_eval = evaluate(right_child)
fn = operators[parse_tree.key]
return fn(left_eval, right_eval)
else:
return parse_tree.key
evaluate(pt)
23
실제로 다음이 성립한다.
참고: eval() 함수는 함수가 사용된 수식 문자열을 실제로 계산한다.
evaluate(pt) == eval("( 3 + ( 4 * 5 ) )")
True
15.4.3. 수식 복원#
수식의 파스 트리에서 수식을 복원하는 것 또한 재귀를 이용하여 간단하게 구현된다.
def print_exp(parse_tree):
result = ""
if parse_tree:
# 왼쪽 자식 서브트리 먼저 순회
result = "(" + print_exp(parse_tree.get_left_child())
# 연산자 기호 표시
result = result + str(parse_tree.get_root_val())
# 이어서 오른쪽 자식 서브트리 순회
result = result + print_exp(parse_tree.get_right_child()) + ")"
return result
print_exp(pt)
'((3)+((4)*(5)))'
정수를 괄호로 감싸지 않으려면 자식이 있는지 없는지 여부를 활용한다.
def print_exp(parse_tree):
result = ""
if parse_tree:
# 왼쪽 자식 서브트리 먼저 순회
if parse_tree.get_left_child():
result = "(" + print_exp(parse_tree.get_left_child())
else:
result = print_exp(parse_tree.get_left_child())
# 연산자 기호 표시
result = result + str(parse_tree.get_root_val())
# 이어서 오른쪽 자식 서브트리 먼저 순회
if parse_tree.get_right_child():
result = result + print_exp(parse_tree.get_right_child()) + ")"
else:
result = result + print_exp(parse_tree.get_right_child())
return result
print_exp(pt)
'(3+(4*5))'
15.5. 트리 순회#
트리 순회(tree traversal)는 트리의 마디를 모두 방문하는 과정이다. 트리 순회에 사용되는 전형적인 세 가지 재귀 방식은 다음과 같으며, 부모 마디의 방문 순서에 따라 재귀 알고리즘이 달라지며 왼쪽 자식 마디는 항상 오른쪽 자식 마디보다 먼저 방문된다.
전위순회(preorder traversal): 부모 마디, 왼쪽 자식 마디, 오른쪽 자식 마디 순의 재귀적 순회
중위순회(inorder traversal): 왼쪽 자식 마디, 부모 마디, 오른쪽 자식 마디 순의 재귀적 순회
후위순회(postorder traversal): 왼쪽 자식 마디, 오른쪽 자식 마디, 부모 마디 순의 재귀적 순회
예제: 전위순회
하스켈(Haskell) 프로그래밍언어 등의 소극적 계산(lazy evaluation)과
관련된 게산방식을 사용할 때 활용된다.
파이썬의 경우 and, or 등의 논리 연산자가 작동하는 방식과 유사하다.
이유는 기타 함수와는 달리 and와 or 논리 연산자는 모든 인자를 무조건
먼저 확인하지는 않기 때문이다.
False and (1/0 == 1)
False
True or (1/0 == 1)
True
반면에 아래와 같이 정의하면 모든 인자를 먼저 확인한다.
def and_op(x, y):
return x and y
try:
and_op(False, 1/0==1)
except:
print("둘째 인자에 문제가 있습니다.")
둘째 인자에 문제가 있습니다.
또 다른 예제는 클래스의 메서도를 호출할 때도 전위순회 방식을 사용한다. 이유는 호출되는 메서드가 해당 클래스에서 정의되었는가를 먼저 확인해야 하기 때문이다.
예제: 중위순회
중위 연산자(infix operator)를 이용한 수식 표현에 일반적으로 사용되는 방식이다.
예를 들어, print_exp() 함수가 사용하는 재귀는 파스 트리의 마디를
아래 우선 순위를 기준으로 재귀적으로 방문한다.
왼쪽 자식 마디
부모 마디
오른쪽 자식 마디
예제: 후위순회
수식이 계산되는 기본적인 방식이다.
예를 들어 evaluate() 함수가 사용하는 재귀는 파스 트리의 마디를
아래 우선 순위를 기준으로 재귀적으로 방문한다.
왼쪽 자식 마디
오른쪽 자식 마디
부모 마디
15.6. 프로그래밍 실습 과제#
두 문자 사이에 공백이 없는 수식 문자열에 대해서도
build_parse_tree()함수가 작동하도록 알고리즘을 수정하라.and,or,not을 사용하는 논리 표현식에 대해 작동하는build_parse_tree()함수와evaluate()함수를 구현하라.not연산자는 하나의 인자만 사용함에 주의하라.