트리(Tree)
Tree의 정의
Tree는 서로 연결된 Node의 계층형 자료구조로써, root 와 부모-자식 관계의 subtree로 구성되어 있습니다.
리스트가 단순히 순서를 매겨 데이터를 나열 하는 선형 자료구조였다면, 트리는 비선형적인 자료구조 입니다.
여기서 잠깐! 선형 자료구조란 하나의 자료 뒤에 하나의 자료가 존재하는 것을 말하며, 비선형 자료구조는 하나의 자료 뒤에 여러개의 자료가 존재하는 것을 말합니다.
트리는 root에서 시작하여 여러 개의 tree가 중첩되는 형태로 만들어집니다. 그렇기에 하나의 tree안에 여러 개의 subtree가 존재합니다.
Tree 관련 개념
기본적인 트리 관련 용어를 정리해보도록 하겠습니다.
•
정점 (Vertex): A,B,C와 같은 값을 갖고 나타내며, 노드로 표현됩니다.
•
간선 (Edge): 정점 간에 연결된 선입니다.
•
자식 노드 (Child), 부모 노드 (Parent)
•
형제 노드(sibling): 같은 부모를 가진 노드를 말합니다.
•
리프 노드 (Leef): 더 이상 뻗어나갈 수 없는 마지막 노드를 일컫습니다.
•
차수 (degree): 각 노드가 갖는 자식의 수. 모든 노드의 차수가 n개 이하인 트리를 n진 트리라고 합니다.
•
조상 (ancestor) 위쪽으로 간선을 따라가면 만나는 노드들 말합니다.
•
자손 (descendant): 아래쪽으로 간선을 따라가면 만나는 노드들을 말합니다.
•
루트 노드(Root): 트리의 시작 점 입니다.
•
높이 (height): 루트 노드에서 가장 멀리 있는 리프 노드 까지의 거리입니다.
•
레벨 (level): 루트 노드에서 떨어진 거리입니다.
트리 순회
선형 자료구조인 배열과 리스트의 경우, 순회하는 법이 인덱스 0,1,2부터 n-1까지로 방법이 하나로 정해져 있기 때문에, 순회하는 방법을 따로 배우지 않았습니다. for문을 이용해서 쉽게 순회할 수 있기 때문이죠. 하지만 트리는 비선형 자료구조이기에 순회하는 방법이 여러가지 존재합니다. 대표적인 방법들로 level order traversal, preorder traversal, inorder traversal, postorder traversal가 있습니다.
Level-order traversal
저희는 앞서서 level에 대해 정의 해보았습니다. level은 root 노드에서 떨어진 거리를 말합니다.
다음과 같이 root가 A인 tree가 있다고 합시다.
level 0 | A |
level 1 | B C D |
level 2 | E F G H I |
level 3 | J K L |
level order traversal은 말 그대로 level 별로 순회하는 것을 말합니다.
(A) →(B, C , D) → (E, F , G, H, I) → (J, K , L)
level order traversal 구현
level order traversal의 탐색 방법을 알았으니, 코드를 구현해 볼 차례입니다.
level order의 구현 코드는 아주 기본적인 템플릿으로, 추후에는 코드를 참고하지 않고도 직접 짤 수 있어야 합니다
from collections import deque
def levelOrder(root):
visited = []
if root is None:
return 0
q = deque()
q.append(root)
while q:
cur_node = q.popleft()
visited.append(cur_node.value)
if cur_node.left:
q.append(cur_node.left)
if cur_node.right:
q.append(cur_node.right)
return visited
Python
복사
Level order는 queue를 통해서 구현 됩니다. 아래와 같이 비어있는 queue와 visited를 생각해봅시다. visited에는 방문한 노드들의 값이 저장됩니다. 다음과 같은 트리가 주어졌을 때, 위의 코드가 어떤 식으로 구현 되는지 살펴보겠습니다.
queue |
visited |
queue에 루트인 A 노드가 들어갑니다. 그 후, while문을 통해 모든 노드를 탐색할 것입니다.
queue | A |
visited |
queue에 있는 A노드가 popleft되면, A 노드를 방문했다고 판단합니다.
queue | |
visited | A |
A 노드의 자식 노드가 존재함으로, queue에
B 노드와 C 노드를 넣어줍니다.
queue | B | C |
visited | A |
이렇게 하여 for문 한 바퀴를 돌았습니다.
위 과정들을 반복해보도록 합시다.
queue를 popleft하면 B 노드가 나타납니다. 방문한 B 노드를 visited에 저장해줍시다.
queue | C | |
visited | A | B |
B 노드의 자식 노드가 존재함으로, queue에
D 노드와 E 노드를 넣어줍니다.
queue | C | D | E | |
visited | A | B |
queue가 비어있지 않으므로, while문을 빠져나가지 못합니다.
queue를 popleft하면 C 노드가 나타납니다. 방문한 C 노드를 visited에 저장해줍시다.
queue | D | E | ||
visited | A | B | C |
C 노드의 오른쪽 자식 노드가 존재함으로, queue에 F 노드를 넣어줍니다.
queue | D | E | F | |
visited | A | B | C |
queue가 비어있지 않으므로, while문을 빠져나가지 못합니다.
queue를 popleft하면 D 노드가 나타납니다. 방문한 D 노드를 visited에 저장해줍시다.
queue | E | F | ||
visited | A | B | C | D |
D 노드는 리프 노드이기에, 자식노드가 존재하지 않습니다.
if 제어문에 걸리지 않고 넘어가주면 됩니다.
queue | E | F | |||
visited | A | B | C | D |
queue가 비어있지 않으므로, while문을 반복해줍니다.
queue를 popleft하면 E 노드가 나타납니다. 방문한 E 노드를 visited에 저장해줍시다.
E 노드는 리프 노드이기에, 자식노드가 존재하지 않습니다.
if 제어문에 걸리지 않고 넘어가주면 됩니다.
queue | F | |||||
visited | A | B | C | D | E |
queue가 비어있지 않으므로, while문을 반복해줍니다.
queue를 popleft하면 F 노드가 나타납니다. 방문한 F 노드를 visited에 저장해줍시다.
queue | ||||||
visited | A | B | C | D | E | F |
F 노드는 리프 노드이기에, 자식노드가 존재하지 않습니다.
if 제어문에 걸리지 않고 넘어가주면 됩니다.
queue | ||||||
visited | A | B | C | D | E | F |
이제 queue가 비어있으므로, while문을 빠져나온 후 visited를 return함으로써 level order traversal가 완료 됩니다.
queue를 사용함으로써, level order traversal를 구현해보았습니다. queue를 popleft하고 append함으로써 각 노드들을 방문하는 과정과 queue가 비게 되면, 완전 탐색이 끝난다는 것이 핵심입니다.
코딩 테스트에서는 위 과정들이 머리 속에서 그려지고, 코드들을 바로바로 짤 수 있어야 합니다.
Level order traversal 시간 복잡도
levelOrder의 시간복잡도는 어려울게 없습니다. 모든 정점의 개수가 n에 대해, popleft하고 append하는 과정이 n번 일어남으로 의 시간복잡도를 가집니다. 총 개의 node를 탐방해야함으로 의 시간복잡도를 가진다 생각해도 좋습니다.
전위순회, 중위순회, 후위순회
전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder)의 구현은 앞서 배운 level order traversal의 비해 상대적으로 쉽습니다.
그 전에 방문하다(visit)와 순회하다(traversal)에 대한 용어 정의가 필요합니다.
비슷하지만 약간의 뉘앙스가 다릅니다. 트리에서의 순회는 트리를 돌아 다니는 것이고, 트리에서의 방문은 노드의 값을 접근하는 것(출력, 저장 등의 행위)입니다.
우선 순회하는 것을 먼저 보도록 하겠습니다.
모든 트리는 기본적으로 다음과 같이 생겼습니다. 재귀적으로 정의 되어 있기 때문에 한 세트에서의 순회 과정을 정의하면 전체 트리를 순회 할 수 있습니다.
시작 노드에서 왼쪽 자식 노드, 다시 시작 노드를 거친 후 오른쪽 자식 노드를 찍고 마지막으로 시작 노드를 가는 것이 트리 순회의 과정입니다.
A→B→A→C→A
다른 예를 봐보도록 합시다.
어떤 식으로 순회할 수 있는지 한 번 생각 해보세요!
이를 코드로 구현하면 다음과 같습니다.
def traversal(root):
if root is None:
return
traversal(root.left)
traversal(root.right)
Python
복사
순회를 하는 방법을 알았으니, 이제 방문에 대해서 공부할 차례입니다. 방문은 앞서 언급했듯이 노드의 값을 접근 하는 것(출력, 저장)입니다.
그리고 노드의 방문 방식에 따라 전위순회, 중위순회, 후위순회로 나누어 집니다.
•
전위 순회: A를 가장 먼저 방문 하는 것
◦
출력 순서: A(root), B(left), C(right)
◦
나를 먼저 방문하고 자식 노드들을 방문한다.
•
중위 순회: A를 중간에 방문 하는 것
◦
출력 순서: B(left), A(root), C(right)
◦
왼쪽 노드를 먼저 방문하고, 나를 방문한 후, 오른쪽 노드를 방문한다.
•
후위 순회: A를 가장 마지막에 방문 하는 것
◦
출력 순서: B(left), C(right), A(root)
◦
자식노드들을 다 방문한 후, 나를 방문한다.
다음과 같은 코드가 있을 때, 각각의 순회에서 어떤 식으로 방문하는지 알 수 있어야 합니다.
pop quiz
전위순회
방문순서
중위순회
방문순서
후위순회
방문순서
def traversal(root):
if root is None:
return
traversal(root.left)
traversal(root.right)
Python
복사
위와 같은 코드에서 언제 방문 할 지에 따라 전위, 중위, 후위의 코드가 결정됩니다.
각각의 코드를 구현해보도록 합시다.
전위 순회 구현
def preorder(root):
if root is None:
return
print(root)
preorder(root.left)
preorder(root.right)
Python
복사
중위 순회 구현
def inorder(root):
if root is None:
return
inorder(root.left)
print(root)
inorder(root.right)
Python
복사
후위 순회 구현
def postorder(root):
if root is None:
return
postorder(root.left)
postorder(root.right)
print(root)
Python
복사
전위, 중위, 후위 순회 시간복잡도
재귀의 시간복잡도 = 재귀 함수 호출 수 x (재귀 함수 하나당) 시간복잡도
저희는 앞서서 재귀의 시간복잡도를 위와 같이 공부하였습니다. 전위, 중위, 후위 순회의 시간 복잡도도 마찬가지로 구할 수 있습니다.
•
재귀 함수 호출 수 :
•
재귀 함수 하나당 시간 복잡도:
⇒ 전위, 중위, 후위 순회의 시간 복잡도는 입니다.
Copyright 2023. 노씨데브. All rights reserved. 무단 공유 및 배포를 금합니다.