개발입문/JAVA

[30일코딩] Heaps and Binary Search

haloaround 2017. 5. 9. 11:40

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