트리

트리는 계층형 트리 구조를 시뮬레이션 하는 추상 자료형으로 루트 값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합이다.

 

트리는 하나의 뿌리에서 위로 뻗어 나가는 형상처럼 생겨 '트리' 라는 명칭이 붙었는데, 트리 구조를 표현할 때는 나무의 형상과는 반대 방향으로 표현한다. 트리 구조는 ㄴ우리 주변 일상에서 쉽게 볼 수 있는 위아래 개념을 컴퓨터에서 표현한 구조다. 한 가족의 계보를 나타내는 족보나 회사의 조직등을 보면 보통 트리 구조 형태로 되어있다. 

 

좀 더 중요한 트리의 속성중 하나는 재귀로 정의된 자기 참조 자료구조라는 점이다. 쉽게 말하면, 트리는 자식도 트리고 또 그지삭도 트리다. 즉 여거 개의 트리가 쌓아 올려져 큰 트리가 된다. 흔히 서브트리로 궝된다고 표현하는데, 앞서 트리에 대한 위키피디아 정의에도 서브트리라는 용어가 등장한다. 

 

트리의 각 명칭 

루트

트리는 항상 루트에서부터 시작된다.  루트는 자식 노드를 가지며 간선으로 연결되어 있다.

 

차수

자식 노드의 개수는 차수라고 부르며

 

크기

크기는 자신을 포함한 모든 자식 노드의 개수다.

 

높이

높이는 현재 위치에서부터 리프 까지의 거리,

 

깊이

깊이는 루트에서부터 현재 노드까지의 거리다. 

 

레벨

레벨은 0 에서부터 시작한다. 논문에 따라 1에서부터 시작하는 경우도 있으나 현재 대부분의 문서에서는 0에서부터 시작하는 것이 좀 더 일반적이다.

 

트리는 항상 단방향이기 떄문에, 간선의 화살표는 생략이 가능하다. 

 

트리

 

그래프 vs 트리

 

그래프와 트리의 가장 큰 차이점은 "트리는 순환 구조를 갖지 않는 그래프" 라는 것이다. 핵심은 순환 구조가 아니라는데 있다. 트리는 특수한 형태의 그래프의 일종이며,크게 그래프의 범주에 포함된다. 하지만 트리는 그래프와 달리 어떠한 경우에도 한번 연결된 노드가 다시 연결되는 법이 없다. 이외에도 단방향, 양방향을 모두 가리킬 수 있는 그래프와 달리, 트리는 부모 노드에서 자식노드를 카리키는 단방향뿐이다. 그 뿐만 아니라 트리는 하나의 부모 노드를 갖는다는 차이점이 있으며 루트 또한 하나여야 한다. 

 

트리가 아닌 예시

더 명확히 하기 위해 예시를 가져왔다. 1번은 트리는 순환구조를 갖지 않는 그래프인데 1번은 순환하므로 트리가 아니다.

2번은 트리는 부모노드가 하나여야 하지만 C에 대하여 부모가 A와 D로 2개를 갖는다. 3은 A-B, C-D-E 가 서로 연결되어 있지 않다. 또한 루트가 A와 C 2개다. 트리는 루트가 1개여야 한다. 

 

이진 트리

트리 중에서도 가장 널리 사용되는 트리 자료구조는 이진 트리와 이진 탐색 트리(Binary Search Tree)이다. 실제로 인터뷰 시에도 가장 자주 질문을 받게 되는 기본적인 트리 형태이기도 하다.

먼저, 각 노드가 m개 이하의 자식을 갖고 있으면 m-ary 트리라고 한다. 여기서 m=2일 경우, 즉 모든 노드의 차수가 2 이하일 때는 특별히 이진트리 라고 구분해서 부른다. 

이진트리는 왼쪽, 오른쪽 최대 2개의 자식을 갖는 매우 단순한 형태로, 다진 트리에 비해 훨씬 간결할 뿐만 아니라 여러 가지 알고리즘을 구현하는 일도 좀 더 간단하게 처리 할 수 있어서, 대체로 트리라고 하면 특별한 경우가 아니고서는 대부분 이진트리를 일컫는다.

 

 

 

이진 트리 유형

트리 유형

• 정 이진 트리 : 모든 노드가 0개 또는 2개의 자식 노드를 갖는다.
• 완전 이진 트리 : 마지막 레벨을 제외하고 모든 레벨이 완전하게 채워져 있으며, 마지막 레벨의 모든 노드는 가장 왼쪽 부터 채워져있다. 
• 포화 이진 트리: 모든 노드가 2개의 자식 노드를 갖고 있으며, 모든 리프 노드가 동일한 깊이 또는 레벨을 갖는다. 문자 그대로 가장 완벽한 유형의 트리다.