Related to: Data Structure
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을 뺀 것과 같다.
참조
https://ratsgo.github.io/data structure&algorithm/2017/10/21/tree/