Question

14.3-1

LEFT-ROTATE(T, x)
 1  y <- right[x]
 2  right[x] <- left[y]
 3  if left[y] != nil[T]
 4  then p[left[y]] <- x
 5  p[y] <- p[x]
 6  if p[x] = nil[T]
 7    then root[T] <- y
 8    else if x = left[p[x]]
 9      then left[p[x]] <- y
10      else right[p[x]] <- y
11  left[y] <- x
12  p[x] <- y
13  max[y] <- max[x]
14  max[x] <- max(high[int[x]], max[left[x]], max[right[x]])

14.3-2

对二中的程序做三点修改
（1）L37，<改成<=
（2）L40，>改成>=
（3）L443，>=改成>

14.3-3

那本答案 PDF 写得比较麻烦，不明天为什么要写得这么复杂，我只分了三种情况

node* Interval_Tree::Search_Min(node *root, interval i)
{
  node *x = root, *y;  
  //先从左子树上找
  if(x->left && x->left->max >= i.low)
  {
    y = Search_Min(x->left, i);
    if(y != nil)
      return y;
  }
  //如果 x 与 i 相交，就不需要找左子树了
  if(Overlap(x->inte, i))
    return x;
  //最后在右子树上找
  if(x->right)
    return Search_Min(x->right, i);
  return nil;   
}

14.3-4

void Interval_Tree::Search_All(node *root, interval i)
{
  node *x = root, *y;  
  //如果当前结点与 i 相交
  if(Overlap(x->inte, i))
    cout<<x->inte.low<<' '<<x->inte.high<<endl;
  //先从左子树上找
  if(x->left && x->left->max >= i.low)
    Search_All(x->left, i);
  //从右子树上找
  if(x->right && x->key <= i.high)
    Search_All(x->right, i);  
}

14.3-5

node* Interval_Tree::Search_Exactly(interval i)
{
   //从根结点开始  
  node *x = root;  
  //不是叶子且不重叠  
  while(x != nil)  
  {  
    if(x->inte.low == i.low && x->inte.high == i.high)  
      return x;  
    //在左子树中  
    if(x->left != nil && x->key >= i.low)  
      x = x->left;  
    //在右子树中  
    else  
      x = x->right;  
  }  
  return nil;
}

14.3-6

见 算法导论-14.3-6-MIN-GAP

14.3-7

见 算法导论-14.3-7-O(nlgn) 时间求矩形集合中重叠矩形的个数