[Algo] Tree개념

Tree

한 개 이상의 Node로 이루어진 유한 집합

(1) 트리의 개념

• 비선형
• 원소들 간에 계층관계를 가지는 계층형 자료구조
• 원소들 간에 관계가 1:n인 자료구조
• 상위 → 하위로 내려가며 확장되는 트리 구조
• cycle이 없음
• Node( = 정점)수가 N개 라면, 간선수는 N-1개
• Tree는 연결 컴포넌트

⭐ 연결 컴포넌트 : 트리의 어떤 정점을 선택하든 경로가 있어야하고, 경로는 단 하나!!

(2) 트리 용어정리

• 루트노드(root Node) : 트리의 시작 노드
• 노드(Node) : 트리의 원소
• 간선(Edge) : 노드를 연결하는 선
• 서브트리(Subtree) : 부트리, 부모 노드와 연결된 간성을 끊었을 때 생성되는 트리
• 조상 노드 : 자식노드들의 위에 있는 모든 노드들
• 형제 노드 (sibling node) : 같은 부모 노드의 자식 노드들
• 자손 노드 : 서브 트리에 있는 하위 노드