[자료구조] 트리(Tree)의 개념, 이진 트리, 전 이진 트리, 완전 이진트리, 포화 이진 트리, 이진 탐색트리

트리(Tree)의 개념

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

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

트리는 다음과 같은 특징들을 갖는다. 

 

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

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

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

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

• 트리에는 사이클(cycle)이 존재할 수 없다. 여기서 사이클이란 시작 노드에서 출발해 다른 노드를 거쳐 다시 시작 노드로 돌아올 수 있다면 사이클이 존재한다고 한다. 

사이클(cycle)

• 트리는 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph)라고 할 수 있다.
• 트리의 노드는 self-loop가 존재 해서는 안된다.

  

  self-loop

• N개의 노드를 갖는 트리는 항상 N-1 개의 간선(edge)을 갖는다.
• 모든 자식 노드는 한 개의 부모 노드만을 갖는다.

트리와 관련된 용어

트리(Tree) 의 구조

• 루트 노드(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이다)

 

트리(Tree)의 종류

1. 이진트리(Binary Tree)

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

 

이진 트리

 

이진 트리는 전위 순회, 중위 순회, 후위 순회를 통해 탐색할 수 있다. 이에 대해서는 다음을 참고하자.

 

 

[자료구조] 트리의 순회, 중위 순회, 전위 순회, 후위 순회 | C언어 구현, 소스코드

 

 

2. 완전 이진트리, 전 이진 트리, 포화 이진 트리 

• 완전 이진트리(Complete Binary Tree)

완전이진트리

   1) 완전 이진트리는 마지막 레벨을 제외 하고 모든 레벨이 완전히 채워져 있다.

   2) 마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 채워져야 한다.

   3) 트리의 높이가 h일때 2^(h-1) ~ 2^h-1 개의 노드를 가질 수 있다.

   4) 완전 이진 트리는 배열을 사용해 효율적으로 표현 가능하다.

 

• 전 이진트리(Full Binary Tree)

  

  전이진트리

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

  

• 포화 이진트리(Perfect Binary Tree)

  

  포화이진트리

  1) 포화 이진트리는 모든 레벨이 노드로 꽉 차 있는 트리를 뜻한다. 

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

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

  4) 트리의 노드 개수가 정확히 2^k-1 개여야 한다. 여기서 k는 트리의 높이다. 

 

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

이진탐색트리

이진 탐색 트리는 이진트리이면서 아래와 같은 속성을 갖는 트리를 뜻한다.

 

1) 이진 탐색 트리의 노드에 저장된 키(key)는 유일하다.

2) 부모의 키가 왼쪽 자식 노드의 키보다 크다.

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

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

 

이진 탐색 트리는 효율적인 탐색을 위해 고안된 트리이다. 

이진 탐색 트리에 대해 자세히 알아보고 싶다면 다음 포스팅을 참고하자.

 

[자료구조] 이진탐색트리(Binary Search Tree)의 개념, 이해 | C언어 구현, 소스코드

 

---