Tree 자료구조
- Tree: 그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조
- 비선형 구조 : 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 구조.
트리 구조는 루트(Root) 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결합니다.
각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하계층으로 연결되면 부모/자식 관계를 가집니다.
위 그림에서 A는 B와 C의 부모 노드(Parent Node)이고, B와 C는 A의 자식 노드(Child Node)입니다. 자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(leaf Node)라고 부릅니다.
용어정리
- 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
- 루트(Root) : 트리 구조의 시작점이 되는 노드
- 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
- 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
- 리프(Leaf) : 트리 구조의 끝지점이고, 자식 노드가 없는 노드
자료구조 Tree는 깊이와 높이, 레벨 등을 측정할 수 있습니다.
-
길이
트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현할 수 있습니다. 루트 노드는 지면에 있는 것처럼 깊이가 0입니다. 위 그림에서 루트 A의 depth는 0이고, B와 C의 깊이는 1입니다. D, E, F, G의 깊이는 2입니다. -
레벨
트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현할 수 있습니다. depth가 0인 루트 A의 level은 1입니다. depth가 1인 B와 C의 level은 2입니다. D, E, F, G의 레벨은 3입니다. 같은 레벨에 나란히 있는 노드를 형제 노드(sibling Node) 라고 합니다. -
높이
트리 구조에서 리프 노드를 기준으로 루트까지의 높이(height)를 표현할 수 있습니다. 리프 노드와 직간접적으로 연결된 노드의 높이를 표현하며, 부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로 가집니다. 트리 구조의 높이를 표현할 때에는 각 리프 노드의 높이를 0으로 놓습니다.위 그림에서 H, I, E, F, J의 높이는 0입니다. D와 G의 높이는 1입니다. B와 C의 높이는 2입니다. 이때 B는 D의 height + 1 을, C는 G의 height + 1 을 높이로 가집니다. 따라서, 루트 A의 높이는 3입니다. -
서브 트리(Sub tree)
트리 구조에서 root에서 뻗어나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리를 서브 트리 라고 부릅니다. (D, H, I)로 이루어진 작은 트리도 서브 트리이고, (B, D, E)나 (C, F, G, J)도 서브 트리입니다.
트리의 실사용
- 파일탐색기
- 월드컵 토너먼트 대진표, 가계도(족보), 조직도 등.
출처 : 코드스테이츠
