이진트리 (binary tree)
1. 완전 이진트리(complete binary tree)
- data가 빠짐없이 들어가 순서대로 정렬된 형태의 트리
- data는 왼쪽부터 오른쪽으로 하나씩 들어간다.
- Heap 구조
- root 노드로 갈 수록 최대값을 가지거나(최대힙), 또는 최소값(최소힙)을 가지는 형태의 tree
- Heap 구조의 시간복잡도
- O(NlogN), N개의 노드에 대해서 한번씩 검사를 진행하고, 트리의 노드가 아래로 2의 배수로 늘어나기 때문에 log(2)N 만큼 걸리기 때문에 최종적으로 O(NlogN) 이라고 할 수 있다
초심자