5 min to read

트리(Tree)란?

Concept

Featured image

Table of Contents

용어 정리

트리는 계층적인 구조를 표현할 때 사용되는 비선형 자료구조입니다.

image

그래프와 트리

그래프는 노드와 노드간을 연결하는 간선으로 구성된 자료구조입니다. 일반적으로 네트워크 모델, 즉 객체와 이에 대한 관계를 표현하는 유연한 방식으로 이해할 수 있습니다. 트리는 그래프의 특수한 형태로 사이클이 존재하지 않는 방향 그래프(Directed Acyclic Graphs, DAG)를 말합니다.

사이클이 존재한다는 것은 그래프의 특정 노드에서 출발하여 돌아다니다가 다시 처음 출발했던 곳으로 되돌아 갈 수 있으면, 사이클이 있다고 합니다.

image

위의 표를 참고하면 트리의 특징이 아래와 같이 구별된다는 특징이 있습니다.

다음의 두 예시는 A노드와 B노드에서 사이클이 존재하지 않기 때문에 트리가 아닙니다.

image

또한 다음의 예시도 트리가 아닙니다. 사이클이 존재하지는 않지만 1에서 4로 가는 경로가 유일하지 않아서입니다.

image

아래의 예시 또한 트리가 아닙니다. 연결되지 않은 노드가 존재하기 때문입니다.

image

순회(Treversal)

트리순회(tree traversal)란 트리의 각 노드를 체계적인 방법으로 방문하는 과정을 말합니다. 하나도 빠뜨리지 않고, 정확히 한번만 중복없이 방문해야 하는 규칙이 있습니다. 노드를 방문하는 순서에 따라 전위순회(pre-order), 중위순회(in-order), 후위순회(post-order) 세 가지로 나뉩니다. 아래 트리를 예시로 각 방법 간 차이를 비교해 보겠습니다.

image

전위순회(pre-order)

루트 노드를 먼저 방문하고 왼쪽 끝까지 내려간 다음 서브트리의 자식노드를 왼쪽-오른쪽 순으로 방문합니다. 깊이우선순회(depth-first traversal)라고도 합니다.

def pre_order(node):
    print(node.data, end=' ')
    if node.left_node != None:
        pre_order(tree[node.left_node])
    if node.right_node != None:
        pre_order(tree[node.right_node])

중위순회(in-order)

왼쪽의 서브트리를 방문한 후, 루트 노드를 방문합니다. 다시 오른쪽의 서브트리로 이동하여 순회를 계속합니다. 대칭순회(symmetric traversal)라고도 합니다.

def in_order(node):
    if node.left_node != None:
        in_order(tree[node.left_node])
    print(node.data, end=' ')
    if node.right_node != None:
        in_order(tree[node.right_node])

후위순회(post-order)

서브트리의 자식노드를 왼쪽-오른쪽 순으로 방문하고 마지막으로 루트 노드를 방문하는 방식입니다.

def post_order(node):
    if node.left_node != None:
        post_order(tree[node.left_node])
    if node.right_node != None:
        post_order(tree[node.right_node])
    print(node.data, end=' ')

이진 트리(Binary Tree)

이진트리란 자식노드가 최대 두 개인 노드들로 구성된 트리입니다. 즉 Degree가 2 이하인 트리를 말합니다. 이진 트리는 트리의 구조에 따라 여러개의 종류로 구분됩니다.

image

정 이진 트리(Full Binary Tree)

모든 레벨의 노드가 꽉 채워진 이진 트리를 말하며, 즉 리프노드를 제외한 모든 노드가 자식노드를 0개 또는 2개를 가지는 이진트리의 구조입니다.

완전 이진 트리(Complete Binary Tree)

완전 이진트리는 정 이진 트리와 유사하지만, 마지막 레벨을 제외 하고 모든 레벨이 완전히 채워져 있는 이진트리의 구조입니다. 마지막 레벨의 경우, 꽉 채워져 있을 필요는 없지만 노드가 왼쪽에서 오른쪽으로 채워져있어야 합니다.

포화 이진 트리(Pefect Binary Tree)

포화 이진 트리는 모든 노드가 두 개의 자식 노드를 가지며, 모든 리프 노드가 동일한 깊이 또는 레벨을 갖습니다.

균형 이진 트리(Balanced Binary Tree)

균형 이진 트리는 왼쪽의 서브트리와 오른쪽의 서브트리의 깊이 차이가 1만큼 나는 트리를 말합니다.

편향된 이진 트리(Skewed Binary Tree)

한쪽 방향의 자식 노드만을 가진 이진 트리

image

이진탐색 트리(Binary Search Tree, BST)

이진 탐색트리는 이진탐색의 아이디어를 채용한 자료구조입니다. 이진 탐색은 원소가 정렬되어 있다는 조건 아래, 정렬된 특징을 이용해 탐색 범위를 반으로 좁혀나가며 검색을 합니다. 그러므로 찾고자 하는 데이터의 크기가 클 수록 효과적이며, $O(log N)$의 시간복잡도를 가지게 됩니다.

하지만 이진 탐색 특성 상 데이터의 삽입이나 삭제가 불가능하기 때문에, 데이터가 자주 변경되는 상황이라면 사용하기 어렵다. 따라서 링크드리스트의 경우, 노드를 기반으로 데이터와 그 다음 노드를 가리키는 포인터 (Pointer) 를 통해 삽입이나 삭제는 $O(1)$의 시간복잡도를 가지게 되어 매우 효율적이다.

이진 탐색트리는 이러한 이진탐색과 링크드리스트의 장점을 결합한 구조로, 효율적인 탐색 능력을 가지면서도 데이터의 삭제나 삽입시에도 유연하게 대응할 수 있습니다.

이진탐색 트리는 이진 트리 기반의 탐색을 위한 자료구조입니다. 모든 노드는 유일한 값이며, 왼쪽 서브 트리의 값은 루트노드의 값보다 작고, 오른쪽 서브 트리의 값은 루트노드보다 큰 값을 가지도록 구성합니다.

아래 그림은 [21, 28, 14, 32, 25, 18, 11, 30, 19, 15]의 순서로 주어지는 값으로부터 이진 탐색 트리를 구축하는 과정을 보여준다. 맨 먼저 입력된 값이 뿌리(root) 노드가 되며, 그 다음부터는 입력값과 노드 간 대소관계에 따라 입력값의 노드 위치가 결정됩니다.

gjf

아래 그림은 위와 같이 만든 이진 탐색 트리에서 27을 찾는 과정을 보여준다. 이진 탐색 트리가 정렬된 배열보다 효과적으로 원하는 값을 찾음을 확인할 수 있습니다.

gjf

또한 이진탐색 트리의 순회는 중위순회(in-order) 방식을 따른다는 것을 알 수 있습니다.

시간복잡도

이진탐색 트리의 경우, 이진탐색과 링크드리스트의 장점을 결합하였기 때문에 편향된 이진트리를 제외하고는 노드의 개수를 N이라고 하였을 때, 탐색/삽입/삭제 시, $O(log N)$의 시간 복잡도를 가지게 됩니다. 트리가 편향되었을 경우 모든 노드를 탐색해야 하기 때문에 $O(N)$의 시간 복잡도를 가지게 됩니다.

Reference

https://ratsgo.github.io/data%20structure&algorithm/2017/10/21/tree/

http://ejklike.github.io/2018/01/09/traversing-a-binary-tree-1.html