tweety-666

資料結構與演算法 - overview of binary search tree

tags: 資料結構與演算法,Algorithms,Data Structure

binary search tree

時間複雜度

• 最差：O(n) 如果binary search tree剛好長成陣列的樣貌，也就是每個node都只有left child node，如果有n個node，那麼遍歷的時候，最差的情況下就得走n次。
• 最佳：O(1) 如果binary search tree剛好只有一個或沒有node，或是一串binary search tree中第一個node就是要找的node。最佳情況下，只要找一次。
• 平均：O(logn)

tweety-666

資料結構與演算法 - binary search tree traversal

tags: 資料結構與演算法,Algorithms,Data Structure

Binary Tree

一個root，每個node下面只有最多兩個node。

Binary Search Tree

一個root，每個node下面只有最多兩個node。大小順序為：left child node < node < right child node。

Breadth-first Tree Traversal

tweety-666

資料結構與演算法 - search in binary search tree

tags: 資料結構與演算法,Algorithms,Data Structure

recursively search

先從一個節點開始尋找，沒找到就再次提供該節點的左子節點跟右子節點，透過遞迴的方式繼續找。

interatively search

利用while的特性，沒有找到該節點就繼續找，直到比較的節點是null（代表沒有拿來比較大小的節點了）就停止。

tweety-666

資料結構與演算法 - insertion in binary search tree

tags: 資料結構與演算法,Algorithms,Data Structure

Graph概略

Graph是由一串node（也稱point或vertex）的有限集合，node之間也許有line（也稱link或edge）將node連在一起。如果line有方向性箭頭，稱為directed graph。

Tree

tweety-666

資料結構與演算法 - linear time sort and radix sort

tags: 資料結構與演算法,Algorithms,Data Structure

radix sort

radix sort又稱“桶子排序”，從個位數開始一直往更多位數比較大小，將要排序的元素分配至某些“桶子”中。

思考

1. 建立代表0~9的桶子。
2. 比較陣列中的每個數字的個位數。
3. 依序把數字放入桶子中。

tweety-666

資料結構與演算法 - linear time sort and counting sort

tags: 資料結構與演算法,Algorithms,Data Structure

linear time sort

線性排序的算法，不是基於比較的排序算法，都不涉及元素之間的比較。

counting sort

1. 只能對整數做排序
2. 有n個元素要排列，元素的範圍是0~k

tweety-666

資料結構與演算法 - quick sort

tags: 資料結構與演算法,Algorithms,Data Structure

pivot and partition

partition（劃分）是quick sort的主要概念。 將陣列根據一個pivot（基準點），將陣列劃分成兩個部分，分別是：比該基準點左邊的，跟比該基準點右邊的。

let pivot = 3 // 陣列中第3個為基準點
[A,B,C,D,E,F,G]
       ^基準點 

tweety-666

資料結構與演算法 - heap sort

tags: 資料結構與演算法,Algorithms,Data Structure

問題

請將一個任意的complete binary tree，轉換成max heap，再轉成一個array。 例如： let array = [3,12,14,7,1,13,10,5,9,4,11,8,15,2,6] 得出max heap：

tweety-666

資料結構與演算法 - insertion sort

tags: 資料結構與演算法,Algorithms,Data Structure

插入排序法

一個沒有排序過的陣列，將元素用「插入正確位置」的方式，使其排列正確。 很類似玩樸克牌或拉密時，整理手牌的時候會做的事情。

思考

就像在打樸克牌，拿起手牌，不斷往前找到適合的位置，等找到的時候就可以直接插入。陣列中迴圈拿元素跟前一個元素比大小，前一個比較大，就往前插入。

tweety-666

資料結構與演算法 - merge sort

tags: 資料結構與演算法,Algorithms,Data Structure

合併排序

還沒排序好的大陣列分成好幾個小小陣列，小小陣列各自比較大小後，排序好成一個小陣列，小陣列跟小陣列比較後，合併成一個排序好的大陣列。

divide and conquer

分割 -> 比較 -> 合併

divide and conquer的概念類似分組排名賽。