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

III Data Structures
  10 Stacks and queues
   
    Stack
      就是一个栈从口里进来从口里出去 先进后出
   
    Queue
      就是一个队列从尾进从头出 先进先出

    
    Linked list 就是一个个的点 中间那线串起来了 一个点至多有一个前驱和一个后继 当然还可以做成双向的链表
      实现 可以用数组next[i]表示指向data[next[i]]
   
    Representing rooted trees
      Binary Trees
        一个点最多伸出两个后继 实现同上
      Rooted Trees with unbouded branching
        一个结点最多伸出两个后继 左孩子 右兄弟

  11 Hash Tables
    通过Hash函数用一个值来表示元素 然后储存

    Universal Hashing
      随机从库中选择一个Hash函数

    Perfect hashing
      没有冲突的Hash 用于固定关键字 用第一次hash分组 然后再第二次hash时 让该组容量为组员数目的平方
  12 Binary Search Tree
    所有结点大于左儿子小于右儿子的二叉树
    Searching
      要查找的值比当前小去左子树 比当前大去右子树
    Maximum and Minimum
      一路向右或者向左
    Successor
      查找右子树的最小 没有右子树的 只要是父母的左孩子就不停的找妈
    Insertion
      查找到可以存放的叶子结点 插入
    Deletion
      如果不是双孩子结点 直接儿子顶替 否则找后继 顶替 (此时后继必然最多一个孩子)
    Randomly built binary search trees
      重新排列输入数据 防止退化

    Radix Trees
      一个结点产生N个孩子 从根到结点的路径标记连起来就是结点的值

    Number of different binary trees
      bn = ∑(b_k*b_n-1-k)
      Generating Function  B(x) = ∑(bn*x^n)
      B(x) = x(B(x))^2+1 => B(x) = (1-sqrt(1-4x))/2x
      Taylor expansion
      bn = C(2n, n)/(n+1)

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

  13 Red-Black Trees
    结点或红或黑 总有两个孩子 根是黑的 叶子为空的黑结点 红结点的孩子为黑 结点到所有直系叶子路径上的黑结点数一致
    n个结点的红黑树高度最多 2lg(n+1)
    Rotation
      左旋是把结点和右儿子交换 右儿子的左子树和结点的右子树交换
      右旋是把结点和左儿子交换 左儿子的右子树和结点的左子树交换
    Insertion
      在BST基础上 加插入结点为红 然后向上调整
      调整过程中 只要父亲是红不停的搞 A如果叔叔是红色 父亲叔叔变黑 爷爷变红 调整爷爷去 无视BC；
      B如果叔叔黑色 如果自己-父亲和父亲-爷爷的关系相反就提升 操作指向原来的爸爸 C爸爸变黑 爷爷变红 爸爸提升
      根置黑
     
      插入为红 那么如果父亲为红 冲突 继续， A 如果叔叔红 爷爷比为黑， 那么爷爷变红 父亲 叔叔变黑 黑色深度不变 插入满足，继续调整爷爷。
      如果叔叔黑 因为爸爸红 所以爷爷黑 以爸爸是爷爷左孩子为例
      C 那么如果是爸爸左孩子 爷爷红 爸爸黑 叔叔黑 这个时候爷爷-叔叔线错了 把爷爷下调 爸爸上升
      B 如果是爸爸右孩子 爸爸下降 自己上升 自己和爸爸都是红的 所以这个时候操作爸爸就好了
      最后结点变黑

    Deletion
      同BST 如果被删除的或者是替换被删除的是黑结点 对填补空缺的孩子进行调整
      只要当前结点是黑结点就调整 A 兄弟为红 兄弟变黑 爸爸变红后下调 B 如果新的侄子都是黑 兄弟变红 处理新爹去
      C 不然的话 如果新的右侄子是黑 左侄子变黑 兄弟变红 兄弟和左侄子换位
      D 兄弟和爸爸同色 爸爸是黑 右侄子变黑 爸爸和兄弟换位 处理根去

      如果被移走结点是黑的 1如果移走的是根 顶它的是红点 2如果移走之后出现两个红点 3使得黑线变短
      3比较困难 将新顶上去的结点叠加一个黑色 叫超黑 然后将黑色不停的往上传 传到红色的时候改成黑色跳出 传到根自动消除

      A 如果兄弟是红的 俩侄子为黑 那么兄弟变黑 爸爸变红 交换 继续
      B 如果侄子都是黑的 兄弟也得是黑的(因为自己双黑 这样才满足路径) 所以把兄弟和自己都去黑 兄弟变红 超黑传给爹 处理爹去
      C 如果侄子不都是黑 如果新的右侄子是黑 那么兄弟肯定是黑的 左侄子红 把左侄子也变黑 兄弟红 兄弟和左侄子换位 继续
      D 这个时候兄弟黑 右侄子红 把兄弟变成爸爸色 爸爸变成黑 右侄子变黑 爸爸和兄弟换位 就让到调整点的黑路径加长了1 超黑消除 结束

    Insertion的B和Deletion的C 当然可以不转化成D 处理 只不过这样方便点

    Join
      已知一棵树均小于X 另一棵树均大于X 合并两树和X
      在黑色路径长度较大的树里 用O(lgn)的时间找到最大的元素 此元素到叶子节点黑色路径长度等于小树的 然后用这个元素为根的子树和X和小树合并 替换到原来位置

    AVL trees
      用左子树高度减去右子树高度的平衡参数维护平衡 参数绝对值不超过1

    Treaps
      用一个随机权值来维护平衡 该权值形成的结构满足堆的性质
  14 Augementing Data Structures
    Dynamic order statistics
      查找第i大的元素
        记录以当前结点为根的子树的大小即可 递归访问 如果左子树容量大于访问容量 去左子树 否则减去左子树容量访问右子树
        求某结点的序号 加上左子树大小 不停向上到根 只要是父亲的右孩子 就加兄弟大小+1
        维护 只要是旋转就需要维护 插入的时候沿路加1

    Interval Trees
      结点是区间的红黑树 以左端点作为比较关键字 结点另外包含其子数并区间的右端点的记录

    Point of Maximum Overlap
      找到一个点有最多区间覆盖
      总有一个区间的端点是满足条件的点
      建BST 结点e关键字为端点坐标 p[e]=1表示增加叠加区间 p[e]=-1表示减少叠加区间 v[x]表示以x为根的树的p的和 m[x]表示从最左开始累加的过程中的最大值 o[x]表示取最大值时的i值
      v[x] = v[lchild[x]]+p[x]+v[rchild[x]]  m[x] = max{m[lchild[x]], v[lchild[x]]+p[x], v[lchild[x]]+p[x]+m[rchild[x]]}
   
    Josephus permutation
      n个人围成一圈 每报m个数 去掉一个人 直到剩下一个 求出队序列 m可变
      建BST 如果当前i出列 删除结点 查找第(i+m-2)%k+1个元素

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