chap14 数据结构的扩张

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

内容

动态顺序统计

1. 在红黑树的基础上，为每个结点增加属性size，用来记录以该结点为子树的大小
2. 关系式：$x.size = x.left.size + x.right.size + 1$

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. 关系式$x.max = max(x.int.high,x.left.max,s.right.max)$
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

如何在$O(n\lg n)$时间内计算大小为n的数组中的逆序对
思路：使用顺序统计树，过的每个元素的秩$r(j)$。根据关系式$inv(j) = n - r(j)$可得总的逆序对。
式中j表示的是数组下标,$inv(j)$表示位于$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为结点的子树中的最小差值，最小关键字，最大关键字
关系式： $x.mingap =$
$min(x.left.mingap,x.right.mingap,x.key-x.left.maxval,x.right.minval-x.key)$

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. 关系式： $x.v = x.left.v+p(x)+x.right.v$;
$x.m = max(x.left.m,x.left.v+p(x),x.left.v+p(x)+x.right.m)$

14-2 Josephus 排列

思路：
1. m为常数，$O(n)--O(n)+O(mn)$
首先为没一个书指定一个order，再根据order按规则取数即可

1. m不是常数，$O(n\lg n)$
   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

代码实现