[자료구조] 트리(Tree)

트리(Tree)는 계층형 트리 구조를 시뮬레이션하는 추상 자료형(ADT, Abstract Data Type)으로, 루트값과 부모-자식 관계의 서브 트리(Subtree)로 구성되며, 서로 연결된 노드의 집합을 말한다. 트리는 하나의 뿌리에서 위로 뻗어나가는 모양으로 생겼기에 트리(나무)라는 명칭이 붙게 되었는데, 실제 트리 구조를 표현할 때는 나무 형상과는 반대 방향으로 표현한다.

트리의 속성

재귀로 정의된 자기 참조 자료구조(Recursively Defind Self-Referential)
트리는 자식도 트리이고, 그 자식도 트리이기 때문에 여러 개의 트리가 쌓아 올려져 큰 트리가 된다. 그래서 트리 아래에 있는 트리를 서브트리라고 표현한다.

트리의 명칭

• 루트(Root) - 트리의 최상단
• 간선(Edge) - 노드와 노드를 잇는 선
• 자식(Child) - 노드 아래에 있는 노드
• 부모(Parent) - 노드 위에 있는 노드
• 형제(Brother?) - 부모가 같은 노드들
• 레벨(Level) - 최상단부터 한세대씩 아래로 내려갈 때마다 0부터 1씩 증가한다.
• 크기(Size) - 자신을 포함한 모든 자식 노드의 개수
• 깊이(Depth) - 루트에서부터 현재 노드까지의 거리
• 높이(Height) - 현재 위치부터 리프(Leaf, 최하단)까지의 거리

그래프와 트리의 차이점

• 트리는 순환 구조를 갖지 않는 그래프로, 특수한 형태의 그래프의 일종이다.
• 트리는 부모 노드에서 자식 노드를 가리키는 단방향만 존재한다.
• 트리는 하나의 부모 노드만을 갖는다.

이진 트리 말고 삼진, 사진 트리는 없나?

트리 중에서 가장 흔히 사용되는 트리 자료구조는 이진 트리와 이진 탐색트리(BST, Binary Search Tree)이다. 각 노드가 m개 이하의 자식 노드를 가지고 있다면, m-ary 트리(다항 트리, 다진 트리)라고 한다. 이진 트리 구조는 다진 트리 구조에 비해 매우 간결하고 그 때문에 여러가지 알고리즘을 구현할 때 많이 활용되므로, 특별한 경우를 제외하고는 트리라고 하면 이진 트리를 나타낸다.

이진 트리의 종류

• 정 이진 트리(Full Binary Tree) - 모든 노드가 0개 또는 2개의 자식 노드를 가짐
• 완전 이진 트리(Complete Binary Tree) - 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 노드는 왼쪽부터 채워짐
• 포화 이진 트리(Perfect Binary Tree) - 모든 노드가 2개의 자식 노드를 갖고 있으면서, 모든 리프 노드가 농일한 깊이 또는 레벨을 가짐