簡單的就直接空白了…
資料結構 Data Structure
List
Array
Stack: LIFO
Queue: FIFO
Hash Table
Heap
- Priority queue
- 保證父節點比子節點小，不保證左右的大小關係
- Balance. 所以當取出 root 或新增 node 時，都是以最右下角的位置為對象。新增 node 時是新增在最右下角的空位，再一路往上與父節點比較看是非需要調換；取出 root 時，把最右下角的 node 移到 root，比較兩個子節點，與 3 者中最小者調換
Binary Search Tree
- 保證每一個 subtree 的右側一定大於左側
- 非 balance
- 新增一定都成為葉節點
- 刪除時若該節點有子節點，則把從左子樹最大值取上來，左子樹最大值就是其最右下的葉節點
- 因為非 balance，所以蒐尋時間不一定。若平衡，為
O(log n)；若極度不平衡成一條線，那就是O(n)。
Self-balancing Binary Search Tree
AVL Tree
- 不平衡時會做 rotation，維持在平衡的狀態，可避免 BST 退化為鏈狀。rotation 前後 in-order traversal 順序相同。
- 每一個節點需要維持其高度資訊：先為樹補上所有 null 葉節點，null 節點高度為 -1，其他節點是其子節點較大者 +1
- 每一個節點需要計算其 Balance Factor (BF) ：左子節點的高度減右以節點的高度。所以若 BF 為負，代表右子樹比較大棵。需要注意若只差 1 還是容許的平衡狀態。
- Rebalance
- 當新增一個節點，整條路上的節點的高度資訊要更新。然後，從新節點往根部方向走兩層，也就是走到新結點的爺爺節點，看爺爺的 BF 是否小於 -1 或大於 1，如果是，那就代表要 Rebalance。怎則做 Rebalance 取決於剛剛怎麼從新節點走到爺爺的路，如果一路走左分枝上來，就是 LL，一路走右分枝就是 RR，同理還有 LR 和 RL，四種形態有對應的旋轉方式。
- 當刪除一個節點，不管是把其左子樹最大值補位上來，還是把右子樹最小值補位上來，都是要整棵樹檢查。整棵樹檢查方式是任意挑一個頁節點往上檢查即可，如果一路到根部，都沒有出現 BF 小於 -1 或大於 1，那就平衡。若一旦發現就要根據其路徑立即做 LL/RR/LR/RL 對應的旋轉方式。旋轉完成後再從頭檢查一次，直到某次一路檢查到根部，都沒有出現 BF 小於 -1 或大於 1。
Red Black Tree
- 也是自平衡的 BST。AVL Tree，為了平衡會要經過好多次旋轉，而 RB Tree 的結構設計，使得任何不平衡都會在三次旋轉之內解決。
- 然而嚴格上來說紅黑數只是幾乎平衡的 BST，因為他只保證「從 root 出發抵達葉節點的最長徑不會超過最短的兩倍」
- 藉由以下 5 項特徵
- 紅黑樹中的每一個節點不是黑色就是紅色
- 根節點一定是黑色
- 原本葉節點的 NULL 指標都另外新增補個葉節點給他，然後最終每一個葉節點一定是黑色
- 如果某個節點是紅色，那麼其兩個子節點必定是黑色，不能有兩個紅色節點相連
- 站在任何一個節點上，所有從該節點走到任意葉節點路經的黑色節點數必定相同
- 根據上述特徵的第 4 點與第 5 點，紅黑樹中路徑可能的長度最小值一定是全部節點皆為黑色，而路徑可能的長度最大值一定是紅色黑色相間，如此便確保最長路徑不會超過最短路徑的兩倍的特性。
- 新稱或刪除資料，都會根據節點位置有不同得對應方式，包含些修正一些節點的顏色，以及旋轉，但旋轉都是在三次以內，即可將其修正成符合紅黑數特徵。
排序 Sort
Bubble sort
- 每次看相鄰 2 個數，確保左邊小於右邊，從最右側開始每次向左滑 1 單位，如此當回滑到最左側時，左手的值就是整串數列的最小值，這樣是一輪
- 時間複雜度是
O(n*n)，因為預期比較動作就是進行 n!，但可以做的優化是如果有某一輪完全沒做 swap，那就可以終止。所以會得到 best case 是O(n)，就是在原本就已經排好的狀況
Selection sort
- 一次把數張撲克牌攤開在手上，最直覺的排法就是，眼光從作掃到右，挑出其中最小的，移到最左邊
- 時間複雜度是
O(n*n)
Insertion sort
- 一張一張把撲克牌拿起來，插到對的位置。如果用 array 來看，就是以最左邊為起點，往右一個一個加進來到對的位置
- 時間複雜度是
O(n*n)，因為預期比較動作就是進行 n!。best case 是O(n)，就是在原本就已經排好的狀況，每當多看一個數，都發現其大於左側已確定的數列中的最大值，也就是每一輪的第一次比較就發現本輪結束
Heap sort
- 創造 heap 需要
O(n log n)，因為有 n 個數，而插入每個數的預期時間與高度相關 - 從 heap 取出每次都取 root，但 heap 要因此調整，時間是
O(log n)，所以全部取完是O(n log n)
Merge sort
- 把數列兩兩一組，完成排序後，再把兩組合併。合併方式為比較兩組當中最左側的值，將較小者取出。這樣為完成一輪
- 時間是
O(n log n)，因爲每輪各組總共 n 次比較，而總共有 log n 輪
Quick sort
- 隨機選取 pivot，把比 pivot 小的放一邊大的放一邊。再對左右兩邊做相同處理
- 如果運氣好 pivot 選得好，造成每次左右兩邊數量一樣，那時間就是
O(n log n)；如果運氣不好，造成每次的都只有的單邊，那時間就是O(n*n)
搜尋 Search
[Array] Linear search
從左到右，所以不管原本的數列是已排列或未排列
[Array] Binary search
僅用於已排列，每次與中間位置比較，所以搜尋時間是 O(log n)
[Graph] BFS 廣度優先 Breadth First Traversal
- 原本 queue 裡只有 root，把他取出，如果不符合欲搜尋對象，就把其子節點他們全部推進 queue 裡，這樣為一輪。之後再從 queue 取出一個進行下一輪
- 圖中有迴圈的情形也適用
- 1 2 3 4 5
[Graph] DFS 深度優先
- 換成搭配 stack
- Inorder traversal：造訪順序為 左 -> 中 -> 右 (4 2 5 1 3)
- Preorder traversal：造訪順序為 中-> 左 -> 右 (1 2 4 5 3)
- Postorder traversal：造訪順序為 左 -> 右 -> 中 (4 5 2 3 1)
[Graph] Bellman-Ford 找出最短路徑
- 把起點設為 0，其他點暫設為無限大
- 工作對象是「所有的邊」，每一輪都是把所有的邊都看一次，看邊上的兩點，從 A 到 B 或從 B 到 A 的值，是否可以更小
- 只要每一輪都還有更新任一點的值，都代表還要進行下一輪，直到某一輪完全沒有更新任何點上的值時結束，此時終點上的值就是最短路徑
- 若有
v個點，e個邊，時間為O(ev)。原因是每一輪都要檢查 e個邊，而最多能跑幾輪？
在第 1 輪結束後，得到的是起點最多經過一條邊到達其他點的最短距離；第 2 輪結束後，得到的是起點最多經過兩條邊到達其他點的最短距離；那要到底幾輪才會是到終點的最短距離呢？
圖中任兩點的最短距離，頂多經過 v-1 個邊，也就是從起點途經所有點才抵達終點的狀況。因為如果某一點造訪兩次，那代表有迴圈出現，這基本上純粹成本增加
如此說來，第 v-1 輪結束後，得到的是起點最多經過 v-1 條邊到達其他點的最短距離，有就是我們最多需要執行的輪數，所以總時間為O(ev) - 負數邊和圖中有迴圈皆可用，但若同時有負數邊和迴圈，則會出現迴圈一直跑就成本一直遞減的狀況，所以最短路徑其實不存在，也就是說當執行輪數到達 v 卻還有值能更新時，即可判斷為最短路徑不存在
[Graph] Dijkstra’s 找出最短路徑
- 把起點設為 0，其他點暫設為無限大
- 工作對象從起點開始，更新起點的相鄰點上的值，如此為一輪
- 從目前看過的點中，選擇值最小者，作為第二輪的開頭
- 如此重複，直到選擇到終點為工作點為止
- 若有 v 個點 e 個邊，時間為
O(v\*v)。原因是每一輪結束，都會確認下由起點到達某一點的最短路徑。總共可有 v-1 個點要確認，所以要進行 v-1 輪。而每一輪，要把當前工作點所一步能及的所有相鄰點做更新，每一點的相鄰點可為 v-1，所以總共是O(v*v) - 與
Bellman-Ford比較：v 個點最多能有 v*(v-1)/2 個邊，且 v 大多數時候小於 e，所以 vv 大部份時候小於 ve，所以Dijkstra’s比較快，尤其是稀疏圖的 v 就是偏小的時候。而且若Dijkstra’s的實作使用 Fibonacci heap 存圖，則時間複雜度可提升到O(e + v log v) - Greedy 在每一輪得到從起點到某一點的最短路徑，所以這也造成無法處理有負數邊的狀況。因為每一輪都只能看到目前所看過的點和邊，如果是還沒看到的邊而且為負數邊，那就會造成以為已經得到到從起點到某一點的最短路徑但其實不然，因為未來某負數邊的加入會改變這一結論。（無法處理負迴圈，但可以處理迴圈）
[Graph] A* 找出最短路徑
A* 是 Dijkstra’s 的發展，Dijkstra’s 每一輪會決定出從起點到某一點的最短路徑，但該點以結論來說，有可能根本不在最短路徑上，所以最終來看就是一種浪費
A* 導入了試探權重 heuristic cost，僅是一種人為的、根據其他已知客觀條件所給的推測、建議性質參數，在選擇下個點時提供幫助。在每一輪，每一點的試探權重與當前由起點抵達該點的成本相加，取其中最小者作為下一點，如果試探權重很符合真實狀況，那就會更快探索到終點並結束，但這並不見得是最佳路徑，因為根本有些點還沒被探索到，你無法確定是不是如果經過那些點會得到一條更佳的路徑，所以目前的到的結果只能說是考慮進試探權重的最佳路徑