[자료구조] 트리(Tree)

트리(Tree)

트리는 기존에 정리했던 스택과 큐와 같은 선형 자료구조가 아닌 비선형구조를 가진 자료구조다.  아래 그림과 같이 비선형구조는 데이터가 계층으로 구성되어있는 구조로 선형구조와 큰 차이를 띄고 있다. 

트리 자료구조의 대표적인 예는 파일구조를 들 수 있다. 폴더안에 폴더 또는 파일이 있는 것을 떠올리면 된다. 오늘은 트리의 전체적인 개념에 대해 정리해볼 계획이다. 

트리 자료구조가 지닌 특징과 구조에 대해서 알아보자.

[특징]

1. Root(루트)가 존재한다.

최상위에 존재하는 노드를 Root라고 정해 놓고, 계층을 나눈다.

2. Node의 개수에서 -1한 값은 트리의 간선 개수와 같다.

트리는 모든 노드가 연결되어 있기 때문에 (N(노드의 개수)- 1 )간선이 존재하게 된다.

3. 높이가 H인 이진트리가 가질 수 있는 노드의 최소 (H+1), 최대 (2^(H+1)-1)개다.

최소의 경우는 편향 이진트리일 때를 말하고, 최대의 경우는 포화이진트리일 경우를 말한다.

4. 순환 구조를 갖지 않는 비 방향성 연결 그래프 구조다.

각 노드들은 루트 아래로 각각의 부속트리를 이루며, 순환구조를 띄고 있지 않다.

[구조]

트리를 구현할 때 기본적인 용어들이 존재한다. 그 용어들에 대해서 정리해보자.

(노드 안에 쓰여진 알파벳은 순서와 관련없다.)

[Node(노드)]

트리구조에서 각각의 원소들을 노드라고한다. 원하는 자료형을 만들어 각각의 노드를 생성할 수 있다.

[Edge(간선)]

간선은 그림에 표시되어있지 않지만 노드와 노드를 연결해준 선을 간선이라고 한다. 현재 그림에서는 무방향간선으로 그렸지만 탐색을 할 때에는 간선은 방향에 따라 중요한다. 상위노드를 가리키면 부모를 가리키게 되는 것이고, 최종 목적지는 Root(루트)가 된다. 하위노드를 가리키면 자식을 가리키는 것이기 때문에 하위탐색을 하게 되고, 시작점은 Root(루트)며 찾고자하는 노드를 찾을 수 있다.

[Root(루트)]

최상위에 존재하는 노드를 Root(루트)라고 한다. 트리에서 탐색의 기준이 되는 노드다.

[Leef(잎)]

잎은 트리 구조에서 가장 마지막에 위치하는 단말노드를 말한다. 그림에서 초록색 노드들은 모두 단말 노드라고 할 수 있다. 잎은 자기 다음의 자식노드가 존재하지 않는다.

[Depth(깊이)/Level]

트리는 계층적 구조이기 때문에 깊이가 존재한다. 루트의 깊이를 0으로 기준을 잡는다면 노드 B의 깊이는 1, 노드 J의 깊이는 3이된다. 본 그림에서의 최대 깊이는 3이다.

[Length(길이)]

길이는 루트에서 특정 노드까지의 길이를 말한다. 노드 C의 길이는 2이가 되며, 노드 G는 3이 된다. 각각의 길이정보를 알 수 있다면 각 노드간의 거리를 알 수 있다.

[sub_Tree(부속 트리)]

부속트리는 트리 안에 있는 작은 트리를 말한다. 트리 구조는 전체뿐만 아니라 부분 트리를 이룬다.

[차수]

차수는 각각의 노드의 자식노드의 개수를 말한다. 차수가 2이하라면 이진트리를 이루지만, 모든 경우가 이진트리를 이루지는 않는다. 차수가 여러개 존재할 경우에는 일반트리로 구현을 해줘야한다.

다음 게시물에는 이진트리와 일반트리에 대해서 정리해보고, 각각 직접 구현해본 것을 정리해볼 것이다.