트리(Tree)
리스트나 스택 또는 큐로 가게도,조직도를 구현할 수 없습니다. 선형 자료구조로 계층형 구조를 표현하기 어렵습니다. 이처럼 계층형 구조를 가진 문제를 해결하기 위한 조료구조 형태가 트리입니다.
- 1개 이상의 유한한 개수의 노드의 집합
- 루트 노드와 0개 이상의 겹치지 않는 하위 나무 구조들의 집합으로 이루어짐
트리는 전체적으로 node와 edge라는 것으로 표현됩니다. 위의 동그라미가 node이며 여기에 우리는 특정 정보를 저장할 수 있고, 선으로 연결되는 것을 edge라고 부르며 정보들간의 관계를 나타냅니다.
트리의 용어
- path: edge에 의해 연결된 node들의 집합
- root node: 최상위의 node
- parent(부모), children(자식), siblin(형제), grandparent(조부모), ancestor(조상): 기준이 되는 것의 바로 직계 상위 node를 부모, 바로 아래층의 node를 자식, 같은 부모를 둔 node들의 형제, 부모의 부모를 조부모, 직계 상위 노드들은 조상
- leaf(잎): 자식이 없는 node
- subtree: 큰 tree에 속한 작은 tree
- node의 degree: 하위 subtree의 개수
- node의 level: root node부터 최하위 node까지의 중첩되지 않은 path의 node개수
출처: 참고블로그