17강: 트리(Tree)
트리(Tree)란?
- 순환하는 길이 없는 그래프(graph)로 정의한다.
- 정점(node)에서 간선(edge)들이마치 나무에서 뿌리로부터 잔가지로 뻗어나가듯이 가지치기 된 구조를 말한다, 즉 데이터의 배치 형태를 추상화한 자료구조
용어설명
- 노드 (nodes)
- 노드들 사이에는 부모(parent), 자식(child) 노드가 있다
- 부모 노드는 루트 노드와 가까운, 자식 노드는 리프노드와 가까운
- 부모의 부모는 조상(ancestor)
- 자식의 자식은 후손(descendant)
- 간선 (edges)
- 루트 노드 (root node)
- 맨 위의 노드
- 리프 노드 (leaf node)
- 더 이상 가지를 치지않는 마지막 노드
- 내부 노드 (internal node)
- 루트, 리프노드를 제외한 노드
- 노드의 수준 (level)
- 루트 노드는 level 0
- 노드에 도착하기 위해서 지나치는 간선의 수
- 노드의 차수 (degree)
- 자식(서브트리)의 수
- 리프 노드는 차수가 0
- 트리의 높이 (height) 또는 깊이 (depth)
- 트리의 높이 = 최대 수준(level) + 1
- 부분 트리 (서브트리, subtree)
- 트리에서 어느 한 노드를 기준으로 잘라냈을 때 나눠지는 부분
-
이진 트리 (binary tree)
- 모든 노드의 차수가 2 이하인 트리
- 재귀적으로 정의할 수 있음
- 빈 트리이거나, 루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리
- 단, 이 때 왼쪽과 오른쪽 서브트리 또한 이진 트리
-
포화 이진 트리 (full binary tree)
- 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리
- 높이가 k이고 노드의 개수가 2^k - 1인 이진 트리가 된다
-
완전 이진 트리 (complete binary tree)
- 높이 k인 완전 이진 트리는
- 레벨 k-2 까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리이고
- 레벨 k-1 에서는 노드가 순차적으로 채워져 있는 이진 트리
본 문서는 프로그래머스 어서와! 자료구조와 알고리즘 강의를 수강하고 정리했습니다.
