tree 구조 내용 정리
tree(트리)의 개념 및 특징
tree는 노드로 이루어진 자료 구조로, DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류이다.
- 단 하나의 root node를 갖는다.
- node들과 이들을 연결하는 edge들로 구성되어 있다.
- directed graph이자 acycle graph이자 connected graph다. 즉, 방향성이 있으며 순환하지 않고 하나로 연결된 graph다.
- 두 개의 node 사이에는 반드시 1개의 경로만 존재한다. root node에서 임의의 node까지 가는 경로도 단 하나만 존재한다.
- root node는 0개 이상의 children node를 가지며, 그 children node 역시 0개 이상의 children node를 가진다. 이것이 반복적으로 정의된다.
- node가 n개인 tree는 항상 n-1개의 edge를 가진다.
- 1개의 root node만 존재하며 모든 children node는 1개의 parent node만 가진다.
tree와 관련된 용어
- root node(루트 노드): parent가 없는 node, tree는 단 하나의 root node만 가진다.
- leaf node(단말 노드, 잎 노드): children이 없는 node
- internal node(내부 노드): leaf node가 아닌 node
- edge(간선): node를 연결하는 선, link, branch라고도 한다
- sibling(형제): 같은 parent를 가지는 node
- size(노드의 크기): 자신을 포함한 모든 children node의 수
- depth(노드의 깊이): root node에서 어떤 node로 가기 위해 거쳐야 하는 edge의 수
- level(노드의 레벨): tree에서 특정 depth를 가지는 node의 집합
- degree(노드의 차수): 하위 node의 수 또는 edge의 수
- degree of tree(트리의 차수): 트리의 최대 degree
- height(트리의 높이): root node에서 가장 깊숙히 있는 node의 depth
- sub tree(서브 트리): root node에서 뻗어 나오는 큰 tree 내부에, tree 구조를 갖춘 작은 tree
Tree 종류
Binary Tree(이진 트리)
binary tree가 될 조건
binary tree가 될 조건은 아래와 같다.
- 각 node가 2개 이하의 children을 갖는다
- root node가 단 1개다
- root node와 다른 node 간의 경로가 단 1개로 유일하다
binary tree의 종류
Full binary tree(= strictly binary tree, 전 이진 트리)
- 모든 node가 0개 또는 2개의 children node를 갖음
complete binary tree(완전 이진 트리)
- 마지막 level을 제외하고 모든 level이 완전히 채워져 있음
- 마지막 level은 꽉 차지 않아도 되지만, node가 왼쪽에서 오른쪽으로 채워져야 함
- 마지막 level인 h에서 1 ~ (2h - 1)개의 node를 가질 수 있음
- 마지막 level의 leaf node가 제거된 perfect binary tree라고 할 수 있음
perfect binary tree(포화 이진 트리)
- 모든 node가 2개의 children node를 갖음
- 모든 말단 node가 동일한 height 또는 level르 갖음
- node의 전체 개수가 $ 2^{k-1} $개임
- complete binary tree이면서 full binary tree임
binary search tree(이진 탐색 트리)
- parent node보다 작은 node는 왼쪽에, 큰 node는 오른쪽에 위치함
- binary search와 linked list를 결합함
- 기존 binary tree보다 탐색이 빠르다는 장점이 있음
- height가 h라면 시간 복잡도는 O(h)임
Max Heap(최대힙)
- tree의 마지막 level에서 왼쪽 node가 모두 존재하는 complete binary tree
- (parent node의 value) $ \geq $ (children node의 value)
- 가장 큰 값은 root node의 key
- n개가 힙에 들어가 있으면 높이는 $ log(N) $
Min Heap(최소힙)
- (parent node의 value) $ \leq $ (children node의 value)
Tree traverse(순회)의 종류
traverse 방식
-
Pre Order Traversal(전위 순회)는 parent node인 N이 가장 먼저 오는 방식
-
In Order Traversal(중위 순회)는 N이 가운데에 오는 방식
-
Post Order Traversal(후위 순회)는 N이 가장 마지막에 오는 방식이다.
traverse 구현
Recursive하게 구현
Iteravtive하게 구현
tree include
tree가 target node를 포함하고 있는지 아닌지 판단하는 문제
tree sum
tree에 있는 모든 node들의 value를 더하는 문제
tree min value
tree에 있는 모든 node들의 value 중 최솟값을 구하는 문제
시간복잡도가 $ O(n^2) $이므로 그리 빠른 알고리즘은 아니다.
Maximize path sum from root to leaf
