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内侧
  
  
• Double rotation: 当height最高的leaf位于Tree内侧
  
  • 将height较高的root child向外侧旋转, 将Tree变形为Single rotation的初始形式
  • 执行Single rotation
  
  

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

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和Ω

• Logarithmic (log n)
• Linear (n)
• Linearithmic (n log n)
• Quadratic (n^2)
• Cubic (n^3)
• Exponential (2^n)