📖Tree

노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조

• 단방향
• 사이클이 없음
• 항상 Root에서 시작해 간선으로 연결
• 트리 내 트리(Sub Tree)가 있는 재귀적 자료구조
• 모든 자식 노드는 하나의 부모 노드만 가짐
• 두 개의 정점 사이에 반드시 1개의 경로만이 존재
• 노드가 n개인 트리는 항상 n-1개의 간선을 가짐

📖용어

• 높이(Height) : 리프 노드에서 루트 노드까지의 거리
• 깊이(Depth) : 루트 노드에서 특정 노드까지의 거리
• 레벨(Level) : - 특정 깊이를 가지는 노드의 집합 (루트의 깊이 : 0)
• 차수(Degree) : 자식 노드의 개수
• 루트 노드(Root Node) : 부모가 없는 최상위 노드, 트리 당 하나의 루트 노드만 존재
• 부모 노드(Parent Node) : 자식 노드를 가지는 노드
• 자식 노드(Child Node) : 부모 노드의 하위 노드
• 형제 노드(Sibling Node) : 같은 부모를 가지는 노드
• 서브 트리(Sub Tree) : root에서 뻗어 나오는 큰 트리의 내부에 트리 구조를 갖춘 작은 트리

📖사용

• 컴퓨터 디렉토리 구조
• 회사의 조직도
• 최대/최소 힙
• 우선순위 큐

📖종류

📎Binary Tree

📎Heap

📎Trie