여러 종류의 트리(Tree) 정리 (이진 트리, 전 이진 트리, 완전 이진 트리, 포화 이진 트리, 이진 탐색 트리)

트리의 개념

 

- 노드로 이루어진 자료구조로 스택이나 큐 같은 선형 구조가 아닌 비선형 자료구조이다.

- 계층적 관계를 표현하는 자료구조이다.

 

 

 

 

트리의 특성

 

- 하나의 루트 노드를 갖는다.

- 루트 노드는 0개 이상의 자식 노드를 갖는다.

- 자식 노드 또한 0개 이상의 자식 노드를 갖는다.

- 노드들과 노드들을 연결하는 간선(Edge)들로 구성되어 있다.

- 사이클(Cycle)이 존재할 수 없다. 트리는 사이클이 없는 하나의 연결 그래프라고 할 수 있다.

★사이클이란? 시작 노드에서 출발해 다른 노드를 거쳐 다시 시작 노드로 돌아올 수 있는 구조를 말함한다.

사이클(Cycle)

- 트리의 노드는 self-loop가 존재해서는 안된다.

 

self-loop

 

- N개의 노드를 갖는 트리는 항상 N-1개의 간선을 갖는다.

- 모든 자식 노드는 한 개의 부모 노드만을 갖는다.

 

 

 

 

트리 관련 용어

 

 

- 루트 노드(root node) : 부모가 없는 노드로 트리는 단 하나의 루트 노드를 가진다. (ex : A- 루트노드)

- 단말 노드(leaf node) : 자식이 없는 노드로 terminal 노드라고도 부른다. (ex : C, D, E - 단말 노드)

- 내부 노드(internal node) : 단말 노드가 아닌 노드(ex : A, B - 내부 노드)

- 간선(edge) : 노드를 연결하는 선

- 형제(sibling) : 같은 부모 노드를 갖는 노드들 (ex : D-E, B-C : 형제)

- 노드의 깊이(depth) : 루트 노드에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수(ex : D의 depth : 2)

- 노드의 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합 ( ex : level 1- {B, C} )
- 노드의 차수(degree) : 자식 노드의 개수 (  ex : B의 degree - 2, C의 degree - 0)

- 트리의 차수(degree of tree) : 트리의 최대 차수 ( ex : 위 트리의 차수는 2이다)

 

 

 

 

트리의 종류

 

1. 이진트리(Binary Tree)

 

이진트리는 각 노드가 최대 두 개의 자식을 갖는 트리를 뜻한다. 즉, 각 노드는 자식이 없거나 한 개 이거나 두 개만을 갖는다.

이진 트리

 

2. 완전 이진트리(Complete Binary Tree)

 

완전이진트리

 

- 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져있다.

- 왼쪽에서 오른쪽으로 채워져야 한다.

- 트리의 높이가 h일때, 2^(h-1) ~ 2^h-1 개의 노드를 가질 수 있다. (ex : h=3일 때, 마지막 레벨에 노드가 1개 존재하는 경우가 최소개수로 4개부터 마지막 레벨에 다 채워져있는 경우가 최대로 7개까지)

- 배열을 사용해 효율적으로 표현 가능하다. (왼쪽에서 오른쪽으로 채워져 있어서임)

 

 

3. 전 이진트리(Full Binary Tree)

 

전이진트리

 

모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다.

 

 

4. 포화 이진트리(Perfect Binary Tree)

 

포화이진트리

 

- 모든 레벨이 노드로 꽉 차 있는 트리이다.

- 전 이진트리의 성질도 만족해야함. 즉 모든 노드가 0개 혹은 2개의 자식 노드를 갖는다.

- 모든 말단 노드가 동일한 깊이 또는 레벨을 갖는다.

- 트리의 높이가 h일때, 노드 개수가 정확히 2^h-1개여야 한다.

 

 

5. 이진 탐색 트리(Binary Search Tree)

 

이진탐색트리

 

- 이진트리의 조건도 만족한다.

- 노드에 저장된 키는 유일하다. 중복 X

- 부모의 키가 왼쪽 자식의 키보다 크다.

- 부모의 키가 오른쪽 자식의 노드의 키보다 작다.

- 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.