트리, 이진트리

1. 트리, 이진트리
1.1 트리란?
: 트리는 그 모양이 뒤집어 놓은 나무와 같다고 해서 이런 이름이 붙었다.

위 그림에서 검정색 동그라미를 노드(node)라고 한다. 보통 데이터가 여기에 담긴다. 노드와 노드 사이를 이어주는 선을 엣지(edge)라고 합니다. 노드와의 관계를 표시합니다.

경로(path)란 엣지로 연결된, 즉 인접한 노드들로 이뤄진 시퀀스(sequence)를 가리킨다. 경로의 길이(length)는 경로에 속한 엣지의 수를 나타냅니다.

트리의 높이(height)는 루트노드에서 말단노드에 이르는 가장 긴 경로의 엣지 수를 가리킨다. 트리의 특정 깊이를 가지는 노드의 집합을 레벨(level)이라 부른다.

잎새노드(leaf node)란 자식노드가 없는 노드다. internal node란 잎새노드를 제외한 노드를 나타낸다. 루트노드(root node)란 부모노드가 없는 노드를 가리킨다.

트리의 속성 중 가장 중요한 것이 ‘루트노드를 제외한 모든 노드는 단 하나의 부모노드만을 가진다’는 것이다. 이 속성 때문에 트리는 다음 성질을 만족한다.

트리의 특징
- 임의의 노드에서 다른 노드로 가는 경로(path)는 유일하다.
- 회로(cycle)가 존재하지 않는다.
- 모든 노드는 서로 연결되어 있다.
- 엣지(edge)를 하나 자르면 트리가 두개로 분리된다.
- 엣지(edge)의 수 |E|는 노드의 수 |V|에서 1을 뺀 것과 같다.

1.2 이진트리란?
: 이진트리란 자식노드가 최대 두 개인 노드들로 구성된 트리이다. 이진트리에는 정이진트리(full binary tree), 완전이진트리(complete binary tree), 균형이진트리(balanced binary tree) 등이 있다.

정이진트리는 다음 그림과 같다. 모든 레벨에서 노드들이 꽉 채워진(=잎새노드를 제외한 모든 노드가 자식노드를 2개 가짐) 이진트리이다.

위 정이진트리에서 레벨에 따른 노드의 숫자는 다음 표와 같다.

정이진트리의 노드수가 nn개라면 잎새노드의 수는 n/2n/2를 올림한 숫자가 된다. 위 그림 예시를 기준으로 하면 총 31개의 노드가 있는데 이 가운데 잎새노드는 31/2를 올림한 16개이다.

완전이진트리는 다음 그림과 같다. 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 이진트리다.

정이진트리와 완전이진트리는 다음처럼 1차원 배열(array)로도 표현이 가능하다.

균형이진트리는 다음 그림과 같다. 모든 잎새노드의 깊이 차이가 많아야 1인 트리를 가리킨다. 균형이진트리는 예측 가능한 깊이(predictable depth)를 가지며, 노드가 nn개인 균형이진트리의 깊이는 lognlog⁡n을 내림한 값이 된다.

깊이 말고 left subtree와 right subtree의 노드 수를 기준으로 균형이진트리를 정의하는 경우도 있다고 한다. 힙 정렬과 이진탐색트리는 모두 이진트리를 기반으로 만들어진 기법이다.

1.3 트리순회(tree traversla)란?
: 트리순회(tree traversal)란 트리의 각 노드를 체계적인 방법으로 방문하는 과정을 말한다. 하나도 빠뜨리지 않고, 정확히 한번만 중복없이 방문해야 하는데, 노드를 방문하는 순서에 따라 전위순회(preorder), 중위순회(inorder), 후위순회(postorder) 세 가지로 나뉜다. 아래 트리를 예시로 각 방법간 차이를 비교해보자.

1.3.1 preorder
: 루트 노드에서 시작해서 노드-왼쪽 서브트리-오른쪽 서브트리 순으로 순회하는 방식이다. 깊이우선순회(depth-first traversal)라고도 한다. 위 예시 트리에 전위순회 방식을 적용하면 1, 2, 4, 5, 3 이다.

1.3.2 inorder
: 루트 노드에서 시작해서 왼쪽 서브트리-노드-오른쪽 서브트리 순으로 순회하는 방식이다. 대칭순회(symmetric traversal)라고도 한다. 위 예시 트리를 중위순회 방식을 적용하면 4, 2, 5, 1, 3 이다.

1.3.3 postorder
: 루트 노드에서 시작해서 왼쪽 서브트리-오른쪽 서브트리-노드 순으로 순회하는 방식이다. 위 예시 트리를 후위순회 방식을 적용하면 4, 5, 2, 3, 1 이다.