[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 따라 깊게 가기