Tree에 대해 설명해보세요
Keyword
비선형, Node, Edge, Root Node, Terminal Node, Internal Node, level, height, 방향 비순환 Graph
Script
트리는 비선형 자료구조로, 계층적 관계를 표현하는 자료구조입니다. 대표적으로 이진트리나 이진탐색트리 등이 그 예시입니다.
트리는 Node와 이를 잇는 Edge로 구성되며, 최상위의 노드를 Root Node, 하위에 더 이상 Node가 없는 Node를 Terminal Node, Terminal Node를 제외한 다른 모든 노드(root node 포함)를 Internal Node라 부릅니다. 또, Root Node를 기준으로 level은 0이고, Tree의 height는 Tree의 최고 레벨을 의미합니다.
특징으로는 N개의 Node를 가지는 Tree는 N-1개의 Edge를 가진다는 것과 Root Node에서 특정 Node로의 경로가 유일하다는 것입니다. (방향 비순환 Graph)
Additional
Graph와 Tree의 차이점
Graph는 Tree의 상위 개념으로, Tree도 일종의 Graph이다.
먼저 Graph는 네트워크 모델이고, Tree는 계층 모델이라는데서 차이점이 생겨난다. Graph는 부모-자식 관계 개념이 없지만, Tree는 계층적 관계를 가지기 때문에 부모-자식 관계가 존재한다.
Graph는 순환, 비순환 구조 모두 해당되고, 방향, 무방향을 모두 허용하지만, Tree는 방향성이 있는 비순환 구조를 가지는 Graph이다.
with programming