[트리, Tree] 트리의 정의, 트리에 대하여

1. 트리(Tree) : 계층적 관계를 표현하는 자료구조이다. 가장 쉽게 알 수 있는 트리의 종류는 컴퓨터의 디렉토리 구조 역시 트리로 되어 있다.

트리라고 하는 것은 Root를 기준으로 가지(Branch)를 뻗어 나가기 때문이다.

트리를 처음 이해하면 일반 자료구조처럼 이를 이용해서 데이터를 저장하고 꺼내야 한다는 생각은 비우도록 하자. 
대신 무엇인가를 표현하는 도구라고 생각하자.

 * 의사 결정 트리 : Yes/No에 따라 가지가 나뉘어 지는 트리. 다양한 데이터 분석 기법에 유용한 도구가 된다.

---

• - 노드(Node) : 트리의 기본 요소. 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것이다. 
• - 가지(Branch, Edge) : 노드와 노드를 연결하는 간선
• - Root Node : 트리의 맨 위에 있는 노드이다. 위 예시에는 1 이다
• - 차수, Degree : 각 노드에서 뻗어나온 가지의 수이다. 위 예시에는 1의 차수 = 2 / 2의 차수 =  2 / 4의 차수 = 1이다
• - 트리의 차수 : 노드들의 차수 중에서 가장 많은 수를 의미한다. 위 예시에는 2이다.
• - 단말 노드(Terminal Node = Leaf Node) : 자식이 하나도 없는 노드이다. 이 단말 노드의 차수는 0이다. 
  위 예시에는 5, 6, 7, 8이 단말노드이다.
• - 비단말 노드(Non-Terminal Node) : 자식이 하나라도 있는 노드이다. 위 예시에는 1, 2, 3, 4가 비단말 노드이다.
• - 자식노드(Children Node) : 어떤 노드에 연결된 다음 레벨의 노드들을 의미한다. 만약 위 예시에서 2의 자식 노드는 4와 5가 된다.
• - 부모노드(Parent Node) : 어떤 노드에 연결된 이전 레벨의 노드이다. 위 예시에서 8의 부모 노드는 4가 된다.
• - 형제노드(Sibling) : 동일한 부모를 갖는 노드들을 의미한다. 위 예시에서 7의 형제노드는 7이 된다. (참고로 트리 구조상 위에 있을수록 촌수가 높다. 부모와 자식의 관계는 상대적이다. 즉, 2는 1의 자식노드이면서 4와 5의 부모노드이다.)
• - Level : 루트 노드의 레벨을 1로 가정한 후 어떤 레벨이 L이면 자식 노드는 L+1이다.
• - 깊이(Depth, Height) : 어떤 트리에서 노드가 가질 수 있는 최대의 레벨을 의미한다. 위 예시에서 깊이는 4이다.
• 그렇다면 트리의 순서는 어떻게 될까? Root -> 왼쪽 -> 오른쪽의 순서가 기본적이다. 

 

---

 

트리의 종류에는 일반 트리, 이진 트리, 완전 이진트리, 균형 이진트리, 포화 이진트리, 균형 트리 등으로 되어 있다.

이진 트리(Binary Tree)	각 노드가 최대 두 개의 자식을 갖는 트리이다. 모든 트리가 이진 트리는 아니다. 이진 트리의 순회는 중위 순회(left -> 현재 -> right), 전위 순회(현재 -> left -> right), 후위 순회(left -> right -> 현재)가 있다. 이진 탐색 트리는, 모든 노드가 모든 왼쪽 자식들 <= n <= 모든 오른쪽 자식들의 특정 순서를 따르는 이진 트리이다.
완전 이진트리(Complete BT)	마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리이다.
균형 이진트리(Full Binary Tree)	모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다.
포화 이진트리(Perfect Binary Tree)	균형 이진트리이면서 완전 이진트리로, 모든 단말노드는 같은 높이에 있어야 하며, 모든 내부 노드가 두 개의 자식노드를 갖는다.
균형 트리(B-Tree)	레드블랙트리, AVL트리가 이 일종이며, 시간 복잡도 O(logN)에 삽입, 찾기 등을 무리없이 가능한 균형 잡힌 트리이다.

---

2. 이진트리(Binary Tree)와 서브트리(Sub Tree)

 1) 서브트리 : 큰 트리에 속하는 작은 트리들을 가리켜 서브트리라 한다.

왼쪽 서브 트리는 B를 루트 노드로 하는 서브 트리, 오른 쪽 서브 트리는 C를 루트 노드로 하는 서브 트리이다.

왼쪽 서브 트리를 보면 B를 루트 노드로 삼지만 그 아래에 또 두가지의 서브 트리가 존재한다. 

위 사진은 이진 트리이다. 이진 트리의 정의에는 두 가지 조건이 필요하다.

• - 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.
• - 나뉘어진 두 서브 트리도 모두 이진 트리여야 한다.

즉, 이진 트리가 되려면, 루트 노드를 중심으로 둘로 나뉘는 두 개의 서브 트리도 이진 트리어야하고, 그 서브 트리의 모든 서브 트리도 이진 트리여야 한다.

그렇다면 위 사진도 이진 트리일까? ㅇㅇ 이진 트리가 맞다. 왜냐하면 노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면 공집합 노드가 존재하는 것으로 간주하기 때문이다.

따라서 위와 같은 트리는 이진 트리 취급을 받지만,

위와 같은 트리는 이진 트리가 아닌 일반 트리이다.

또한 이진 트리에는 일반 이진 트리, 포화 이진 트리, 완전 이진 트리, 균형 이진트리가 있다. 각 특징은 위에 있다.
이해하기 쉽게 사진을 예로 들어 설명하도록 하겠다.

 

---

물론 트리는 이 밖에도 다양한 종류가 있다(레드블랙트리, B-트리 등등)

트리는 정말정말 중요한 자료구조이기 때문에 지속적으로 공부하는 것을 추천한다.

다음은 트리의 순회에 대한 포스팅이다.