文章来源: http://thunderfyc.wordpress.com.cn/ 

V Advanced Data Structures
  18 B-Trees
    Data structures on secondary storage
      硬盘上有一些盘子(platter) 以固定速度绕着一个共同的轴(spindle)转 盘子表面是磁性物质 盘子被手臂(arm)末端的针头(head)读写 下面走过的叫轨迹(track)
      为减少硬盘读写次数 利用树结构将结点包含尽可能多的内容 每个结点能够扩展很多孩子 而数量由硬盘页的大小决定
   
    B-trees
      每个结点已知关键字数n 和非降序的关键字序列  每个结点有n+1个孩子 每个孩子的关键字以结点内关键字序列为间隔排序 所有叶子深度一样 一个结点至少含t个孩子 至多含2t个孩子 t=2时 叫2-3-4树
      查找 通过遍历关键字序列 判断应该进入哪一个孩子
      插入关键字 找到叶子结点 插入时 如果结点满 就找到中间值 分开叶子结点 中间值作为间隔 插入到父亲结点 若满 继续分 如果不满 插入
      删除 1如果k在结点内 结点是叶子 直接删除  2如果k在非叶子结点上 如果孩子y在k前 找一个y中的k’在k前 删除k’用k代替k’ 再找后继 如果只有t-1关键字 连上k合并之后再删 3如果不在当前结点 确定所在孩子 如果孩子只有t-1关键字 在他兄弟里面找多的并过来 找不到就把他和兄弟合并

  Mergeable Heaps

  procedure(worse-case)   Make-Heap  Insert    Minimum   Extract-Min   Union  Decrease-Key  Delete
  Binary heap             O(1)       O(lgn)    O(1)      O(lgn)         O(n)   O(n)         O(lgn)
  Binimal heap            O(1)       O(lgn)    O(lgn)    O(lgn)         O(lgn) O(lgn)       O(lgn)
  Fibonacci heap          O(1)       O(1)      O(1)      O(lgn)         O(1)   O(1)         O(lgn)  //amortized

  19 Binomial Heaps
    Binomial Trees
      二项树B0单结点 Bk是两个B_k-1合并 一个的根是另外一个根的最左的孩子
      Bk中 深度为i的结点有C(k,i)个
    Binomial Heaps
      二项树的森林  每个二项树符合小根堆性质 每个高度的树最多一个 结点数为n的话 就是二进制表示决定有哪个二项树

      查找最小值 找二项树根的最小值
      合并二项堆 将两个二项堆直接按二项树合并 然后从第一个二项树开始 如果连续三棵树的深度相同 合并后两棵 否则合并之
      插入结点   生成B0 合并
      弹出堆顶   在二项树根里面找最小值 然后 被去掉的那个二项树就形成了二项堆 合并
      删除结点   将结点变小 然后调整到树顶 删除

    2-3-4 Heaps
      每个结点2、3、4个孩子 只有叶子存一个值 没有固定顺序 每个结点存储其子孙的最小值 所有操作都是O(lgn)
      最小结点 从根开始 找孩子中最小值等于根的最小值的 T(n) <= T(n/2)+4 = O(lgn)
      插入 如果值小于当前内部结点值 就修改 然后不停的往下压 类似B-tree的插入
      删除 在删除过程中 注意查找新的最小值
      合并 直接加一个根 再找最小值

  20 Fibonacci Heaps
    每个结点有指向父亲的指针 指向任意孩子的指针 储存孩子数量 指向兄弟的指针 兄弟指针形成双向圈 每棵树满足堆性质 Fibonacci堆为森林 有指针指向最小值
   
    插入 直接作为树插入 更新最小值
    求最小值 直接获得
    合并 更新最小值 直接合并
    弹出最小值 把孩子都作为树插入 然后内合并操作
    内合并 找到有同样孩子数的根 把根大的作为根小的孩子插入 最后形成的森林最多的树和有最多孩子的树的孩子数一样
    提升结点 将结点值赋最小 如果有父亲 且父亲比它大 就把结点分离作为新树 并且 将其标为没有删除过孩子 更新最小值 另外调整父母 调整时 如果父母已经删除过一个孩子 那么标记为未删除 并且分离 继续调整祖父 如果没删除过 直接标记删除即可

文章来源: http://thunderfyc.wordpress.com.cn/ 
   
  21 Data Structure for Disjoint Sets
    一个森林 根为代表元素 查找某个结点的祖先是谁 不停访问结点的父亲
    合并 将两个树合并为一棵 一个的根作为另外一个的子集 为了使效率提升 可以将结点少的树并到结点多的树里
    查找 递归访问父亲

    Off-line Minimum
    已知操作序列 可以插入数字(1到n的整数) 可以弹出当前最小结点 求最后弹出最小结点序列
    把插入操作序列当作一个集合，两个弹出最小元素中间是空集，将结果枚举 从1到n 确定这个i是在哪棵树中 这棵树后的弹出最小的访问的答案设为它 然后找到比j大的最小数所在的集合合并

    Depth Determination
    可以做建新树 查找结点深度 将某个结点作为另外一个节点孩子插入 求实现
    用并查集 代表元素用某个祖先表示 另外记录到该祖先的长度 插入时 直接将其父亲作为祖先 压缩路径时注意更新 查找结点深度时 不停访问祖先 累加即可

    Off-line Least-common-ancestor
    LCA问题 查找两结点的最早公共祖先
    Tarjan算法 从根开始 将当前结点的祖先作为自己 然后对于每个孩子 继续处理 处理完一个节点后 合并孩子和自己 孩子的祖先设为自己 全部处理完之后 自己标记为访问完 对于问题集合中结点对中的另外一个结点 如果它访问完 答案为它祖先
    1 当两个节点有直系关系时 因为要等祖先标记为处理完 才能解答 这个时候子孙的祖先为祖先 正确； 2 当两个节点处于不同子树时 左边的子树先处理完 要到最早公共祖先处 才能够继续访问右边子树 这个时候左节点的祖先为LCA 那么访问到右边结点时 答案正确

 文章来源: http://thunderfyc.wordpress.com.cn/