자료구조 트리 개념

 

1. 트리의 정의와 특징

트리는 큐나 스택과 같은 선형 구조가 아닌 비선형 구조의 자료구조이다.

 

선형 구조

[[자료1] [자료2] [자료3] [자료4]]

 

특징

1. 트리는 그래프의 한 종류이다

2. 트리의 간선은 방향성을 가진다 (그래프와의 차이)
그래프중에도 간선이 방향성을 가지는 것을 방향그래프라고 한다.

하지만 모든 그래프가 가져야 하는것은 아니다

 

3. 트리는 하나의 루트 노드를 갖는다 (그래프와의 차이)

그래프에서는 루트 노드의 개념이 없다.

 

4. 루트 노드는 0개 이상의 자식 노드를 갖는다(그래프와의 차이)

그래프에서는 루트 노드의 개념이 없다.

 

5. 자식 노드 또한 0개 이상의 자식노드를 갖는다 (그래프와의 차이)

그래프에서는 자식 노드의 개념이 없다.

 

6. 트리는 노드와 노드를 연결하는 간선으로 이루어져 있다

 

7. 트리에는 사이클 구조가 존재할 수 없다 (그래프와의 차이)

사이클이란 특정 노드에서 시작된 간선이 연결되어 시작됬던 노드로 되돌아 올 수 있는 구조

사이클 구조

8. 트리의 노드는 셀프 루프가 존재해서는 안된다  (그래프와의 차이)

셀프 루프

9. N개의 노드를 갖는 트리는 항상 N-1 개의 간선을 갖는다 (그래프와의 차이)

즉, 트리의 노드 중 아무런 간선 없이 홀로 떨어진 노드는 존재하지 않는다는 말이다.

하지만 그래프에서는 존재할 수 있다

10. 모든 자식 노드는 1개의 부모 노드만을 갖는다 (그래프와의 차이)

그래프에서는 간선의 방향성 자체가 없을 수도 있으므로 부모, 자식 노드의 개념이 무조건 있는것이 아니고

방향성이 있더라도 한 노드만을 향해서 방향성을 가질 필요는 없기 때문에 그래프에서는 존재하지 않는 원칙이다

 

 

2. 트리와 관련된 용어

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

 

3. 트리(Tree)의 종류

1. 이진트리(Binary Tree)

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

 

이진 트리

 

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

 

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

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

완전이진트리

 

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

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

   3) 마지막 레벨 h에서 1~2h-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) 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

 

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

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

 

---

참조

https://code-lab1.tistory.com/8