某储备粮的“学习笔记”

by 咳嗽di小鱼

AVL Tree性质:
  • BST基础性质
  • 左侧和右侧subtree的height最多差1
  • 空白Tree的高度为-1
  • Search, Insert, Delete Runtime均为Θ(log n)

AVL Insertion:
  1. 执行标准BST Insertion
  2. 从新insert的leaf开始, 从下往上更新balance factor(左右高度差)
  3. 如发现高度差超过1(即为2), 则执行fix

AVL Fix: 修复高度差为2的subtree
  • Single rotation: 当height最高的leaf位于最左侧/最右侧
    • 将subtree的root Z向height较低的方向旋转, 即以height较高的child Y为root
    • Y原内侧child, 并入Z内侧

    AVL_single_rotation.png
  • Double rotation: 当height最高的leaf位于Tree内侧
    • 将height较高的root child向外侧旋转, 将Tree变形为Single rotation的初始形式
    • 执行Single rotation

    AVL_double_rotation.png

2-3 Tree性质:
  • BST基础性质
  • 每个node包含一个KVP*和两个children, 或者包含两个KVP和三个children.
  • 所有leaf都在同一层(level)

2-3 Tree Insertion:
  1. 找到KVP应在的leaf (BST规则)
  2. 如果该leaf已经饱和 (已经包含两个KVP), 则将3个KVP排序a < b < c.
  3. 将a和c分割成两个单独的leaf, 并将b插入到parent中.
  4. 重复第2步直到符合2-3 Tree所有性质

2-3 Tree Deletion: 删除x
  1. 如果x所在的node有两个KVP, 则直接删除x
  2. 如果同parent下, 与该node相邻的child有两个KVP, 则用node与child之间的parent替代x, 并用中间值替代parent
  3. 否则 (同parent下, node相邻child均只有一个KVP), 将相邻child与parent(中间值)合并. 重复直到Tree符合要求.

B-Tree性质:
  • 扩展版的2-3 Tree
  • 每个node包含最多2d个KVP
  • 非root的node最少包含d个KVP
  • 2-3 Tree的d = 1

Insertion和Deletion与2-3 Tree大同小异

注: 此B-Tree定义不完全符合11W Slide

备注: KVP意为Key-Value Pair, 即Key与Value的一对, 为一个KVP.

今天先到这里了...明天总结后半部分`= =


更多CS 240总结请看: http://blog.gregwym.info/tag/cs240/


Comparison-based sorting

最优Runtime为Ω(n log n)

QuickSelect

用QuickSort algorithm快速查找第k大的数 (avg rumtime: Θ(n))

组成函数

  • choose-pivot(A) 在数据中选择其中一个作为pivot
  • partition(A, p) 使用A[p]作为pivot, 将A中的数据分为

    • 所有小于等于pivot的数据
    • pivot本身
    • 所有大于pivot的数据

Implementation

下载: quickselect.cc

void swap(int *A, int i, int j){ 
    int temp; 
    temp = A[i]; 
    A[i] = A[j]; 
    A[j] = temp; 
    return; 
}

Read more...


Priority Queue 的基础操作:

  • insert: 在Queue中加入一个带有对应优先级的item
  • deleteMax: 移除优先级最高的item (此操作仅适用于maximum-oriented priority queue)
  • deleteMin: 移除优先级最低的item (此操作仅适用于minimum-oriented priority queue)

三种Implementation:

  1. 无序array (selection sort)

    • insert: O(1)
    • delete: O(n)
  2. 有序array (insertion sort)

    • insert: O(n)
    • delete: O(1)
  3. Heap (一种BST)

    • insert: O(log n)
    • delete: O(log n)

Heap的性质:

  1. 从上到下, 从左到右, 必须在一层(level)填满以后再使用下一层
  2. parent的优先级必须大于等于(小于等于 for min-heap)其children的优先级
  3. Heap的高度是Θ(log n)

Heap Insertion:

  • 将新item放入第一个空闲的位置 (参考heap的第一条性质)
  • 对其执行bubble-up, 直到符合所有heap性质
    #bubble-up:



    while [parent(v) exists and key(parent(v)) < key(v)] do 
        swap v and parent(v) v <- parent(v)
    

Heap deleteMax/Min:

  • 用heap中的最后一个item取代root
  • 对其执行bubble-down, 直到符合所有heap性质



    bubble-down



    while [v is not a leaf] do 
        u <- child of v with largest key 
        if key(u) > key(v) then 
            swap v and u v <- u 
        else 
            break
    

Heap array的特点 (当前item的位置为i):

  • Left child位于2i+1
  • Right child位于2i+2
  • Parent位于floor[(i-1)/2]

建立heap的两种方法:

  • 以空heap为起始, 逐个item执行insert
  • 以含有n个item的array为起始, 从index为floor[(n-1)/2]的item开始, 逐个执行bubble-down, 直到index 0

注: 使用第二种方法建立heap, 然后执行k次deleteMax/Min, 可快速查找array中第k大的iterm. 运行时间为Θ(n + k log n)

其他方法请参考: 找数组/VECTOR内第K大的数

更多CS 240总结请看: http://blog.gregwym.info/tag/cs240/


Runtime的符号

  • Big-O 表示当c和n0在达到一定大小以后, runtime小于等于某一数级[g(x)]
  • Little-O (与Big-O对应) 表示当c和n0为任意值时, runtime一定小于某一数级[g(x)]
  • Ω 表示当c和n0达到一定大小以后, runtime大于等于某一数级[g(x)]
  • ω (与Ω对应) 表示c和n0为任意值时, runtime一定大于某一数级[g(x)]
  • Θ 为同时满足Big-O和Ω

常见的Runtime数级
  • Logarithmic (log n)
  • Linear (n)
  • Linearithmic (n log n)
  • Quadratic (n^2)
  • Cubic (n^3)
  • Exponential (2^n)

更多CS 240总结请看: http://blog.gregwym.info/tag/cs240/