트리(Tree)란?

트리란?

---

- 노드들을 간선으로 연결한 계층형 자료구조

- 제일위의 하나의 노드를 루트노드로 하여 나머지 노드들이 간선으로 연결

- 하나의 노드는 그자체로 트리이며 루트가 됩니다.

- ㅌ스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조입니다.

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

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

1. 트리에는 사이클(cycle)이 존재할 수 없습니다. 

사이클(cycle)

트리는 사이클이 없는 하나의 연결 그래프구조라고 할 수 있습니다.

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

self-loop

 

트리와 관련된 용어

---

트리의 구조

• 노드 node: 트리는 노드들의 집합으로 트리를 구성하는 것으로 보통 값과 부모 자식의 정보를 가지고 있다.
• 엣지/간선 edge: 엣지는 노드들을 연결하는 간선으로 부모 노드와 자식 노드를 연결하게 된다.
• 루트 노드 root node: 가장 상위 노드로 부모를 가지지 않는다.
• 리프 노드 leaf node: 가장 하위 노드로 자식을 가지지 않는다.
• 형제 노드 sibling node: 같은 부모를 가지는 자식 노드들을 말한다.
• 노드의 깊이 depth: 트리에서 부모에서 자식순으로 이동할 때, depth가 1 증가하며 따라서 형제 노드 간의 depth는 일치하며 root node의 depth는 0이 된다.
• 노드의 크기 size: 자신을 포함한 모든 자손 노드들의 개수를 말한다.
• 노드의 레벨 level: 트리의 특정 깊이를 가지는 노드의 집합을 말한다.
• 노드의 차수 degree: 하위 트리 개수 / 엣지 수
• 트리의 차수 degree of tree: 트리의 최대 차수를 말한다.
• 트리의 높이 height: 루트 노드에서 가장 깊숙히 있는 노드의 깊이를 말한다.

 

트리의 종류

---

1. 이진 트리가 아닌 트리 Non-binary-tree

• 노드의 자식 개수에 대한 제한이 없는 트리
• 대표적인 예: 트라이(trie)

트라이 자료구조 예시

2. 이진 트리 Binary-tree

• 노드의 자식 개수가 2개 이하인 트리
• 이진 검색 트리 Binary-search-tree (BST)
• 균형 이진 탐색 트리 Balanced binary search tree
• 완전 이진 트리
• 전 이진 트리
• 포화 이진 트리

위의 트리의 종류에 대해서는 앞으로 계속 포스팅을 할 예정입니다!

 

관련 알고리즘 이론

---

• 이진 힙: 완전 이진 트리의 한 종류
• 트라이
• 그래프 : 트리는 그래프의 한 종류