최근 수정:
자료구조의 일종으로 사이클이 없는 그래프를 트리라고 한다. 특히, (간선의 수 == 정점의 수 - 1) 이어야 한다. (이 조건이 되지 않으면 DAG 일 수도 있다.)
모양이 나무와 비슷하다.
대부분의 용어는 그래프와 비슷하다. [1] 그렇지만 트리에서만 사용되는 용어도 존재한다.
하지만 가장 중요한 것은 방향성의 유무이다. 방향성이 없다면 루트, 부모 등의 용어는 무용지물이 된다. 따라서 아래의 용어들은 방향성이 있는 경우에 사용한다.
방향성이 있는 트리를 루트 있는 트리라 해서 Rooted Tree 라고도 한다.
트리에는 여러가지 종류가 있다. 대표적인 것은 이진 트리. 이것 외에도 2-3-4 트리, 레드-블랙 트리, B 트리 등 여러 종류가 있다. 자세한 것은 해당 항목 참고.
트리도 그래프의 일종이므로 그래프와 같은 방식으로 구현 가능하다. (인접 행렬, 인접 리스트 등) 다만, 트리는 사이클이 없으므로 부모 정보만 저장하는 방식으로도 표현 가능하다.
[1] 정점(노드), 간선 등
[2] 패드립이 아니다...!