트리Tree에 대한 내용을 다루겠습니당!

자료구조를 파악하는데 가장 필요한 기본 용어로,

이걸 잘 알고 있으면 이후에 많이 사용되는 자료구조(Heap이라던가...Heap이라던가... 이거 몰라서 틀려서 이러는거 아녜용 ㅠ)를 이해하는데 기초를 알게 되는 것이라 보시면 됩니당.

트리(Tree)

비선형 자료구조입니당. 뜬금없이 이게 뭔 소리냐, 일반적으로 배열Array은 원소가 순차적으로 나열이 되어 있지만, 트리Tree는 원소가 '계층'으로 나뉘어져 있어용.

왜 굳이? 라고 생각하실 수도 있지만, 이건 원소를 찾는 속도를 높여줘용!

좌측에 있는게 배열Array이고, 우측에 있는 걸 트리Tree라고 합니당. 여기서 5 원소를 찾을려면 어떻게 해야할까요?

배열은 그냥 순차적으로 확인하면 됩니다만, 여기서 총 5번 원소를 확인해야 하므로 $O(n)$이 됩니당.

근데 트리Tree는 껑충껑충 뛰어요! $1 \to 2 \to 5$만 거쳐 총 3번만 확인할 수 있습니다! 이 경우 시간 복잡도가 $O(\log n)$이 되용 와우!

실제로 이런 방식으로 빠르게 찾아가려면 트리를 좀 더 깊게 알아야 겠지만, 이번엔 트리Tree에 대한 기본 개념만 설명하겠습니당 ㅎㅎ

트리 구성 요소

여기서 동그라미를 노드Node라고 합니당. 데이터의 '단위'라고 생각하시면 됩니당. 그리고 각 노드Node를 잇는 선을 간선Edge이라고 해용.

노드Node는 위치에 따라 다르게 불려용. 가장 위에 있는 노드를 루트 노드Root Node라고 합니당. 그리고 가장 아래에 다른 노드가 연결되지 않은 노드를 단말 노드Leaf Node라고 해용. 보통은 '리프 노드'라고 합니당.

그리고 여기서 '리프 노드'를 제외한 모든 노드를 내부 노드Internal Node라고 해용! 참고로 루트 노드Root Node도 포함합니당!

자 그럼 기본 개념을 정리하자면,

노드 : 데이터의 단위
간선 : 각 노드를 잇는 선
루트 노드 : 가장 위에 있는 노드
리프 노드 : 가장 아래에 다른 노드가 연결되지 않은 노드
내부 노드 : 리프 노드를 제외한 모든 노드(루트 노드 포함)

그리고 추가로 트리Tree에 대한 특징을 정리하자면,

트리Tree 특징
1. 그래프의 한 종류로, 방향성있는 비순환 그래프DAG(Directed Acyclic Graph)입니당.
2. 사이클이 불가능해, 자체 간선(자기 자신을 연결, Self-loop)이 불가능합니당.
3. 임의의 두 쌍의 노드를 잇는 간선은 유일!**
4. 따라서, 노드의 개수가 n개라면 간선의 개수는 n-1개입니당.

트리에 대한 내용은 여기까집니당!