Question

14.1-3

//14.1-3 非递归地查找以 x 为根结点的树中第 i 大的结点
node *Os_Tree::Os_Select_Iterative(node *x, int i)
{
  //根结点开始找起
  while(x != NULL)
  {
    int r = x->left->size + 1;
    //如果找到了
    if(r == i)
      return x;
    //如果位置更靠前
    if(i < r)
      x = x->left;
    //如果位置更靠后
    else
    {
      x = x->right;
      i = i - r;
    }
  }
}

14.1-4

//14.1-4 递归地计算树 T 中进行顺序遍历后得到的线性序中 x 的位置
int Os_Tree::Os_Rank_Recursion(node *root, node *x)
{
  if(x->key == root->key)
    return root->left->size + 1;
  if(x->key > root->key)
    //左子树的结点个数 + 根结点 + x 在右结点中的秩
    return root->left->size + 1 + Os_Rank_Recursion(root->right, x);
  //在左子树中的秩
  return Os_Rank_Recursion(root->left, x);
}

14.1-5

//14.1-5 确定 x 在该树的线性序中第 i 个后继
node *Os_Tree::Next(node *x, int i)
{
  //就是当前结点
  if(i == 0)
    return x;
  //在 x 的右子树中
  if(x->right != nil && x->right->size >= i)
    return Os_Select(x->right, i);
  //或在 x 某个祖先的右子树中
  else
  {
    //找到某个“有右子树”且“x 不在其右子树上”的祖先
    while(x->p != NULL && x == x->p->right)
      x = x->p;
    //找到了根结点，就停止查找
    if(x->p == NULL)
    {
      cout<<"error:not exist"<<endl;
      exit(0);
    }
    //对这个祖先进行递归的查找 
    Next(x, i-1);
  }
}

15.1-6

附加信息 rank[x]
插入时，若插入到 x 结点的左子树中，则 rank[x] = rank[x] + 1，否则不变
删除时，若删除的结点在 x 的左子树中，则 rank[x] = rank[x] - 1，否则不变
左旋时，若对 x 执行左旋，令 y=x->right，则 rank[x]不变，rank[y] = rank[y] + rank[x]
右旋时，若对 x 执行右旋，令 y=x->left，则 rank[y]不变，rank[x] = rank[x] + rank[y]

14.1-7

见 算法导论-14.1-7

求逆序数 中介绍了使用树状数组或归并排序求逆序对，这里使用顺序统计数。

数组中某个数字 s[i]的逆序数是指出现在 s[i]之前，但是比 s[i]大的数字的个数。

根据顺序统计量的 Os_Rank()，每插入到一个元素 x 后，可以求得在已经出现的元素中，比 x 大的数字的个数

14.1-8【转】

通过角度来判断两条弦是否相交，这样可以在 O(n*logn) 内完成。
对于两条弦 P1P2 和 Q1Q2 来说（顺时针），圆心与端点形成的向量有一个角度 A
如果 A(P1)<A(Q1)<A(P2)<A(Q2) 或者 A(Q1)<A(P1)<A(Q2)<A(P2)，这样角度区间“交叉”就意味着两条弦有交叉。
通过角度来统计交叉弦的对数，和“逆序对”的问题本质上是一样的

这可以看做是“顺序统计树”的典型应用。
我们判断两条弦是否相交的依据还是上面提到的“角度”区间是否有“交叉”现象发生
（注意一个区间包含另一个区间的情况不能算作“交叉”）
首先 n 条弦共 2n 个端点，每个端点对于圆心来说，都对应一个[0,2pi) 内的角度。
我们按角度大小（实际上就是逆时针方向）对这 2n 个角度进行排序，这一步需要花费 O(nlogn)
对于每条弦来说，它的两个端点都可以看做是“事件点”：从 0 角度开始逆时针在圆上扫描，遇到弦的第一个点可以看成是弦的“起点”，遇到的第二个点看成是弦的“终点”。
然后，我们用一棵“顺序统计树”来辅助进行处理（初始化当然为空）。

按照角度小到大的顺序遍历这 2n 个端点：
如果该端点是某条弦 X 的“起点”
{
  将弦 X 插入顺序统计树中（以 X 的“起点”角度作为 key）；
}
如果该端点是某条弦 X 的“终点”
{
  统计出目前这棵树中有多少条弦的“起点”角度比 X 的“起点”角度大，这就是与 X 相交的弦的数量；
  //对于顺序统计树来说，上面这步只要 O(logn) 就能实现
  将弦 X 从顺序统计树中删除； //这一步同样只需要 O(logn)
}

题目：

假设希望对一组区间记录一个最大重叠点，亦即覆盖它的区间最多的那个点。
a) 证明：最大重叠点总存在于某段的端点上。
b) 设计一数据结构，能有效地支持操作 INTERVAL-INSERT,INTERVAL-DELETE 和返回最大重叠点操作 FIND-POM。（提示：将所有端点组织成红黑树。左端点关联+1 值，而右端点关联-1 值。附加一些维护最大重叠点的信息以扩张树中结点。）

思考：

设有 n 个区间，将所有 2n 个点从小到大排序，对于排序后的第 i 个点，若它是某个区间的左端点，则 p[i]=1，若它是某个区间的右端点，则 p[i]=-1。由第一问可知，所求的点一定是某条线段的端点，所以从端点集合中找出被最多区间覆盖的那个。若一个端点是排序后的第 i 个点，则有个 SUM(s[1],s[i]) 个区间覆盖这个点。

使用红黑树对所有的端点进行动态排序并保证有较好的性质，在树的结点中增加一些顺序统计量的信息，用于求 SUM(s[1],s[i])

步骤 1：基础数据结构

红黑树，p[x]=1 表示它是区间的左端点，p[x]=-1 表示它是区间的右端点

步骤 2：附加信息

v[x]：以 x 为根的所有结点的 p 值之和

m[x]：MAX(SUM([left[x], i))

o[x]：以 x 为根的所有结点中的最大覆盖点

步骤 3：对信息的维护

步骤 4：设计新的操作

Find_Pom()：返回根结点的 p 值

代码：

头文件

产品代码

测试代码

题目：

Josephus 问题的定义如下：假设 n 个人排成环形，且有以正整数 m<=n。从某个制定的人开始，沿环报数，每遇到第 m 个人就让其出列，且报数进行下去。这个过程一直进行到所有人都出列为止。每个人出列的次序定义了整数 1，2，...，n 的(n, m)-Josephus 排列。例如，(7,3)-Josephus 排列为<3,6,2,7,5,1,4>。
a) 假设 m 为整数。请描述一个 O(n) 时间的算法，使之对给定的整数 n，输出(n, m)-Josephus 排列。
b) 假设 m 不是个常数。请描述一个 O(nlgn) 时间的算法，使给定的整数 n 和 m，输出(n, m)-Josephus 排列。

思考：

利用 14.1 中的动态顺序统计，假设刚刚删除的是剩余点中的第 start 个点（初始时为 0），此时还剩下 t 个点，那么下一个要删除的是剩余点的第（start+m-1）%t 个点

步骤 1：基础数据结构

红黑树

步骤 2：附加信息

size[x]：以 x 为根的子树的（内部）结点数（包括 x 本身），即子树的大小。size[nil[T]]=0

步骤 3：对信息的维护

size[x] = size[left[x]] + size[right[x]] + 1

插入操作：从插入结点到根结点都要更新 O(lgn)

旋转操作：只需要更新旋转轴上的两个点 O(1)

删除操作：从删除结点的父结点开始到根结点都要更新 O(lgn)

代码：

https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter14/exercise14_2.cpp