[关闭]
@zqbinggong 2018-03-13T02:14:02.000000Z 字数 2157 阅读 443

chap14 数据结构的扩张

顺序统计树 区间树 算法导论

内容


动态顺序统计

  1. 在红黑树的基础上,为每个结点增加属性size,用来记录以该结点为子树的大小
  2. 关系式:
  3. 对子树规模的维护

    • 插入操作和删除操作是对称的,对于插入来说,将插入的元素确定结点后,只需沿着寻找的路径,让该路径上所有结点的size增加1即可
    • 对于rotate操作,以左旋为例,只需增加y.size = x.size; x.size == x.left.size + x.right.size + 1

      1. 红黑树扩张的定理以及扩张数据结构的一般步骤
  4. 基本操作

查找具有给定秩的元素

os-select(x,i)

r = x.left.size + 1
if i == r
    return x
else if i < r
    return os-select(x.left,i)
else return os-select(x.right,i)

确定一个元素的秩

os-rank(T,x)

r = x.left.size + 1
y = x
while y != T.root
    if y = y.p.right
        r = r + y.p.left.size + 1
    y = y.p
return r

区间树

  1. 基于红黑树,新增属性int和max,其中int是一个区间,max表示以该结点为子树中最大的端点,关键字key表示int.low
  2. 关系式
  3. 新操作 区间查找

interval-search(T,i)

x = T.root
while x !+ T.root and i does not overlap x.int
    if x.left != T.nil and i.low < x.left.max
        x = x.left
    else x = x.right
return x

习题

14.1-7

如何在时间内计算大小为n的数组中的逆序对
思路:使用顺序统计树,过的每个元素的秩。根据关系式可得总的逆序对。
式中j表示的是数组下标,表示位于 之后的比j小的数个数


14.2-2 能否将黑高作为属性维护

当然可以


14.3-3

  1. 问题:返回与给定区间重合且具有最小端点的区间
  2. 思路:为满足最小端点的要求,尽量往左下方找

--

mim-insert-search(T,i)
return mim-interval-search-from(T,T.root,i)

mim-interval-search-from(T,x,i)
if x.left != T.nil and i.low < x.left.max
    y = mim-interval-search-from(T,x.left,i)#尽量往左下方找
    if y != T.nil
        return y
    else if i overlaps x.int
        returnx 
    else return mim-interval-search-from(T,x.right,i)

14.3-6 返回两个最接近数的差

思路: 增加属性x.min-gap,x.min-val,x.max-val,分别是以x为结点的子树中的最小差值,最小关键字,最大关键字
关系式:


14.3-7 矩形重叠问题

思路:
1. 选取所有矩形的x坐标,将其排序,并记录该坐标对应的矩形以及它是该矩形的左变坐标还是右边坐标
2. 从小到大便遍历这些x坐标,当遇到一个左边坐标时,检查它的y左边区间是否与区间树中的区间重叠,再将其插入区间树;
3. 当遇到一个右边坐标区间,删除对应的y区间
4. 一直遍历,知道遇到2中检查情况为真时,返回true,否则返回false


14-1 最大重叠点

思路:
1. 总存在一个是端点的最大重叠点
2. 这里。把区间的端点作为单独的元素并创建一个二叉搜索树,并且给做端点增加属性p=1,右端点p=-1,注意在插入元素时,如果有端点值相等,则先插入左边端点
3. 反向,最大重叠点满足一个特殊的关系:对于已经排好序的端点序列来说,让他们的p按顺序相加,直到和sum最大,此时最后加入的端点就是最大重叠点
4. 根据3中的关系,给每个结点再增加属性v,m,i,分别表示以x为结点的子树中所有元素按序相加(3中所述)的sum,最大sum,最大sum对应的i
5. 关系式: ;


14-2 Josephus 排列

思路:
1. m为常数,
首先为没一个书指定一个order,再根据order按规则取数即可

  1. m不是常数,
    josephus(n,m)

    initialize T to be empty
    for j = 1 to n
    create a noede x with x.key = j
    os-insert(T,x)
    k=n,j=m
    while k > 2
    x = os-select(T.root,j)
    pritn x.key
    os-delete(T.root,j)
    k = k - 1
    j = ((j+m-2)mod k) + 1
    print os-select(T.root,1).key


代码实现

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注