Tree
트리는 하나의 뿌리에서 위로 뻗어 나가는 형상처럼 생겨서 트리(나무) 라는 명칭이 붙었는데, 트리 구조를 표현할 때는 나무의 형상과는 반대 방향으로 표현한다.
트리는 하나의 재귀로 정의된 자기 참조 자료구조다. 트리는 자식도 트리고 또 그 자식도 트리라서 여러 개의 트리가 쌓아 올려져 큰 트리가 된다. 흔히 서브트리로 구성된다고 표현한다.
트리의 각 명칭
트리는 항상 루트(root)에서부터 시작된다. 루트는 자식(child) 노드를 가지며, 간선(edge)으로 연결 되어 있다. 자식 노드의 개수는 차수(dgree)라고 하며, 크기(size)는 자신을 포함한 모든 자식 노드의 개수다. 높이(height)는 현재 위치에서부터 리프(leaf)까지의 거리, 깊이(depth)는 루트에서부터 현재 노드까지의 거리다. 트리는 그 자식도 트리인 서브트리(subtree) 구성을 띈다.
레벨(level)은 0에서부터 시작하지만 논문에 따라 1에서부터 시작하는 경우도 있다. 트리는 항상 단방향(Uni-Directional)이기 때문에, 간선의 화살표는 생략 가능하다.
그래프 vs 트리
그래프와 트리의 차이점은 트리는 순환 구조를 갖지 않는 그래프 이다.
핵심은 순환 구조가 아니라는 데 있다. 트리는 특수한 형태의 그래프의 일족이며, 크게 그래프의 범주에 포함된다. 하지만 트리는 그래프와 달리 어떠한 경우에도 한 번 연결된 노드가 다시 연결되는 법이 없다. 이외에도 단방향(Uni-Directional), 양방향(Bi-Directional)을 모두 가리킬 수 잇는 그래프와 달리, 트리는 부모 노드에서 자식 노드를 가리키는 단방향 뿐이다. 그 뿐만 아니라 트리는 하나의 부모 노드를 갖는다는 차이점이 있으며 루트 또한 하나여야 한다. 이처럼 트리와 그래프는 서로 다른 점이 많다.
트리가 아닌 예
그림 1은 순환 구조이기 때문에 그래프와 트리의 차이점에서 첫 번째로 언급한, 트리는 순환 구조를 갖지 않아야 한다는 정의에 부합하지 않는다.
그림 2는 C노드의 부모가 A, D 이렇게 둘이다. 부모 노드는 단 하나여야 한다.
그림 3은 A->B 와 D<-C->E 가 서로 연결되어 있지 않으며, 루트가 둘이므로 트리가 아니다. 루트 또한 하나여야 한다.
이진 트리
트리 중에서도 가장 널리 사용되는 트리 자료구조는 이진 트래와 이진 탐색 트리(Binary Search Tree, BST)다.
각 노드가 m개 이하의 자식을 갖고 있으면, m-ary 트리(다항 트리, 다진 트리)라고 한다. 여기서 m=2일 경우, 즉 모든 노드의 차수가 2 이하일 때는 특별히 이진 트리(Binary Tree)라고 구분해서 부른다. 이진 트리는 왼쪽, 오른쪽, 최대 2개의 자식을 갖는 매우 단순한 형태로, 다진 트리에 비해 훨씬 간결할 뿐만 아니라 여러 가지 알고리즘을 구현하는 일도 좀 더 간단하게 처리할 수 있어서, 대체로 트리라고 하면 특별한 경우가 아니고서는 대부분 이진 트리를 일컫는다.
-
정 이진 트리(Full Binary Tree) : 모든 노드가 0개 또는 2개의 자식 노드를 갖는다.
-
완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가장 왼쪽부터 채워져 있다.
-
포화 이진 트리(Perfect Binary Tree) : 모든 노드가 2개의 자식 노드를 갖고 있으며, 모든 리프 노드가 동일한 깊이 또는 레벨을 갖는다. 문자 그대로, 가장 완벽한 유형의 트리다.