트리 Tree
자료들 사이의 계층적 관계(Hierarchical Relationship)를 나타내는데 사용하는 비선형 자료구조
- 1개 이상의 노드를 갖는 집합
- 루트 노드가 존재
- 트리의 부분트리(Sub tree) 또한 트리 구조를 따름
- 트리에는 사이클이 존재할 수 없음
트리의 구성요소(용어)
- 노드(Node): 트리를 구성하고 있는 각각의 요소
- 간선(Edge): 트리를 구성하기 위해 노드와 노드를 연결하는 선
- 깊이(Depth): 루트 노드에서 해당 노드까지 도달하는 데 사용하는 간선의 개수로, 루트 노드의 깊이는 0
- 레벨(Level): 노드의 깊이+1
- 노드의 분지 수, 노드의 차수(Degree): 노드의 자식 수
- 트리의 분지 수, 트리의 차수(Degree of tree): 해당 트리 내 모든 노드의 분지 수 중 최댓값
- 높이(Height): 루트 노드에서 해당 노드까지 도달하는데 지나간 정점의 개수. 노드 중 가장 높이가 높은 노드의 높이를 트리의 높이라고 함
- 루트 노드(Root Node): 트리 구조에서 최상위에 있는 노드
- 단말 노드(Terminal Node, Leaf Node): 하위에 다른 노드가 연결되어 있지 않은 노드
- 내부 노드, 비단말 노드(Internal Node): 단말 노드를 제외한 모든 노드로 루트 노드를 포함
- 부모 노드(Parent Node): 부모 자식 관계에서 상위 계층에 있는 노드로, 상위 계층에 있을수록 노드의 깊이와 레벨이 낮음
- 자식 노드(Child Node): 부모 자식 관계에서 하위 계층에 있는 노드
- 형제 노드: 부모가 동일한 노드
- 조상 노드: 한 노드의 부모노드부터 루트노드까지 가는 경로에 존재하는 모든 노드를 해당 노드의 조상 노드라 함
- 후손 노드: 한 노드를 루트로 하는 서브트리에 있는 모든 노드를 해당 노드의 후손 노드라 함
신장 트리 Spanning Tree
무향 연결 그래프 G의 부분 그래프이고, G의 모든 정점을 포함하는 트리인 그래프
이진 트리 Binary Tree
트리의 분지 수가 2 이하인 트리. 루트 노드를 중심으로 두 개의 서브 트리(이진 트리)로 나뉨
- 자식이 최대 2개이기 때문에 왼쪽 자식과 오른쪽 자식으로 구별
- 높이가 N인 이진 트리의 최대 노드 개수는 2N-1개
- 배열을 이용해 구현할 때
i번 노드의 부모 노드:i/2
i번 노드의 왼쪽 자식:i*2
i번 노드의 오른쪽 자식:i*2+1 - 이진 트리의 순회
전위 순회: 현재 노드 -> 왼쪽 자식-> 오른쪽 자식
중위 순회: 왼쪽 자식 -> 현재 노드 -> 오른쪽 자식
후위 순회: 왼쪽 자식 -> 오른쪽 자식 -> 현재 노드
참고링크
▷ 정 이진 트리 Full Binary Tree
모든 노드의 차수가 0 또는 2인 이진 트리
▷ 포화 이진 트리 Perfect Binary Tree
정 이진 트리에서 모든 단말 노드의 깊이가 같은 이진 트리
- 높이가 H인 포화 이진 트리의 노드 개수는 2H-1개
- 노드가 N개인 포화 이진 트리의 높이는 log2(N+1)개
- 깊이가 D인 포화 이진 트리의 단말 노드 개수는 2D개
▷ 완전 이진 트리 Complete Binary Tree
마지막 레벨은 노드가 왼쪽에 몰려 있고 마지막 레벨을 제외하면 포화 이진 트리 구조를 띄고 있는 이진 트리
- 레벨 1부터 k-1까지는 노드가 모두 채워져있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 채워진 이진 트리
▷ 사향 이진 트리 Skewed Binary Tree
연결리스트처럼 한 줄로 연결 되어 있는 형태의 이진 트리
