Related to: Data Structures
개요
Tree는 그 모양이 뒤집어 놓은 나무와 같다고 해서 이런 이름이 붙었습니다. Graph의 특수한 형태로, 사이클이 없는 연결 그래프입니다.
핵심 개념
Tree
Tree는 그 모양이 뒤집어 놓은 나무와 같다고 해서 이런 이름이 붙었습니다. 예컨대 다음 그림과 같습니다.
- node : 위 그림에서 검정색 동그라미, 데이터가 담기는 곳
- edge : node와 node 사이를 이어주는 선, 노드와의 관계를 표시
- path : edge로 연결된, 즉 인접한 노드들로 이뤄진 시퀀스(sequence)를 의미, 경로의 길이(length)는 경로에 속한 edge의 수
- tree height : root node에서 말단 node에 이르는 가장 긴 경로의 edge 수
- tree level : tree의 특정 깊이를 가지는 node의 집합
- leaf node : 자식 node가 없는 node
- internal node : 잎새노드를 제외한 node
- root node : 부모노드가 없는 node
Tree의 성질
Tree의 속성 중 가장 중요한 것이 ‘루트노드를 제외한 모든 노드는 단 하나의 부모노드만을 가진다’는 것입니다. 이 속성 때문에 트리는 다음 성질을 만족합니다.
- 임의의 노드에서 다른 노드로 가는 경로(path)는 유일
- 회로(cycle)가 존재하지 않음
- 모든 노드는 서로 연결되어 있음
- 엣지(edge)를 하나 자르면 트리가 두 개로 분리됨
- 엣지(edge)의 수 |E| 는 노드의 수 |V|에서 1을 뺀 것과 같다.
관련 개념
- Binary Tree란 무엇일까 — 이진 트리의 종류와 특성
- Heap — 완전 이진트리 기반의 우선순위 큐
- Graph — 트리의 상위 개념인 그래프 자료구조
- 그래프와 트리(Tree and Graph) — 그래프와 트리 비교
- Data Structure — 자료구조 개요
- Decision Tree — 머신러닝에서의 결정 트리
참조
https://ratsgo.github.io/data structure&algorithm/2017/10/21/tree/