Tree란?

Tree 자료구조는 데이터를 마치 거꾸로된 나무 형태로 저장하는 자료구조이다. Tree 자료구조는 여러 유형이 존재하지만 그 중 가장 기본은 binary tree(이진 트리) 자료구조이다. 이진 트리는 두 개의 자식 노드를 가진 트리 형태이다.

구성 요소

Node: 트리 구조의 교점이다. Node가 데이터를 가지고 있고 또한 자식 노드를 가지고 있습니다. 트리 자료구조는 노드를 기본으로 구성되어 있다.

Root Node: 트리 구조의 최 상단의 노드, 즉 시작점이 되는 노드 이다.

Edge: 트리를 구성하기 위해 노드와 노드를 연결하는 선이다.

level: 트리의 특정 깊이를 가지는 노드의 집합이다.

degree: 하위 트리 개수, 즉 각 노드가 지닌 가지의 수를 말한다.

Internal Node: Leaf 노드를 제외한 중간에 위치한 노드들을 말한다.

Leaf Node: 하위에 다른 노드가 연결되어 있지 않은 노드이다.

• 트리 속성 중 가장 중요한 것은 '루트 노드를 제외한 모든 노드는 단 하나의 부모노드만을 가진다'는 것이다.

트리의 탐색

트리의 순회란 트리의 각 노드를 체계적인 방법으로 방문하는 과정을 말한다. 노드를 방문하는 순서에 따라 전위 순회, 중위 순회, 후위 순회 세가지로 나뉜다.

1.전위순회(preorder)
루트 노드 > 왼쪽 서브 트리 > 오른쪽 서브 트리 순으로 순회는 방식이다. '깊이 우선 순회'라고도 한다.

2.중위순회(inorder)
루트 노드에서 시작해서 왼쪽 서브 트리 > 노드 > 오른쪽 서브 트리 순으로 순회하는 방식이다. '대칭 순회'라고도 한다.

3.후위 순회(postorder)
루트 노드에서 시작해서 왼쪽 서브 트리 > 오른쪽 서브 트리 > 노드 순으로 순회하는 방식이다.

이진 트리와 이진 탐색 트리

Tree 구조는 데이터의 저장의 의미보다는 저장된 데이터를 더 효과적으로 탐색하기 위해서 사용된다. 이진 트리는 앞서 언급한대로 각 노드가 최대 2개의 자식 노드를 가질 수 있다. 이 2개의 노드를 left node, right node라고 한다. left node는 부모 node의 값보다 작은 값이 저장되고 right node는 같거나 큰 값이 저장된다.

이진 트리는 최대 차수가 2인 트리를 말한다. 이는 하나의 노드에 LEFT or RIGHT만 존재한다고 표현한다. 이진 트리에는 여러 유형이 존재한다.

1.편향 이진 트리(Skewed Binary Tree)
편향 이진 트리는 하나의 차수로만 이뤄져 있는 경우를 말한다. 이런 구조는 배열과 같은 선형 구조이기 때문에 Leaf Node(가장 끝 노드) 탐색 시 결국 모두 읽어들여야 한다는 단점이 있어서 효율이 떨어진다고 말한다. 이같은 점을 보완하기 위해서 '높이 균형 트리'라는 것이 있다.

2.포화 이진 트리(Full Binary Tree)
포화 이진 트리는 Leaf Node를 제외한 모든 노드의 차수가 두 개로 이뤄진 경우를 말한다. 이 경우에는 해당 차수에 몇 개의 노드가 존재하는지 바로 알 수 있어 개수 파악이 용이하다는 장점이 있다.

3.완전 이진 트리(Complete Binary Tree)
포화 이진 트리와 같은 개념으로 생성하지만 모든 노드가 왼쪽부터 순서대로 생성되는 이진 트리를 말한다.

이진 탐색 트리(Binary Search Tree)란?

이진 탐색 트리는 이진 탐색이 항상 동작하도록 구현하여 탐색 속도를 극대화시킨 자료구조를 말한다.

이진 탐색 트리에서는 항상 부모 노드가 왼쪽 자식보다는 크고 오른쪽 자식보다는 작다. 이러한 특성 덕분에 이진 탐색 트리에서는 한 번 확인할 때마다 보아야 하는 원소의 개수가 절반씩 줄어든다는 점에서 '완전 이진 트리'인 경우 탐색 시간에 O(logN)의 시간 복잡도를 가진다.

이진 탐색 트리에서 탐색(traverse)를 할 때는 찾고자 하는 값이 부모 노드보다 작을 경우 왼쪽 자식으로, 찾고자 하는 값이 부모 노드보다 클 경우 오른쪽 자식으로 이어 나가면서 방문한다.

더 공부할 것

• 시간 복잡도란?