[ 자료구조 ] 트리(Tree)
1. 트리(Tree)
트리는 노드(Node)로 이루어져 있는 자료 구조입니다.
- 트리는 하나의 루트 노드를 갖고 있으며, 0개 이상의 자식 노드를 갖고 있습니다.
- 데이터를 순차적으로 저장하지 않기 때문에 비선형 자료구조입니다.
- 노드 간에 부모 자식 관계를 갖고 있는 계층형 자료구조이며 모든 자식 노드는 하나의 부모 노드만 갖고 있습니다.
- 순환이 존재하지 않습니다.
- 트리 내에 또 다른 트리가 존재하는 재귀적 자료구조입니다.
2. 트리의 구성 요소 및 관련 용어
1) 트리의 구성요소
노드 ( Node )
- 트리를 구성하고 있는 기본 요소
- 정점이라고도 부른다.
간선 ( Edge )
- 노드와 노드를 연결하는 선
- 노드의 개수를 N개라고 하면, 간선의 개수는 N-1개이다.
루트노드 ( Root Node )
- 트리 구조에서 부모가 없는 가장 최상위에 위치한 노드
부모노드 ( Parent Node )
- 자식 노드를 가지고 있는 노드
자식노드 ( Child Node )
- 부모 노드의 하위에 위치한 노드
형제노드 ( Sibling Node )
- 같은 부모를 가진 노드
리프노드 ( Leaf Node )
- 외부노드 ( External Node, Outer Node ), 단말노드 ( Terminal Node )
- 자식 노드가 없는 노드
가지노드 ( Branch Node )
- 내부노드 ( Internal Node, Inner Node ), 비단말노드 ( Non-Terminal Node )
- 자식 노드를 1개 이상 가지고 있는 노드
2) 트리 관련 용어
깊이 ( Depth )
- 루트에서 어떤 노드까지 도달하기 위한 간선(Edge)의 수
- B의 Depth : 1
레벨 ( Level )
- 트리에서 동일한 깊이를 가지고 있는 노드의 집합
- B의 Level : 1
높이 ( Height )
- 루트에서 가장 하위의 단말노드까지의 깊이(Depth)
- Tree A의 Height : 4
크기 ( Size )
- 자신을 포함한 모든 자식 노드의 개수를 합한 개수
- B의 Size : 6
차수 ( Degree )
- 자식 노드의 개수
- B의 Degree : 2
트리의 차수 ( Degree of Tree )
- 트리의 최대 차수
- Tree A의 최대 차수 : 2
경로 ( Path )
- 한 노드에서 다른 노드 사이에 있는 노드들의 순서
- A ~ D의 Path : A-B-D
경로의 길이 ( Path Length )
- Path 경로 위에 있는 노드의 총 개수
- A ~ D의 Path Length : 3
너비 ( Width )
- 해당 Level에 있는 노드의 수
- Level 2의 Width : 4
넓이 ( Breadth )
- 리프 노드의 수
- Tree A의 Breadth : 5
거리 ( Distance )
- 두 노드 사이의 최단 경로에 있는 간선(Edge)의 수
- D와 J의 Distance : 3
계수 ( Order )
- 부모 노드가 가질 수 있는 최대 자식 수 ( 이진 트리는 Order = 2 )
- Tree A의 Order : 2
3. 이진 트리의 순회
- 순회방법에는 크게 세가지 방법이 있습니다. ( 전위 순회, 중위 순회, 후위 순회 )
- 노드의 우선순위를 어떻게 두는지에 따라서 이름이 달라집니다
1) 전위 순회
- 우선순위 : 현재 노드 > 왼쪽 자식 노드 > 오른쪽 자식 노드
2) 중위 순회
- 우선순위 : 왼쪽 자식 노드 > 현재 노드 > 오른쪽 자식 노드
3) 후위 순회
- 우선순위 : 왼쪽 자식 노드 > 오른쪽 자식 노드 > 현재 노드
4. 트리의 종류
1) 이진트리( Binary Tree )
- 부모 노드가 자식 노드를 최대 2개씩만 갖고 있는 트리
- 2개 이상 가지는 경우 삼항 트리( Ternary tree )라고 합니다.
2) 이진 검색 트리( BST : Binary Search Tree )
- 부모 노드가 자식 노드를 최대 2개씩만 갖고 있는 트리 ( 이진 트리의 특징을 지님 )
- 노드의 왼쪽 자식의 값이 반드시 자신의 값 이하이며, 오른쪽 자식의 값은 반드시 자신의 값 이상입니다.
- 중복 값은 제외
3) 포화 이진 트리( Full Binary Tree )
- Leaf Node를 제외한 모든 노드의 차수가 2개로 이루어져 있는 트리
- 해당 차수에 몇 개의 노드가 존재하는지 파악할 때 용이합니다.
4) 완전 이진 트리( Complete Binary Tree )
- 포화 이진 트리와 같은 개념으로 트리를 생성하지만, 모든 노드가 왼쪽부터 차근차근 생성되는 이진트리
- Heap은 완전 이진 트리의 일종입니다.
5. 트리 구조 활용
- 최댓값, 최솟값을 빠르게 알고 싶을 때
- 계층적인 데이터 저장하고자 할 때 ( ex. 컴퓨터의 폴더 구조 )
- heap ( 우선순위 큐 )
마치며
트리의 기본 개념과 관련된 용어를 알아볼 수 있었습니다.
단순해보이는 자료구조이면서도 실생활에서 자주 사용되기 때문에 알아두면 좋은 구조라고 생각됩니다.
※ 참고
- https://thinking-developer.tistory.com/70
- https://yoongrammer.tistory.com/68