[자료 구조] 트리(Tree)란?
[자료 구조] 트리(Tree)란?
트리(Tree)의 개념
- 트리는 노드로 이루어진 자료 구조
- 트리는 하나의 루트 노드를 갖는다.
- 루트 노드는 0개 이상의 자식 노드를 갖고 있다.
- 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.
- 노드(Node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다.
- 트리에는 사이클(Cycle)이 존재할 수 없다.
- 노드들은 특정 순서로 나열될 수도 있고, 아닐수도 있다.
- 각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있다.
- 각 노드는 어떤 자료형으로도 표현 가능하다.
- 비선형 자료구조로 계층적 관계를 표현함
- 비선형 자료 구조 : 원소들을 순차적으로 나열하지 않은 것
- ex) 디렉토리 구조, 조직도
- 그래프의 종류
- 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph)
- 또는 DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류
트리(Tree)와 관련된 용어
- 루트 노드(root node) : 부모가 없는 노드, 트리는 하나의 루트 노드만을 가짐
- 단말 노드(leaf node) : 자식이 없는 노드, '말단 노드' or '잎 노드'라고도 부름
- 터미널 노드라고도 부름
- 내부(internal node) : 단말 노드가 아닌 노드
- 간선(edge) : 노드를 연결하는 선 (link, branch라고도 부름)
- 형제(sibling) : 같은 부모를 가지는 노드
- 노드의 크기(size) : 자신을 포함한 모든 자손 노드의 개수
- 노드의 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
- 노드의 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합
- Level0, Level1, Level2, Level3등등
그래프와 트리의 차이
출처
댓글
댓글 쓰기