트리
1. 트리의 개념
트리는 데이터 간의 관계를 나타내는 비선형 자료구조로 특정 조직의 조직도를 대표적인 예로 들 수 있다. 트리는 데이터가 저장되는 노드와 다른 노드를 연결하는 가지로 구성되며 여러 가지들을 이용하여 계층적인 관계를 갖는다.
각 노드의 정보 항목과 뻗어져 나가는 가지를 합쳐 트리라고 부르는데 아래 그림에는 10개의 노드와 9개의 가지가 존재한다. 내부가 모두 비어있는 트리인 빈트리가 아닐 경우 최상위 노드를 루트라 부르며 사장실이 루트가 된다. 각 노드에서 하단으로 향하는 가지의 수를 차수라고 부르며 사장실의 차수는 3개, 그 외의 노드의 차수는 1개로 볼 수 있고(최 하단 팀 제외) 해당 트리의 차수를 얘기할 때는 제일 큰 차수인 3이 된다.
트리에는 단말 노드 또는 잎 노드가 있는데 하단으로 향하는 가지가 없는, 즉 차수가 0인 노드들을 가리키며 위 그림에서는 인사팀, 경리팀, 영업팀이 단말 노드가 되며 그 외에 다른 노드들은 비 단말 노드나 내부 노드라고 부른다.
트리의 뻗어나가는 정도, 즉 깊이를 볼 때 레벨(그림에서는 L)로 부르는데 아래로 한 번 뻗어나갈 때 마다 레벨은 1씩 증가하며 사장실 ~ 팀까지는 L3까지 내려가며 이는 트리의 깊이(혹은 높이)를 4라고도 부른다. 해당 트리는 루트를 제외하면 3개의 서브 트리로 나뉘는데 이는 숲이라고도 부른다. (n개의 서브 트리를 가진 트리에서 루트 노드를 제거했을 때 분리된 트리)
2. 이진트리
이진트리는 모든 노드의 차수가 최대 2를 넘지 않는 트리이다. 즉 모든 노드는 왼쪽과 오른쪽 최대 단 두개의 자식 노드를 가지고 있다. 이 특성을 이용하면 N개의 노드에서 최대 높이와 최소 높이를 계산으로 구할 수 있다. 최대 높이는 N개의 노드를 사용해 왼쪽이나 오른쪽으로 치우쳐진, 즉 경사 이진트리를 형성하는 경우인데 이때의 최대 높이는 노드의 개수와 같은 N이 된다. 최소 높이는 모든 노드가 두 개의 노드를 모두 가지고 있을 때 log₂N + 1이 최소 높이가 된다.
이진트리의 주요 연산으로는 삽입, 삭제, 순회가 있다. 그 중에서 먼저 순회에 대해 살펴보자. 이진트리에서 순회 연산은 일정한 순서에 따라 각 노드를 한 번씩 방문하는 것이다. 이 연산을 이용해 트리 내 정보를 선형적인 순서의 정보로 만들어 사용할 수 있다. 트리의 순회 방법으로는 전위 순회, 중위 순회, 후위 순회 총 세 가지의 형태가 있는데 어디를 먼저 방문하느냐에 따라 방법이 달라진다. 루트에서 시작해 왼쪽 서브 트리, 오른쪽 서브 트리 순으로 방문한다면 전위 순회, 왼쪽 서브 트리 후 타고 올라가 루트를 방문 후 오른쪽 서브 트리로 간다면 중위 순회, 왼쪽 서브 트리 후 오른쪽 서브 트리 후 마지막으로 루트로 간다면 후위 순회가 된다.
3. 특수 이진트리
포화 이진트리란 모든 노드가 최대 자식 노드인 2개를 모두 갖고있는 트리이다. 계산식으로는 깊이가 n라고 가정할 때 노드의 개수가 2ⁿ - 1개인 이진트리이다. 즉, 깊이가 n인 이진트리는 최대 2ⁿ - 1개를 갖고 있다.
완전 이진트리란 트리의 최대 레벨을 n이라 했을 때 n - 1까지는 포화 이진트리이되 n부터는 왼쪽부터 오른쪽으로 채워진 트리이다. 총노드의 개수를 2ⁿ⁺¹ - 1을 초과하지 않으면서 노드 번호에 해당하는 연속적인 번호를 갖는 트리이다. 포화 이진트리는 완전 이진트리 중 하나라고는 볼 수 있지만 완전 이진트리는 포화 이진트리가 아니다.
