Tree 구조에 대해 설명해보세요.

[트리의 정의]

트리는 1개 이상의 노드를 갖는 집합으로 노드들은 다음과 같은 조건을 만족한다.

(1) 트리에는 루트(root)라고 부르는 특별한 노드가 있다.

(2) 다른 노드들은 원소가 중복되지 않는 n개의 부속 트리 (subtree) T1, T2,···,Tn으로 나누어지며 Ti 각각은 루트의 부속 트리라고 부른다. (트리는 사이클이 없는 그래프 (acyclic graph)이며 계층 구조를 이룬다.)

[트리 자료구조의 필요성]

트리 구조에 저장하면 더 효율적인 자료들이 있기 때문이다. 예를 들면 계층적인 데이터 형태들은 트리에 저장하면 자연스럽게 표현된다.

(1) 회사나 정부의 조직 구조,

(2) 나라, 지방, 시•군별, 계층적인 데이터의 저장,

(3) 인덱스 파일의 생성 등이다.(인덱스는 계층적 자료 구조로 검색을 쉽게 해 준다).

[트리에 관한 용어]

- 노드의 차수(degree) : 노드의 부속 트리의 개수

- 트리의 차수(degree of tree) : 트리의 최대 차수

- 맆(leaf, 단말, terminal) 노드: 차수가 0인 노드, 즉 맨 끝에 달린 노드들이다.

예) ( K, L, F, G, M, I, J )

- 내부(internal, non-terminal) 노드 : 차수가 1 이상인 노드

예) ( A, B, C, D, E, H )

- 부모(parent) : 부속 트리(subtree)를 가진 노드

- 자식(child) : 부모에 속하는 부속노드

- 형제(sibling) : 부모가 같은 자식 노드들

- 조상(ancestor) : 노드의 부모 노드들의 총 집합

- 자손(descendant) : 노드의 부속 트리에 있는 모든 노드들

- 레벨(level) : 루트 노드들로부터 깊이(루트 노드의 레벨 = 1)

- 트리의 깊이(depth of tree) : 트리에 속한 노드의 최대 레벨

[트리 구조 저장법]

(1) n-링크 표현법

- 노드에 n 개의 링크를 두고 자식의 개수만큼 링크에 저장한다. 모든 노드는 자식 노드 수에 관계없이 최대 n개의 링크를 갖는다. 각 링크는 부속 트리가 저장된 곳을 링크한다.

* 차수가 n인 경우 표현된 노드

(2) 왼쪽자식노드-오른쪽형제노드 표현 방법

- 모든 노드에 링크가 2개 있다. 첫째 링크는 첫 번째 자식노드를 표현하고 둘째
링크는 자신의 오른쪽 형제 노드를 표현한다.

- 노드의 길이가 2개로 고정되기 때문에 n-링크 방법보다 간편하다.

* 차수가 n인 트리를 차수가 2인 트리로 저장하는 방법

- 트리를 왼쪽자식노드-오른쪽형제노드로 변환하여 그린 다음
45도 시계 방향으로 돌리면 된다.(약간 수정은 필요)

- 모든 노드가 2개 이하의 자식 노드를 갖는다.

- 차수가 2인 트리가 된다.(이진 트리)

[이진(Binary) 트리]

트리(일반 트리) 중에서 자식 노드의 수가 2개 이하인 것을 이진 트리(binary tree)라고 한다. 일반 트리는 앞에서 보았듯이 컴퓨터에 표현하기 어렵기 때문에 이진 트리로 바꾼다. 대부분 응용에서 일반 트리보다는 원래부터 이진 트리로 표현된 문제가 많다.

이진 트리(a binary tree)는 유한개의 노드로 구성된 트리로

(1) 비어있거나 혹은

(2) 루트노드와 2개의 부속 트리로 구성된다. 2개의 부속 트리는 왼쪽 부속 트리, 오른쪽 부속 트리라고 부른다.

* 주의 : 노드가 없는 경우도 이진 트리의 일종이다.

[이진 트리의 성질]

이진 트리는 자식의 개수가 2개 이하인 일반트리가 아니다.

- 노드가 없는 트리도(empty node)도 이진 트리가 된다.

- 부속 트리(자식노드)에 순서가 있다.

- 이진 트리의 최대 레벨이 i 인 경우 트리의 최대 노드의 개수는 2i-1 이다.

- 이진 트리의 맆 노드의 개수 n0 와 차수가 1인 노드의 개수 n1, 차수가 2인 노드의 개수 n2 에 관한 다음의 등식이 성립한다.

• n0 = n2 + 1

(증명) 전체 노드 개수를 n이라고 하면

① n= n2 + n1 + n0 (노드 개수는 세 가지 경우를 합한 것이다.)

② n= 2 * n2 + 1 * n1 + 0 * n0 + 1

(전체 노드 수는 자식노드를 곱한 식에다, 루트 노드 1을 더한다.)

두 식을 계산하면 n과 n1 이 소거되어 증명 성립

이진 트리 저장 방법의 비교

(1) 배열을 이용한 저장법

- 저장이 편하다.

- 노드의 위치를 쉽게 알 수 있다. 첨자가 0부터 시작한다고 가정하면

m 레벨의 k번째 노드의 위치는 ? -> (2 m-1 –1) + (k -1)

- 배열의 이용하지 않는 저장 공간이 많다.

깊이가 k인 트리에서 전체 필요한 공간은 S(k) = 2k – 1 이지만 skewed 이진트리처럼 깊이에 비하여 노드 수가 적은 경우 기억 공간 활용률이 낮다.

- complete(완전) 이진 트리의 저장에는 효과적이다

(2) 연결리스트를 이용한 저장법

- 트리의 크기와 깊이에 관계없이 노드 수만큼의 데이터를 저장한다.

- 트리의 크기가 증가하여도 기억장소에서 노드를 확보하여 트리를 구성할 수 있다.

- 트리 전체를 탐색하는 알고리즘이 배열보다는 복잡하다.

- 트리의 최대 깊이를 대비하여 많은 기억장소를 확보하고, 트리가 예상보다 커지면 프로그램 수행을 종료해야 한다.