[30일코딩] Heaps and Binary Search
Graphs & Trees
<Basics>
1) Root / Node / Leaf
루트 노드에서 시작 각 노드들로 이동한다.
루트가 아닌 자식이 없는 노드는 leaf node 라고 부른다.
2) Binary: Left and Right
각 node는 최대 2개의 노드 left, right child만 가진다.
3) Parent / Children
부모 노드와 자식 노드 순서가 있고
이것은 나무 일부분을 이룬다. sub-tree
4) Recursive
그리고 이 sub-tree 들은 반복된다.
5) Height of Trees
https://www.tutorialspoint.com/data_structures_algorithms/tree_data_structure.htm
Heap
힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된
완전이진트리(Complete binary tree)를 기본으로 한 자료구조(tree-based structure)
- Min-Heap
Root node 가 모든 노드의 최대값
- Max-Heap
Root node 가 모든 노드의 최소값
Binary Search Tree (BST)
- nonEmptyBST
- EmptyBST
EmptyBST 시작,
nonEmptyBST 에서 data 따라 left,right 분류
Path Finding Algorithm
- Breadth First Search
같은 level은 모두 훝고 가기 A- BCD - B'C'D'
- Depth First Search: A-B-B'
parent-child path 따라 깊게 가기