Tree
- 노드 간 부모-자식 관계와 루트 노드를 가지는 그래프 => 계층 관계를 표현하기에 적합
※ 그래프 = 노드와 노드 간을 연결하는 간선(branch)으로 구성된 자료구조
- 자식 노드는 단 하나의 부모 노드만을 가질 수 있고 부모 노드는 여러 개의 자식 노드를 가질 수 있음
- 비선형 구조, 방향성 존재, 비순환 그래프
- 루트 노드(맨 위), 내부 노드(중간), 리프 노드(맨 밑, 자식이 없는 노드)
이진 트리(Binary Tree)
- 자식 노드의 개수가 2개 이하인 트리
- 탐색 속도 = O(logN)
- 이진 탐색 트리(BST, Binary Search Tree) = 이진 탐색 + LinkedList가 결합된 구조로 왼쪽 자식 노드에는 부모 노드 보다 작은 값이 오른쪽 자식 노드에는 부모 노드 보다 큰 값이 들어 있는 이진 트리
=> 탐색 속도가 이진 트리 보다 빨라지지만 트리가 균형이 잡히지 않을 경우 O(N)의 시간 복잡도를 가짐
- 완전 이진 트리 = 노드가 왼쪽부터 채워져 있고 리프 노드를 제외한 모든 노드가 채워져 있는 이진 트리
힙(Heap)
- 최댓값 및 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전 이진 트리 기반 자료구조
- 시간 복잡도 = O(NlogN)
- 최소 힙(Min Heap) = 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 (루트 노드가 최소)
- 최대 힙(Max Heap) = 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 (루트 노드가 최대)
