[C언어] 자료구조 - Tree 트리 -1

 

트리에 대해서 알아보자. 

트리는 계층적인 구조(hierarchical structure)로서 선형이 아닌 구조를 띄고 있다.

 

선형이 아니라는 것은?

선형보다는 삽입,삭제가 쉽지 않음을 의미한다.

그렇지만 그럼에도 쓰는 이유에는 장점이 커서 그렇다.

 

트리는 말 그대로 나무를 뒤집어놓은 모양과 비슷하다고 해서 붙혀진 이름이다.

뭐 이런 형식으로 저장해놓은 것이다.

우선 용어부터 정리하고 가자면

 

–노드(node) : 트리의 구성요소

–루트(root) : 부모가 없는 노드(A)

–서브트리(subtree) : 하나의 노드와 자손들로 이루어짐

–단말노드(terminal) : 자식이 없는 노드(A,B,C,D)

–비단말노드 : 자식을 가지는 노드(E,F,G,H,I,J)

 

–자식, 부모, 형제, 조상, 자손 노드 : 내 위가 부모고 조상이다.

내 아래가 자식이고 자손이다.

–레벨(level) : 트리의 각층의 번호

–높이(height) : 트리의 최대 레벨(3)

–차수(degree) : 노드의 자식 노드수

-노드와 노드를 잇는 선: 간선 or edge

(트리의 차수를 물어본다면 트리가 가지고 있는 노드의 차수중에 가장 큰값)

 

밑에 트리의 차수는3이라고 할 수 있다.

 

 

트리도 이런 형태를 가지고 있지만

프로그래밍에서 어떻게 구현할 것이냐가 문제다.

 

쉽게 배열로 표현할 수 있다.

그러나 노드는 자신의 데이터와 자신의 자식들을 가리키는 링크를 가져야 하는데

차수가 달라진다면 배열의 크기도 노드마다 각각 달라져야한다. 

 

그래서 연결리스트를 이용하는 방법을 많이 쓴다.

하지만 또한 자식에게 접근하려면 부모에서부터 접근해야한다는 단점이 있어서 얘도 시간 많이 잡아먹는다.

 

**연속된 구조와 연결된 자료구조에 대해서는 장단점을 알고 있어야 한다.

 

---

그렇다면 어떻게 해야할까...?

트리의 차수를 통일한다.

2로 통일한다.

그래서 나온것이 이진트리이다. binary tree라고도 불리고 가장 많이 쓰는 트리형태이다.

이진트리라면 배열로, 연결리스트로도 괜찮게 구현 가능하다. 굿굿굿

 

 

그래서 이진트리로 트리를 알아볼 생각이다.

 

이진트리는 모든 노드의 최대 차수가 2, 모든 노드가 2개 이하의 서브 트리를 갖는다.

그리고 자식이 2명이면 2명을 구분해줘야 한다.

이런식으로 그래야 연산이 가능해진다.

 

---

 

이제는 이진트리의 성질을 알아보자

 

1. n개의 노드를 가진 트리는 n-1개의 간선을 갖는다.

 

왜냐하면 루트노드는 부모노드를 가지지않기 때문이다.

그니까 노드는 무조건 부모랑 이어져있으니까 당연히 n개있을 줄 알지만

루트는 부모노드를 가지지 않는다.

 

2. 높이가 h인 이진트리는 h개 이상, 2^h - 1개 이하의 노드를 가진다.

 

이진트리지만 자식을 하나만 가지게 해서 최대한 높이를 늘린다 하면

h의 높이를 가질 수 있고

이진트리니까 무조건 자식 만땅으로 완전트리를 만든다면(완전트리는 나중에설명)

1+2+2^2+2^3 ..... 2^(n-1) = 2^n - 1 이라는 중학교 공식에 의해 그렇게 된다.

 

 

3. n개의 노드를 가지는 이진트리의 높이는 2번을 로그를 취하면 된다. 

 

⌈log_2 (n+1)⌉ ~ n 이정도???

이런식으로 가능하다. 

 

---

 

이제 이진트리의 종류를 알아보자면

 

우선 3가지정도로 분류가능하다.

 

1. 포화 이진트리

2. 완전 이진트리

3. 그 외

 

1. 포화 이진트리

각 레벨의 노드가 꽉 차있는 이진 트리이다.

그러므로 높이가 h면 정확히 2^h -1의 노드를 가진다.

 

2. 완전 이진트리

포화트리는 아니지만 높이가 h라고 하면 높이가 h-1레벨 때 까지의 노드가 꽉 차있고

h 레벨에서는 왼쪽부터 노드가 순서대로 차있는 트리를 뜻한다. 

h레벨에서는 포화가 아니라는 소리다. -> h레벨에서만 포화가 아니다.

위의 트리는 포화트리는 아닌데 완전트리다.

그렇다면 포화트리는 완전트리일까??? 

그렇다. 하지만 역은 성립하지 않는다.

 

3. 그외 

정 말 그 외에 것들 ㅋㅋㅋㅋㅋ

 

그렇다. 트리에 대한 기본 개념을 알아보았고

다음 글에서는 기본연산에 대해서 알아보자.