Please enable JavaScript.

Coggle requires JavaScript to display documents.

D.S (Tree (Advance tree (支援 double-end priority queue (皆支援操作 (delete max,…

- - - - Min-Max Heap
        
        定義
        
        Level 是以 Min-level 與 Max-level 交替呈
        
        root位於min level
        
        Complete B.T
        
        若x 位於min level 則代表以x為root之子樹x具有最小值
      - Deap
        
        定義
        
        Complete B.T
        
        min-heap 相對位置data <= max-heap data
        
        root 不存data, root 左子樹為min-Heap, 右子樹為 max-heap
      - Symmetric Min-Max Heap
        
        定義
        
        左兄 <=右兄之值
        
        若x有祖父,則祖父的左子點必須小於x
        
        Complete B.T
        
        若x有祖父,則祖父的右子點必須大於x
      - 皆支援操作
        
        delete max
        
        detele min
        
        insert X
    - - E=I+2N
      - WEPL(weight external path length)
        
        Min WEPL
        
        Hoffman Algo
    - - 最多Node數
      - 最多key樹
      - B-tree of order m
        
        If not empty, root 的degree 在2到 m
        
        除了 root 即Failure Node之外,其餘的Node degree 在 2/m <= degree <= m
        
        所有的failure node必須在同一level (balance)
        
        相關數學
        
        最多key數
        
        最多Node數
        
        最少key數
        
        最少node數
        
        操作
        
        Insert
        
        split
        
        Delete
        
        rotate
        
        combine
    - - 定義
        
        balanced B.S.T, balanced B.S.T, if not empty
        
        不得連續兩個紅Node
        
        Node 非黑即紅, root為黑,Nil為黑
        
        root 到不同leaf 之 Path 上,皆具有相同的黑色nodes(balanced)
        
        Horowitz 版本
        
        是 2-3-4 Tree, 對應的 BST,滿足
        
        若此Link在 2-3-4 Tree 已存在,則視為黑link,,否則為紅link
        
        任何path不得有兩續兩個紅link
        
        Link 非黑即紅
        
        root到leaf path皆具有相同數目的黑色link
      - 操作
        
        insert
        
        color change
        
        rotate
        
        delete
    - - 定義
        
        n個內部node,加權值,令為Pi , 1<=i<=n
        
        n+1個外部node,加權值,令為 qi,0<=i<=n
        
        在所有不同BST中具有最小搜尋總成本之BST稱之(可能>1 顆)
      - Ci,j 公式
    - - Shortest(x) Path
        
        0, external node
        
        1+ min(Shortest(x->left,x->right))
      - 定義 Leftist Heap
        
        對於任何 Node shortest(X->leftchild) >= (X ->rightchild) (leftist tree)
        
        是一個 min-tree
      - 操作
        
        merge-two leftist heap
        
        delete min
        
        insert node
    - - Binomial tree
        
        令root 的level為0
        
        Bk:代表k高度的binomial tree,是由兩個高的為k-1的Bk-1所組成,任一個bk-1為new root , root , 另一棵bk-1為其子樹
        
        B0:代表高度為0 的 Binomial tree, 只有root一個點
        
        相關公式
        
        Bk的第i level level的node數
        
        Bk的node總數
      - 由一群binomial tree 組成之集合 (Forest),且必須為min-tree
      - 操作
        
        delete-min
        
        insert node
        
        Merge two binomial heap
    - - Binomial Heap的super set 又稱 extended Binomial Heap
      - 操作
        
        Delete node
        
        Decrease key of a node
  - - - 定義
        
        可以為空
        
        若不為空
        
        有root及左右子樹
        
        左右子樹也是B.T
      - 差異:二元樹可為空,0<=Node's Degredd<=2 , 0<=Node's Degredd<=2 , 子樹有方向性
    - - 高度為k之B.T,最多Node數 = (2的k次方)-1
      - 針對非空之B.T令Leaf 個數為No個, Degree 為2之Node數為 n0 = n2+1
      - 第level i 的子樹最多＝ 2的(i-1平方)
    - - Full B.T
        
        具有最多Nodes數之B.T
      - CompleteB.T
        
        高度為K之B.T 節點數 = n
        
        Node 編號由上而下由左而右依序增長
        
        2的(k-1次方)-1<n<=(2的k次方) -1
      - Skewed B.T
      - Strict B.T
        
        B.T中任何 Non-leaf 皆有兩個child
    - - 中序
        
        LDR
      - 後序
        
        LRD
      - 前序
        
        DLR
      - Level Order
    - - Array
      - LinkedList
  - - - 方法
        
        刪除父點與子點連結,但是保留the leftest node
        
        將連結向左轉45度
        
        建立sibling連結
    - - 浪費鏈結空間
        
        有用的 link n-1
    - - child: pointer指向leftmost-child only
      - sibling:指向Next-right-sibling
    - - 父點(子點......子點)
  - - - 父點 >= 子點 (Max Heap)
      - complete B.T
    - - 製作priority Queue
      - Heap Sort
      - Insert Element And Delete Max
      - Build Heap
        
        Top-Down
        
        Bottom-Up
    - - Delete-Max
      - Insert
    - - Botton-up
        
        O(n)
      - Top-down
        
        O(nlogn)
  - - - 將root平行串接
      - root們順時針旋轉45度
      - 每棵樹皆化成二元樹
  - - - 多個互斥的Set組合而成
    - - Kruskal's algo 求 min ,spanning tree,判斷邊(i,j)加入S中是否會形成Cycle
      - 根據等位配對找出等位集合
    - - 主要是每個Set皆用一棵Tree來表示
        
        Linkedlist
        
        Array
      - 操作
        
        Union(i,j)
        
        聯集Seti,Setj
        
        Find(x)
        
        找出元素x位於哪個set,傳回該set之root
        
        組合
        
        Union-by-Height 與 simple-find
        
        Union-by-Height 與 find-with-path-compression
        
        Union與simple-find
  - - - 左引線指向中序前一個節點
      - 右引線指向中序後一個節點
  - - - Binary Search Tree
        
        Def
        
        若不為空 Root 左子樹Node 值均小於root
        
        若不為空 Root 右子樹Node 值均大於root
        
        屬於B.T
        
        若不為空左右子樹皆為 Binary Search Tree
        
        search
        
        應該無重複data
        
        sorting
        
        需決定值相同的Data要放在何處
        
        將input 建立B.S.T
        
        中序traversal 即可sorting
        
        結構受input order 影響 , 可能變 skewed Tree
        
        操作
        
        delete
        
        degree = 2 node
        
        挑選最左邊最大之節點或最右邊最小節點取代父點,視原本節點為 leaf或 degree-1之節點依照case1 or case2處理
        
        degree = 1 node
        
        delete then 子點代替父點
        
        leaf-node
        
        only delete
        
        Balanced BST
        
        AVL tree
        
        if not empty, 左右子樹高度不能高過一
        
        左右子樹也必須為AVL tree
        
        四項調整
        
        RR LL 一次rotate
        
        RL LR 兩次rotate
        
        形成AVL最少Node數
        
        Black Red Tree
        
        if not empty, 節點為黑紅節點所組成
        
        Root為黑節點
        
        不能有兩個相臨紅節點
        
        Root 到不同Leaf Path 上皆具有相同的黑色Node
        
        Treap
      - m-way Search Tree
  - - - 給予中序+前序(後序)畫出二元樹
      - 寫出前、中、後序 Recursive algo
      - 寫出前中後序
      - Recursive algo for B.T 應用
        
        Count B.T Node數
        
        求B.T高度
        
        判斷 Equal
        
        Swap a B.T
        
        Copy a B.T
        
        用B.T表示expression,對此B.T求值
        
        利用Tree作Sorting
        
        m-way Search Tree
        
        Binary Search Tree
- - - - Circular(用n-1格)
      - Circular(用n格)
      - Linear
    - - single LinkedList
      - Circular LinkedList
  - - - Stack模擬Queue
        
        兩個Stack
      - Queue模擬Stack
- - - - strongly connected component
      - 出支度
        
        邊數與degree關係
      - 入支度
        
        邊數與degree關係
    - - strongly connected
      - 分支度
        
        邊數與degree關係
  - - - 允許有負邊,但不能有negative length of cycle
      - Dynamic Programming
    - - all-pair-of-vertex
    - - 限制:不能有負邊
      - Greedy
  - - - 若自B中取一邊加入S,必定會形成cycle
      - 在S中,任何頂點對之間,只存在一條simple path
      - E = T+B (Tree edge,Back edge)
    - - Prim's
      - Kruskal's
      - sollin's algo
- - - - 固定空間
      - 變動空間
    - - Big-Oh(O)
      - Omega(Ω)
      - Theta(θ)
      - Little-oh
      - Little-Omega(ω)
  - - - 主要看遞回來寫時間複雜度
    - - Extended Master Theory
      - Recursive Tree
        
        計算每層成本是否相同
        
        相同(每成本 * logn) >>>Level cost X log(n)
        
        不相同且<=第一層level成本 >>> 第一層level cost
      - Master Theory
      - 特徵方程式
      - 展開帶入法
      - 猜測近似法則
      - 無法使用MasterTheory之特殊例子
- - - - 判斷括號字串
      - 判斷輸入字串是否為palindrome
    - - 公式(背)
      - 可能問法
  - - - push(S,item)
      - pop(s)
    - - push(S,item)
      - pop(s)
  - - - 優先權高低(背)
      - 步驟(背)
- - - - 是由B個bucket,每個bucket有S個Slot所組成
  - - - 減少collide
      - 避免局部儲存的狀況(uniform)
      - 計算簡單
    - - divisions
        
        兩個原則
      - folding additions
        
        shift
        
        boundary
      - middle square
      - digital analysis
    - - Double Hashing
        
        解決 secondary clustering
        
        table不保證充分利用
      - chaining
        
        close addressing mode
        
        hashing 可作 sort方法
      - Qrodratic Probing
        
        解決 primary clustering
        
        table不保證充分利用
        
        易發生secondary clustering 現象, 增加searching time
      - rehashing
      - Linear Probing
        
        簡單,易實施,table可充分利用
        
        容易有primary clustering, 及相同hashing address 會儲存在附近的bucket中,增加searching time
- - - - interactive
      - recursion
- - - - Divide(Partition) and Conquer
      - Hoare Partition
      - QuickSort(A,m,n)
      - Best case : O(nlogn)
      - Worst case : O(n2)
        
        randomise-quicksort
        
        median-of-midian
        
        middle of three
      - unstable
    - - Algo
        
        Insert (A,r,i) 副
        
        Insert(A,n) 主
      - Time Complex
        
        Worst :O(n2)
        
        Best:O(n)
      - Stable
      - 改善
        
        Linear Insertion Sort
        
        Binary Insertion Sort
    - - stable
      - Time Complexity
        
        Avg:O(n2)
        
        Worst :O(n2)
        
        Best:O(n)
    - - 自第 i 筆到 n ,select min 與 A[i] 做swap
      - Algo
        
        select-sort(A,n)
      - 適合用在大型資料上,每一回合只swap一次
      - Time Complexity
        
        Best, Avg, Worst :O(n2)
      - unstable
    - - 步驟
        
        Botton-Up 建 tree
        
        Delete Max
        
        Heapify
      - Best,Avg,Worst : O(nlogn)
      - unstable
    - - 常用於external sort
      - 方法
        
        Iterative
        
        Recursive
      - Best/Avg/Worst
        
        O(nlogn)
      - stable
      - selection tree
        
        winner tree
        
        O(n)+O(nlogK)
        
        loser tree
        
        O(n)+O(nlogK)
        
        只需與Parent比較
        
        無 selection tree
        
        O(n*k) k個run,n個data
    - - unstable
      - Time Complexity
        
        Avg:O(n2)
        
        Worst:O(n2)
        
        Best: 尚無定論
  - - - O(n+k)
        
        stable
    - - LSD radix sort
        
        O(d*(n+r)) d:回合, n:data, n:data數, r:bucket數
        
        stable
      - MSD radix sort