Please enable JavaScript.

Coggle requires JavaScript to display documents.

資料結構 - Coggle Diagram

- - - - 保留順序，可用 index 取第 i 項
    - - insert/delete 會造成後方元素 shift
    - - ADT 管 what；array/linked list 管 how
    - - 封裝資料，只開放定義好的方法
  - - - list 存 PyObject reference，不直接存物件
    - - 配置更大陣列、複製、舊陣列 GC
    - - resize 單次 O(n)，平均攤銷 O(1)
    - - Node = data + next；不需連續記憶體
  - - - array O(1)；linked list 要從 head 走
    - - array 要 shift；已知 linked position 可 O(1)
    - - current = current.next 直到 None
    - - 排序涉及比較與搬移，不只是語法
  - - - 字元轉數字，加 shift 後 mod 26
    - - 新高分插入，低分往右移
    - - append 找尾端；remove first 更新 head
    - - 從 sorted portion 往左比較與插入
  - - - 資料有順序或歷史時優先考慮
    - - random access 是 array-based list 強項
    - - deque 兩端操作可 worst-case O(1)
    - - resize、shift、pointer 都是成本
- - - - membership testing、去重、聯集交集
    - - 不可 add/remove，適合穩定集合值
    - - add/update/remove/search/iterate
    - - 同 key 覆蓋舊值，hash 要穩定
  - - - deterministic，同 key 要回同 bucket
    - - 靠 bucket 定位，避免掃描全部資料
    - - 05 p.15：解法一 chaining
        
        bucket 存 entries 串列
        
        單一 bucket 最壞查找 O(n)
      - 05 p.15：解法二 open addressing
        
        碰撞後找下一個 open slot
        
        linear probing：index+1、index+2
    - - 負載太高 collision 變多，需擴充表格
  - - - bucket 內用 linked list/list 串接
    - - 不串列，往表內其他空格探測
    - - 平均 O(1) 會接近線性查找
  - - - 幾乎每格有值時，二維 list 直觀
    - - 用 (row,col) tuple 當 key
    - - 適合 JSON、profile、inventory
    - - 封裝 row/column 存取，像容器一樣操作
  - - - hashing one-way；encryption two-way
    - - dict subclass，key 是元素、value 是次數
    - - default、順序、合併 mapping 視角
    - - set 去重；dict 查詢；hash 驗檔
- - - - root 沒有 parent，是深度計算起點
    - - 同一 parent 的 children 互為 sibling
    - - internal 有 child；leaf 沒有 child
    - - path 是節點序列，用方向判斷祖先後代
    - - left-root-right 得到遞增 key
  - - - root depth = 0，往下一層加 1
    - - leaf height = 0；樹高影響搜尋
    - - 包裝 node，避免直接碰實作細節
    - - root、parent、children、is_leaf 等介面
  - - - 沿分支走到底，再回到下一分支
    - - 用 queue，先拜訪同一深度
    - - preorder 先 root；postorder 後 root
    - - 插入順序會影響 BST 高度與成本
  - - - left/right 有順序，可表決策或運算式
    - - root=0；parent=floor((i-1)/2)
    - - 小於 root 往左，大於 root 往右
    - - 平衡 O(log n)，退化鏈狀 O(n)
  - - - Python 無內建通用 tree，可用 bigtree
    - - print_tree、tree_to_dict、tree_to_dataframe
    - - 適合階層關係，不是單純線性資料
- - - - connected、undirected、weighted graph
    - - 保留 V-1 條邊，讓所有 vertex 連通
    - - cycle 代表有多餘邊，不再是 tree
    - - network design、clustering、approximation
    - - key 最小權重；parent 來源；mstSet 防 cycle
  - - - 從一個起點逐步擴張 MST
    - - 一端在 MST、一端尚未加入才可選
    - - 搭配 priority queue 可到 O(E log V)
  - - - 依 weight 由小到大，是 global greedy
    - - 同集合會成 cycle，該邊捨棄
    - - find 找代表；union 合併集合
    - - 壓平路徑、按 rank 合併以降成本
  - - - 比較左右高度，null height = -1
    - - 允許差 1，避免過度頻繁旋轉
    - - LL 右旋；RR 左旋
    - - LR 左再右；RL 右再左
  - - - 最後一層由左到右填，利於陣列存
    - - min 根最小；max 根最大；siblings 不必排序
    - - push 上浮；pop 移根後重建 heap property
    - - priority queue 讓最高優先或最低成本先處理