트리

트리(tree)는 계층형 트리 구조를 시뮬레이션하는 추상 자료형(ADT)으로, 루트 값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합이다.

트리의 중요한 속성 중 하나는 재귀로 정의된 자기 참조 자료구조라는 점이다.

트리는 항상 루트(root)에서부터 시작된다.

루트는 자식(child) 노드를 가지며, 간선(edge)으로 연결되어 있다.

자식 노드의 개수는 차수(degree)라고 하며, 크기(size)는 자신을 포함한 모든 자식 노드의 개수다.

높이(height)는 현재 위치에서부터 리프(leaf)까지의 거리, 깊이(depth)는 루트에서부터 현재 노드까지의 거리다.

그래프와 트리의 차이점

그래프와 트리의 가장 큰 차이점은 "트리는 순환 구조를 갖지 않는 그래프"라는 점이다.

트리는 특수한 형태의 그래프의 일종이며, 트리는 그래프와 달리 어떠한 경우에도 한번 연결된 노드가 다시 연결되는 법이 없다.

이외에도 단방향(uni-directional)과 양방향(bi-directional)을 모두 가리킬 수 있는 그래프와 달리, 트리는 부모 노드에서 자식 노드를 가리키는 단방향 뿐이다.

또한 트리는 하나의 부모 노드를 갖으며 루트 또한 하나여야 한다는 차이점이 있다.

이진 트리

이진 트리(binary tree)는 각각의 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조이다.

이진 트리와 이진 탐색 트리

이진 탐색 트리(binary search tree)는 왼쪽 자식 노드는 부모 노드보다 큰 값을 가지고, 오른쪽 자식 노드는 부모 노드보다 작은 값을 가지는 이진 트리이다.

이진 트리의 시간 복잡도

이진 트리는 O(logN)의 시간 복잡도를 가진다.

2개의 자식 노드를 가지는 이진 트리를 이용해서 M개의 값들 중 원하는 값을 찾는다고 가정하자.

처음에는 M개의 값들 모두 탐색 대상이지만, 루트 노드에서 첫 번째 자식 노드 층으로 이동하게 되면 탐색해야 하는 노드의 수가 절반으로 줄어든다.

이제 M/2개의 값들이 남게 되는데, 다시 한번 다음 자식 노드 층으로 넘어가게 되면 M/4개의 값들이 남게 된다.

이런 식으로 매번 층을 내려갈 때마다 남은 값의 수가 절반이 된다.

만약 탐색을 해야하는 자료의 수가 2^N개라 하면, 이진 트리를 사용할 경우 N번의 탐색을 통해 원하는 값을 찾을 수 있다.

log_2(2^N) = 2이기 때문에, 이진 탐색 트리를 이용한 이진 탐색 기법의 시간 복잡도가 log_2(N)이 된다.

다시 말해, 자식 노드의 수가 M개인 트리로 N개의 자료에서 원하는 값을 탐색하는 알고리즘의 시간 복잡도는 log_m(N)이 된다.