트리 순회 알고리즘

트리(Tree)

트리는 노드(Node)와 그 노드들을 연결하는 간선(Edge)로 이루어진 자료구조이다. (노드가 N개인 경우 간선은 N-1개이다.)

트리는 계층적 관계로 이루어져 있기 때문에 그래프와 다르게 사이클이 이루어지지 않는다. 사이클이 이루어지지 않고 방향성이 정해져 있기 때문에 트리는 그래프 중에서 DAG에 속하는 그래프이다. 

 

트리는 그럼 어떻게 이루어져 있는가?

트리의 구성은 다음과 같다. 가장 최상단에 루트 노드(Root Node)가 있고 밑으로 내려갈수록 자식 노드가 있으며 최하단의 노드는 리프노드(Leaf Node, 단말노드;)라고 부른다.

가장 헷갈려하는 구성요소는 높이와 깊이이다.

높이는 말그대로 트리의 최대 높이를 말한다. 레벨과 동일하며 깊이는 노드를 중심으로 경로의 길이를 의미한다. 

트리의 구성

 

보통 트리 문제는 DFS를 이용한 순회문제나 루트노드 찾기, 서브트리, 높이나 너비 구하기, 트리 찾기등 다양하게 출제된다.

참고 백준 문제자료 : 바킹독 트리 문제집↗

 

이진 트리 (Binary Tree)

이진 트리는 일반 트리와 다르게 모든 노드가 최대 2개까지의 자식 노드를 갖는 트리를 말한다.

최대 2개의 자식노드를 갖기 때문에 자식 노드가 공집합이거나 하나의 노드를 갖는다 하더라도 이진트리에 속한다.

이진 트리의 종류로 대표적으로 3가지가 있다. 이외에도 몇가지 트리가 있긴 있다.

• 포화 이진 트리(Perfect Binary Tree) : 모든 레벨에 꽉찬 이진트리
• 완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외한 나머지 레벨에 노드들이 가득 차있는 상태
• 정 이진 트리(Full Binary Tree) : 리프노드를 제외한 모든 노드가 2개의 자식 노드를 가지고 있는 이진 트리

 

이진 트리의 부모의 인덱스, 자식노드들의 인덱스를 구하려면 다음과 같이 구할 수 있다. 루트노드의 인덱스(`i`)가 1일 경우를 가정한다.

• 현재 자신의 노드 : i
• 현재 노드의 부모의 노드 : i // 2
• 현재 노드의 왼쪽 자식 노드 :  i * 2
• 현재 노드의 오른쪽 자식 노드 : i * 2 +1

다음은 이진 트리 노드의 클래스를 정의하는 방법이다.

class Node:
    def __init__(self, parent, value, left_node, right_node):
        self.parent = parent # 부모노드
        self.value = value
        self.left_node = left_node
        self.right_node = right_node
        
        
 N = 5 # 노드의 개수
 tree = {} # 트리
 
 for i in range(1, N+1):
     value, left_node, right_node = input().split() # 데이터를 입력받음
     tree[value] = Node(i-1, value, left_node, right_node) # 부모노드가 0이면 루트노드

 

트리 순회(Traversal)

트리를 순회하는 방식은 총 4가지가 있다.

아래 그림을 예시로 순회를 진행해보자.

전위 순회(Pre-order)

각 서브트리에 루트 노드를 먼저 방문하는 방식이다. (M → L → R)

# 예제에서는 형제 노드가 아닌 단일 노드의 경우를 -1으로 표시함.

def pre_order(node):
	print(node.value)
    if node.left_node != -1:
    	pre_order(tree[node.left_node])
    if node.right_node != -1:
    	pre_order(tree[node.right_node])

중위 순회(In-order)

각 서브트리에 왼쪽 하위노드를 먼저 방문 후 루트 노드를 방문하는 방식이다. (L → M → R)

def in_order(node):
    if node.left_node != -1:
    	in_order(tree[node.left_node])
    print(node.value)
    if node.right_node != -1:
    	in_order(tree[node.right_node])

후위 순회(Post-order)

각 서브트리에 왼쪽 하위 노드를 방문하고 오른쪽 하위 노드 방문 후 루트 노드를 방문하는 방식이다. (L → R → M)

def post_order(node):
    if node.left_node != -1:
    	post_order(tree[node.left_node])
    if node.right_node != -1:
    	post_order(tree[node.right_node])
	print(node.value)

레벨 순회(Level-order)

레벨 순회는 가장 최상단부터 내려오는 방식이다. 계층별로 방문(a → b → c → d...)

BFS 방식으로 순회하는 것과 유사하다.

m, i 노드는 모두 왼쪽 노드였을 경우를 가정한다.

 

이번엔 해당 순회를 코드로 작성해보자. 

순회 문제는 재귀 호출을 통해 쉽게 문제를 풀 수 있다. 보통 구현을 요구하는 문제들이 나온다.

이진 탐색 트리(Binary Search Tree)

이진 탐색 트리(BST)는 이진트리에서 아래의 성질을 만족한다. 

• 기본적인 이진 트리의 성질을 만족한다.
• 각 노드의 좌측 자식노드는 부모노드보다 작고 우측 자식노드는 부모노드보다 커야 한다.
• 중복된 노드가 존재하면 안된다. 

이진 탐색 트리는 검색을 초점으로 효율적으로 만들어진 트리이다. 그렇기 때문에 중복성이 발생하면 순서가 꼬일 수 있다. 그리고 이진 탐색 트리는 검색이 목적이기 때문에 시간복잡도는 O(logN)이다. 정확하게 말하면 O(h) 높이만큼의 시간복잡도이다. 다만 다음과 같은 경우에는 최악의 시간복잡도인 O(N)이 발생할 수 있다. 선형적인 트리가 되는 경우 균형적으로 구축할 수 없기 때문에 균형을 유지시키기 위해 AVL 트리나 추가비트를 저장해 균형을 유지하는 레드 블랙 트리가 있다. 

트리 구조를 재조정(Rebalancing)하기 위해 구현한 Red-Black Tree도 존재한다.

 

이진 탐색 트리 연산

• 검색 : 일치하지 않는 경우엔 값 비교를 통해 자식 노드로 재귀적으로 검색한다.
• 삽입 : 트리를 탐색 후, 마지막 노드에서 부모노드 보다 크다면 오른쪽 작으면 왼쪽으로 이동한다. 
• 삭제
  • 자식 노드가 없는 노드를 삭제 → 그냥 삭제
  • 자식노드가 1개인 노드를 삭제 → 지워진 노드에 자식을 올리기
  • 자식노드가 2개인 노드를 삭제 → 왼쪽 노드에서 가장 큰 값 혹은 오른쪽 노드에서 가장 작은 값 올리기

 

📝 풀어보기 좋은 문제들

• 백준 문제자료 : 바킹독 트리 문제집