04-1 트리란?
트리(tree)
나무를 닮은 자료 구조
→ 계층적인 관계를 가진 자료의 표현에 유용하게 사용됨
트리 관련 용어
트리에서 각각의 요소들을 노드(node)라고 부름
트리는 하나 이상의 노드들로 이루어짐
노드와 노드의 연결 관계는 간선 또는 에지(edge)로 나타냄
계층적인 구조에서 가장 높은 곳에 있는 노드를 루트(root) 노드라고 부름
| 부모(parent) 노드 | 간선으로 직접 연결된 노드 중에 상위 노드 |
| 자식(child) 노드 | 간선으로 직접 연결된 노드 중에 하위 노드 |
| 형제(sibling) 노드 | 같은 부모 노드를 가진 노드 |
| 조상(ancestor) 노드 | 어떤 노드에서 루트 노드까지의 경로상에 있는 모든 노드 |
| 자손(descendent) 노드 | 어떤 노드 하위에 연결된 모든 노드 |
| 단말(terminal, leaf) 노드 | 자식 노드가 없는 노드, 자식이 있으면 비단말 노드 |
| 노드의 차수(degree) | 노드가 가지고 있는 자식의 수, 단말 노드는 항상 0 |
| 트리의 차수 | 트리에 포함된 모든 노드의 차수 중에서 가장 큰 수 |
| 레벨(level) | 트리의 각층에 번호를 매기는 것, 루트 노드의 레벨은 1이고 한 층씩 내려갈수록 레벨은 1씩 증가 |
| 트리의 높이(height) | 트리가 가지고 있는 최대 레벨 |
트리의 모든 노드는 자신을 루트로 하는 하나의 서브 트리를 대표
트리의 표현 방법
- 트리는 중첩된 집합 으로 나타낼 수 있음
- 트리의 루트와 서브 트리를 중첩된 괄호로 묶어 표현
ex) A: 루트 / B, C, D: A의 자식 노드 ⇒ (A (B…)(C…)(D…))
트리를 하나의 문자열처럼 표현할 수 있으나, 직관적으로 구조를 이해하기에 어려움 - 트리는 들여쓰기(identation) 으로 나타낼 수 있음
자료가 계층적 구조를 갖는 것을 나타냄
일반 트리의 표현
일반 트리(general tree): 자식의 개수에 제한이 없는 트리
N-링크 표현
차수가 N인 노드가 N개의 링크를 갖도록 허용 (하나의 데이터 필드와 자식 노드 개수만큼의 링크를 가짐)
노드마다 링크의 개수가 다르다는 문제 → 트리의 표현과 관리가 복잡
왼쪽 자식-오른쪽 형제 표현
노드가 두 개의 링크만을 갖도록 함
하나의 링크는 왼쪽 자식(첫번째 자식, child)를 가리킥, 다른 하나는 오른쪽 형제(다음 형제, sibling)을 가리킴
→ 루트에서 가장 오른쪽 자식의 오른쪽 자식 노드 ... 를 찾아가는 과정에서 맣은 노드를 거쳐야 함
04-2 이진 트리
이진 트리(binary tree): 모든 노드가 최대 2개의 자식만을 가질 수 있는 트리
자식 사이에도 순서 존재. 왼쪽 자식과 오른쪽 자식은 반드시 구별되어야 함
이진 트리의 종류
포화 이진 트리(full binary tree)
: 트리의 각 레벨에 노드가 꽉 차있는 이진 트리
높이가 k인 포화 이진 트리의 노드의 수
전체 노드 개수: 2^k - 1
포화 이진 트리는 각 노드에 순서대로 번호를 붙일 수 있음
위에서 아래로 내려오면서 왼쪽에서 오른쪽 순서대로 번호를 붙임
루트 노드의 번호는 항상 1
완전 이진 트리(complete binary tree)
: 높이가 k인 트리에서 레벨 1부터 k-1까지는 노드가 모두 채워져있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진 트리
마지막 레벨에서는 노드가 꽉 차 있지 않아도 되지만 중간에 빈 곳이 있으면 안됨
균형 이진 트리(balanced binary tree)
: 균형 이진 트리 또는 높이균형 이진 트리(height-balanced binary tree)는 모든 노드에서 좌우 서브 트리의 높이 차이가 1이하인 트리
균형 이진 트리가 아닌 트리를 경사 트리 또는 경사 이진 트리라고 함
이진 트리의 표현 방법
배열 구조와 연결된 구조로 표현 가능
배열 구조 표현
포화 이진 트리에서 노드에 번호를 붙이는 것을 그대로 배열의 인덱스로 사용
- 트리의 높이를 구해 배열(또는 파이썬의 리스트)을 할당
높이가 k이면 길이가 2^k-1인 배열 필요 - 포화 이진 트리의 번호를 인덱스로 사용하여 배열에 노드들을 저장
포화 이진 트리나 완전 이진 트리에 가장 적합
심한 경사 트리의 경우 배열 항목 사이에 사용하지 않는 빈칸이 많아 메모리의 낭비가 심할 수 있음
어떤 노드의 인덱스를 알면 부모 노드, 자식 노드의 인덱스를 쉽계 계산 가능
- 노드 i의 부모 노드 인덱스 = i / 2
- 노드 i의 왼쪽 자식 노드 인덱스 = 2i
- 노드 i의 오른쪽 자식 노드 인덱스 = 2i + 1
연결된 구조 표현: 링크 표현법
각 노드는 두 개의 링크 필요, 각각 왼쪽(left)과 오른쪽(right) 자식 노드를 가리킴
좌우 링크는 반드시 구별되어야 함
이진 트리를 위한 노드 클래스
class BTNode:
def __init__ (self, elem, left=None, right=None):
self.data = elem
self.left = left # 왼쪽 자식을 위한 링크
self.right = right # 오른쪽 자식을 위한 링크
04-3 이진 트리의 연산
이진 트리는 루트와 두 개의 서브 트리로 이루어지고, 서브 트리도 모두 이진 트리여야 한다는 순환조건이 있음
이러한 순환적인 특징에 의해 이진 트리의 연산에는 순환 알고리즘이 흔히 사용됨
이진 트리의 표준순회
트리를 순회(traversal): 트리의 모든 노드를 한 번씩 방문
선형 자료구조에서는 항목들이 일렬로 저장되어 있어 순회가 매우 단순한 반면, 트리에서는 자료가 일렬로 나열되어 있지 않기 때문에 순회 방법이 다양
순회 방법은 루트(V), 왼쪽 서브 트리(L), 오른쪽 서브 트리(R)를 각각 어떤 순서로 방문하느냐에 따라 구분됨
- 전위순회(preorder traversal): VLR
- 중위순회(inorder traversal): LVR
- 후위순회(postorder traversal): LRV
서브 트리의 방문 작업 L과 R을 처리하는 데도 동일한 순회 방법이 적용되어야 함
트리에서는 전체 트리나 서브 트리나 기본 구조가 완전히 같으므로 전체 트리에서 사용된 알고리즘을 서브 트리에도 똑같이 적용할 수 있음 → 순환 기법(재귀 호출)이 흔히 사용됨
전위순회(preorder)
(1) 루트 먼저 방문 (V)
(2) 왼쪽 서브 트리 방문(L)
(3) 오른쪽 서브 트리 방문(R)
루트 노드를 처리한 후 루트의 왼쪽 서브 트리에 대해서도 똑같이 VLR 순으로 같은 순회 방법 적용, 오른쪽 서브 트리도 같은 방법으로 방문
→ 순환호출 이용
이진 트리의 전위순회
# 전위순회 함수
def preorder(n):
if n is not None:
print(n.data, end=' ')
preorder(n.left) # 왼쪽 서브 트리 처리
preorder(n.right) # 오른쪽 서브 트리 처리
중위순회(inorder)
(1) 왼쪽 서브 트리 방문(L)
(2) 루트 방문 (V)
(3) 오른쪽 서브 트리 방문(R)
루트를 처리하기 전에 왼쪽 서브 트리 먼저 처리, 왼쪽 서브 트리의 노드 먼저 처리하기 전에 다시 왼쪽으로 내려가야 함
이진 트리의 중위순회
# 중위순회 함수
def inorder(n):
if n is not None:
inorder(n.left) # 왼쪽 서브 트리 처리
print(n.data, end=' ')
inorder(n.right) # 오른쪽 서브 트리 처리
후위순회(postorder)
(1) 왼쪽 서브 트리 방문(L)
(2) 오른쪽 서브 트리 방문(R)
(3) 루트 방문 (V)
이진 트리의 후위순회
# 후위순회 함수
def postorder(n):
if n is not None:
postorder(n.left)
postorder(n.right)
print(n.data, end=' ')
순회 방법의 선택
- 순서는 중요하지 않고 노드를 전부 방문하기만 하면 되는 경우
→ 어떤 방법도 상관 X - 자식을 머리 처리해야 부모를 처리할 수 있는 경우
→ 후위순회 - 부모가 처리되어야 자식을 처리할 수 있는 경우
→ 전위순회
레벨 순회
레벨 순회(level order): 레벨 순으로 노드를 방문
위에서 아래로, 같은 레벨에서는 왼쪽에서 오른쪽으로 방문
큐를 이용하여 구현 가능
큐에 노드를 넣고 빼는 과정을 반복
- 공백 상태의 큐에 루트를 넣음
- 큐에서 노드 하나를 꺼내 방문하고 그 노드의 자식들을 큐에 삽입하는 과정을 반복
- 삽입할 때는 왼쪽 자식을 먼저 넣고 오른쪽 자식을 다음에 넣음
- 자식이 없는 경우, 삽입하지 않음
- 위의 과정을 큐가 공백 상태가 될 때까지 반복
큐에서 노드가 나오는 순서가 방문 순서
이진 트리의 레벨 순회
# 이진 트리의 레벨 순회
def levelorder(root) :
queue = ArrayQueue() # 큐 객체 초기화
queue.enqueue(root) # 최초에 루트 노드만 들어있음.
while not queue.isEmpty(): # 큐가 공백 상태가 아닌 동안,
n = queue.dequeue()
if n is not None:
print(n.data, end=' ')
queue.enqueue(n.left)
queue.enqueue(n.right)
이진 트리의 연산들
전체 노드의 수 구하기
이진 트리의 노드 개수는 왼쪽 서브 트리의 노드 수와 오른쪽 서브 트리의 노드 수의 합에 1(루트 노드)을 더한 값
이진 트리의 노드 수 구하기
# 이진 트리의 노드 수 구하기
def count_node(n):
if n is None: # n이 None이면 공백 트리 --> 0을 반환
return 0
else: # 좌우 서브 트리의 노드 수의 합 + 1 (순환이용)
return count_node(n.left) + count_node(n.right) + 1
트리의 높이 구하기
이진 트리의 높이는 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 중에서 큰 값에 1을 더한 값
이진 트리의 높이 구하기
# 이진 트리의 높이 구하기
def calc_height(n):
if n is None: # 공백 트리 --> 0을 반환환
return 0
hLeft = calc_height(n.left) # hLeft <- L의 높이
hRight = calc_height(n.right) # hRight <- R의 높이
if (hLeft > hRight): # 더 큰 값에 1을 더해 반환
return hLeft + 1
else: return hRight + 1
테스트 프로그램
이진 트리 연산의 테스트 프로그램
# 이진 트리 연산의 테스트 프로그램
d = BTNode('D', None, None)
e = BTNode('E', None, None)
b = BTNode('B', d, e)
f = BTNode('F', None, None)
c = BTNode('C', f, None)
root = BTNode('A', b, c)
print('\n In-Order : ', end=' '); inorder(root)
print('\n Pre-Order : ', end=' '); preorder(root)
print('\n Post-Order : ', end=' '); postorder(root)
print('\n Level-Order : ', end=' '); levelorder(root)
print()
print(" 노드의 개수 = %d개" % count_node(root))
print(" 트리의 높이 = %d" % calc_height(root))
실행 결과
04-4 모스 코드 결정 트리
모스 코드(Morse Code): 도트(점)와 대시(선)의 조합으로 구성된 메시지 전달용 부호
영어 대문자에 대한 모스 코드 표
문자를 모스 코드로 변환하는 과정: 인코딩
문자를 모스 코드로 변환하는 것 → 부호화, 인코딩(encoding)
영어 대문자에 대한 모스 코드 표
table=[('A','.-'), ('B','-...'), ('C','-.-.'), ('D','-..'),
('E','.'),('F','..-.'),('G','--.'),('H','....'),
('I','..'),('J','.---'),('K','-.-'),('L','.-..'),
('M','--'),('N','-.'),('O','---'),('P','.--.'),
('Q','--.-'),('R','.-.'),('S','...'),('T','-'),
('U','..-'),('V','...-'),('W','.--'),('X','-..-'),
('Y','-.--'),('Z','--..')]
모스 코드 인코딩 함수
def encode(ch):
idx = ord(ch)-ord('A') # 리스트에서 해당 문자의 인덱스
return table[idx][1] # 해당 문자의 모스 부호 반환ord()는 파이썬 내장 함수로 문자를 아스키 코드값으로 바꿔줌
문자 ch의 아스키 코드값과 'A'의 코드값의 차이가 문자 ch의 위치에 해당
모스 코드를 문자로 변환하는 과정: 디코딩
모스 코드가 주어졌을 때 해당하는 알파벳을 추출 → 복호화, 디코딩(decoding)
표에서 찾고자 하는 모스코드에 대한 알파벳을 찾을 때 디코딩의 경우 인코딩과는 달리 모스 코드가 주어졌을 때 위치를 바로 계산할 수 없음
표의 모든 항목을 하나씩 조사하여 일치하는 모스 코드가 있는지를 검사해야 함
단순한 방법의 모스 코드 디코딩 함수
# 단순한 방법의 모스 코드 디코딩 함수
def decode_simple(morse):
for tp in table: # 모스 코드 표의 모든 문자에 대해
if morse == tp[1]: # 찾는 코드와 같으면
return tp[0] # 그 코드의 문자를 반환운이 나쁠 시 표의 모든 항복을 뒤져봐야 함 → 표의 크기(문자 수)가 n개라면 n번 비교해야 함
결정 트리를 이용한 모스 코드의 디코딩
결정 트리(decision tree): 여러 단계의 복잡한 조건을 갖는 문제에 대해 조건과 그에 따른 해결방법을 트리 형태로 나타낸 것
→ 효율적인 디코딩 가능
결정 트리 이용
- 루트를 제외한 모든 노드는 하나의 알파벳을 나타냄
- 루트에서 시작하여 코드에 점(.)이 나타나면 왼쪽 자식으로 움직임
- 코드에 선(-)이 나타나면 오른쪽 자식으로 움직임
- 위의 과정을 코드 전체에 대해 수행하면 해당 코드의 알파벳 노드에 도착
모스 코드 결정 트리 만들기
- 빈 루트 노드를 만들고 모스 코드표의 각 문자를 하나씩 트리에 추가
- 문자를 추가할 때 루트부터 시작하여 트리를 타고 내려감
타고 내려갈 때 자식 노드가 None이면 새로운 노드를 추가 (추가만 할 뿐 그 노드의 문자는 아직 결정X) - 마지막 코드의 노드에 도달하면 그 노드에 문자를 할당
모스 코드 디코딩을 위한 결정 트리 만들기
def make_morse_tree():
root = BTNode(None, None, None)
for tp in table: # tp: 모스 코드 표의 각 항목
code = tp[1] # tp[1]: 모스 코드
node = root # 루트부터 탐색
for c in code:
if c == '.': # 점(.)이면 왼쪽으로 이동
if node.left == None:
node.left = BTNode(None, None, None)
node = node.left
elif c == '-': # 선(-)이면 오른쪽으로 이동
if node.right == None:
node.right = BTNode(None, None, None)
node = node.right
node.data = tp[0] # 최종 노드에 문자(tp[0]) 부여
return root
결정 트리를 이용한 디코딩
def decode(root, code):
node = root # 루트 노드에서 시작
for c in code: # 각 부호에 대해
if c == '.' : node = node.left # 점(.): 왼쪽으로 이동
elif c == '-' : node = node.right # 선(-): 오른쪽으로 이동
return node.data # 문자 반환어떤 코드도 트리의 높이보다 많은 노드를 이동하지 않음
→ 결정 트리가 n개의 노드를 갖는 포화 이진 트리라면 높이가 log2(n)
→ log2(n)에 비례하는 비교 필요
테스트 프로그램
문자열을 입력받아 모스 코드로 바꾸고, 이 코드를 다시 문자열로 복구하는 테스트 프로그램
인코딩과 디코딩 테스트 프로그램
morseCodeTree = make_morse_tree()
str = input("입력 문장 : ")
mlist = []
for ch in str:
code = encode(ch)
mlist.append(code)
print("Morse Code: ", mlist)
print("Decoding: ", end='')
for code in mlist:
ch = decode(morseCodeTree, code)
print(ch, end='')
print()
실행 결과
04-5 수식 트리
수식 트리(Expression Tree): 산술식을 트리 형태로 표현한 이진 트리
수식 트리은 하나의 연산자가 두 개의 피연산자를 갖는다고 가정
피연산자는 단말노드에, 연산자는 루트나 가지노드에 배치
연산자인 비단말 노드는 두 개의 피연산자를 가져야 하므로 반드시 양쪽 자식을 모두 가짐
자식 노드인 피연산자가 숫자(number)일 수도 있지만, 또 다른 식일 수도 있음
수식 트리의 계산
어떤 연산자를 계산하려면 자식 노드의 계산이 반드시 끝나있어야 함
→ 수식 트리의 계산에는 후위순회가 사용됨
수식 트리 게산 함수
def evaluate(node):
if node is None: # 공백 트리이면 0 반환
return 0
elif node.isLeaf(): # 단말 노드이면 -> 피연산자
return node.data # 그 노드의 값(데이터) 반환
else: # 루트나 가지노드라면 -> 연산자자
op1 = evaluate(node.left)
op2 = evaluate(node.right)
if node.data == '+' : return op1 + op2
elif node.data == '-' : return op1 - op2
elif node.data == '*' : return op1 * op2
elif node.data == '/' : return op1 / op2
수식의 표현 방법
연산자와 피연산자의 상대적인 위치에 따라 방법을 구분
| 전위(prefix) | 중위(infix) | 후위(postfix) |
| 연산자 피연산자1 피연산자2 | 피연산자1 연산자 피연산자2 | 피연산자1 피연산자2 연산자 |
| + A B | A + B | A B + |
| + 5 * A B | 5 + A * B | 5 A B * + |
전위표기법은 연산자를 먼저 작고 좌우 피연산자를 이어서 적는 방법
중위, 후위 표기법은 연산자를 중간, 마지막에 적는 방법
중위 표기의 경우 사람들에게는 익숙하지만 컴퓨터 입장에서는 처리가 번거로움
후위 표기의 장점
- 괄호를 사용하지 않아도 계산 순서를 알 수 있음
- 연산자의 우선순위를 생각할 필요가 없음
- 수식을 읽으면서 바로 계산할 수 있음
→ 컴퓨터는 수식의 처리를 위해 후위표기 이용
사람들은 중위표기에 익숙하기에 컴퓨터의 계산기 프로그램들은 사용자로부터 중위표기 수식을 입력받고, 후위표기 수식으로 변환한 후, 식을 계산
수식 트리 만들기
전위표기 식으로 수식 트리 만들기
전위표기 수식은 맨 앞에서 뒤로 읽으면서 처리
입력 수식: * + 1 3 / 4 2
- * 첫 항목(*)은 수식 트리의 루트 노드가 됨
- + 이전 항목(*)이 연산자이므로 +는 *의 왼쪽 자식이 됨
- 1 이전 항목(+)이 다시 연산자이므로 1은 +의 왼쪽 자식이 됨
- 3 이전 항목(1)이 피연산자(첫번쨰)이므로 3은 이전 연산자 +의 두 번째 피연산자가 됨
두 번째 피연산자가 처리됐으므로 +를 루트로 하는 서브 트리 완성됨 - / 이제 /는 이전 연산자 *의 오른쪽 자식이 됨
- 4 이전 연산자의 왼쪽 자식이 됨
- 2 이전 연산자의 오른쪽 자식이 됨
후위표기 식으로 수식 트리 만들기
후위표기 수식은 맨 뒤에서 앞으로 읽으면서 처리
입력 수식: 1 3 + 4 2 / *
- * 끝 항목(*)은 수식 트리의 루트 노드가 됨
- / 이전 항목(*)이 연산자이므로 /는 *의 오른쪽 자식이 됨
- 2 이전 항목(/)이 다시 연산자이므로 2는 /의 오른쪽 자식이 됨
- 4 이전 항목(2)이 피연산자(두 번째)이므로 4는 이전 연산자의 /의 첫 번째 피연산자가 됨
피연산자들이 모두 처리되었으므로 /를 루트로 하는 서브 트리 완성됨 - + 이제 +는 이전 연산자 *의 왼쪽 자식이 됨
- 3 3은 이전 연산자의 오른쪽 자식이 됨
- 1 1은 이전 연산자의 왼쪽 자식이 됨
후위표기 수식을 이용한 수식 트리 만들기
def buildTree(expr):
if len(expr) == 0:
return None
token = expr.pop()
if token in "+-*/":
node = BTNode(token)
node.right = buildTree(expr)
node.left = buildTree(expr)
return node
else:
return BTNode(float(token))
테스트 프로그램
수식 트리 테스트 프로그램
str = input("입력(후위표기): ") # 후위표기식 입력
expr = str.split() # 토큰 리스트로 변환
print("토큰분리(expr): ", expr)
root = buildTree(expr)
print('\n 전위순회: ', end=''); preorder(root)
print('\n 중위순회: ', end=''); inorder(root)
print('\n 후위순회: ', end=''); postorder(root)
print('\n 계산 결과 : ', evaluate(root)) # 수식 트리 계산
실행 결과
'ECC - 알고리즘 > 자료구조와 알고리즘 with 파이썬' 카테고리의 다른 글
| Chapter07. 탐색 (0) | 2025.05.08 |
|---|---|
| Chapter06. 정렬 (0) | 2025.05.03 |
| Chapter 03. 리스트 (0) | 2025.03.26 |
| Chapter 02. 큐 (0) | 2025.03.21 |
| Chapter 01. 스택 (0) | 2025.03.19 |