Question

1.Os_Tree.h

#include <iostream>
using namespace std;

#define BLACK 0
#define RED 1

//顺序统计量树结点结构
struct node
{
  /*红黑树的域*/
  int key;
  bool color;
  node *p;
  node *left;
  node *right;
  /*附加信息*/
  int size;//以结点 x 为根的子树的内部结点的个数，x->key=x->left->key+x->right->key+1

  /*构造函数*/
  node(node *init, int k):left(init),right(init),p(init),key(k),color(BLACK),size(1){}  
};
//顺序统计量树结构
class Os_Tree
{
public:
  node *root;
  node *nil;//哨兵
  /*构造函数*/
  Os_Tree(){nil = new node(NULL, -1);root = nil;nil->size = 0;};  
  /*动态顺序统计相关操作*/
  node *Os_Select(node *x, int i);
  int Os_Rank(node *x);
  /*红黑树的相关操作*/
  void Left_Rotate(node *x);//左旋
  void Right_Rotate(node *x);//右旋
  void Os_Insert_Fixup(node *z);//插入调整
  void Os_Insert(node *z);//插入
  void Os_Delete_Fixup(node *x);//删除调整
  node *Os_Delete(node *z);//删除
  void Print();//输出
  void Print(node *x);//输出
  node *Os_Search(node *x, int k);//在 x 的子树中查找关键字为 k 的结点
  node *Tree_Successor(node *x);//求后继
  node *Tree_Minimum(node *x);//求关键字最小的点
};
//左旋，令 y = x->right, 左旋是以 x 和 y 之间的链为支轴进行旋转
//涉及到的结点包括：x,y,y->left，令 node={p,l,r},具体变化如下：
//x={x->p,x->left,y}变为{y,x->left,y->left}
//y={x,y->left,y->right}变为{x->p,x,y->right}
//y->left={y,y->left->left,y->left->right}变为{x,y->left->left,y->left->right}
void Os_Tree::Left_Rotate(node *x)
{
  //令 y = x->right
  node *y = x->right;
  //按照上面的方式修改三个结点的指针，注意修改指针的顺序
  x->right = y->left;
  if(y->left != nil)
    y->left->p = x;
  y->p = x->p;
  if(x->p == nil)//特殊情况：x 是根结点
    root = y;
  else if(x == x->p->left)
    x->p->left = y;
  else 
    x->p->right = y;
  y->left = x;
  x->p = y;
  //对附加信息的维护
  y->size = x->size;
  x->size = x->left->size + x->right->size + 1;
}
//右旋，令 y = x->left, 左旋是以 x 和 y 之间的链为支轴进行旋转
//旋转过程与上文类似
void Os_Tree::Right_Rotate(node *x)
{
  node *y = x->left;
  x->left = y->right;
  if(y->right != nil)
    y->right->p = x;
  y->p = x->p;
  if(x->p == nil)
    root = y;
  else if(x == x->p->right)
    x->p->right = y;
  else 
    x->p->left = y;
  y->right = x;
  x->p = y;
  //对附加信息的维护
  y->size = x->size;
  x->size = x->left->size + x->right->size + 1;
}
//红黑树调整
void Os_Tree::Os_Insert_Fixup(node *z)
{
  node *y;
  //唯一需要调整的情况，就是违反性质 2 的时候，如果不违反性质 2，调整结束
  while(z->p->color == RED)
  {
    //p[z]是左孩子时，有三种情况
    if(z->p == z->p->p->left)
    {
      //令 y 是 z 的叔结点
      y = z->p->p->right;
      //第一种情况，z 的叔叔 y 是红色的
      if(y->color == RED)
      {
        //将 p[z]和 y 都着为黑色以解决 z 和 p[z]都是红色的问题
        z->p->color = BLACK;
        y->color = BLACK;
        //将 p[p[z]]着为红色以保持性质 5
        z->p->p->color = RED;
        //把 p[p[z]]当作新增的结点 z 来重复 while 循环
        z = z->p->p;
      }
      else
      {
        //第二种情况：z 的叔叔是黑色的，且 z 是右孩子
        if(z == z->p->right)
        {
          //对 p[z]左旋，转为第三种情况
          z = z->p;
          Left_Rotate(z);
        }
        //第三种情况：z 的叔叔是黑色的，且 z 是左孩子
        //交换 p[z]和 p[p[z]]的颜色，并右旋
        z->p->color = BLACK;
        z->p->p->color = RED;
        Right_Rotate(z->p->p);
      }
    }
    //p[z]是右孩子时，有三种情况，与上面类似
    else if(z->p == z->p->p->right)
    {
      y = z->p->p->left;
      if(y->color == RED)
      {
        z->p->color = BLACK;
        y->color = BLACK;
        z->p->p->color = RED;
        z = z->p->p;
      }
      else
      {
        if(z == z->p->left)
        {
          z = z->p;
          Right_Rotate(z);
        }
        z->p->color = BLACK;
        z->p->p->color = RED;
        Left_Rotate(z->p->p);
      }
    }
  }
  //根结点置为黑色
  root->color = BLACK;
}
//插入一个结点
void Os_Tree::Os_Insert(node *z)
{
  node *y = nil, *x = root;
  //找到应该插入的位置，与二叉查找树的插入相同
  while(x != nil)
  {
    x->size++;
    y = x;
    if(z->key < x->key)
      x = x->left;
    else
      x = x->right;
  }
  z->p = y;
  if(y == nil)
    root = z;
  else if(z->key < y->key)
    y->left = z;
  else
    y->right = z;
  z->left = nil;
  z->right = nil;
  //将新插入的结点转为红色
  z->color = RED;
  //从新插入的结点开始，向上调整
  Os_Insert_Fixup(z);
}
//对树进行调整，x 指向一个红黑结点，调整的过程是将额外的黑色沿树上移
void Os_Tree::Os_Delete_Fixup(node *x)
{
  node *w;
  //如果这个额外的黑色在一个根结点或一个红结点上，结点会吸收额外的黑色，成为一个黑色的结点
  while(x != root && x->color == BLACK)
  {
    //若 x 是其父的左结点（右结点的情况相对应）
    if(x == x->p->left)
    {
      //令 w 为 x 的兄弟，根据 w 的不同，分为三种情况来处理
      //执行删除操作前 x 肯定是没有兄弟的，执行删除操作后 x 肯定是有兄弟的
      w = x->p->right;
      //第一种情况：w 是红色的
      if(w->color == RED)
      {
        //改变 w 和 p[x]的颜色
        w->color = BLACK;
        x->p->color = RED;
        //对 p[x]进行一次左旋
        Left_Rotate(x->p);
        //令 w 为 x 的新兄弟
        w = x->p->right;
        //转为 2.3.4 三种情况之一
      }
      //第二情况：w 为黑色，w 的两个孩子也都是黑色
      if(w->left->color == BLACK && w->right->color == BLACK)
      {
        //去掉 w 和 x 的黑色
        //w 只有一层黑色，去掉变为红色，x 有多余的一层黑色，去掉后恢复原来颜色
        w->color = RED;
        //在 p[x]上补一层黑色
        x = x->p;
        //现在新 x 上有个额外的黑色，转入 for 循环继续处理
      }
      //第三种情况，w 是黑色的,w->left 是红色的,w->right 是黑色的
      else
      {
        if(w->right->color == BLACK)
        {
          //改变 w 和 left[x]的颜色
          w->left->color = BLACK;
          w->color = RED;
          //对 w 进行一次右旋
          Right_Rotate(w);
          //令 w 为 x 的新兄弟
          w = x->p->right;
          //此时转变为第四种情况
        }
        //第四种情况：w 是黑色的,w->left 是黑色的,w->right 是红色的
        //修改 w 和 p[x]的颜色
        w->color =x->p->color;
        x->p->color = BLACK;
        w->right->color = BLACK;
        //对 p[x]进行一次左旋
        Left_Rotate(x->p);
        //此时调整已经结束，将 x 置为根结点是为了结束循环
        x = root;
      }
    }
    //若 x 是其父的左结点（右结点的情况相对应）
    else if(x == x->p->right)
    {
      //令 w 为 x 的兄弟，根据 w 的不同，分为三种情况来处理
      //执行删除操作前 x 肯定是没有兄弟的，执行删除操作后 x 肯定是有兄弟的
      w = x->p->left;
      //第一种情况：w 是红色的
      if(w->color == RED)
      {
        //改变 w 和 p[x]的颜色
        w->color = BLACK;
        x->p->color = RED;
        //对 p[x]进行一次左旋
        Right_Rotate(x->p);
        //令 w 为 x 的新兄弟
        w = x->p->left;
        //转为 2.3.4 三种情况之一
      }
      //第二情况：w 为黑色，w 的两个孩子也都是黑色
      if(w->right->color == BLACK && w->left->color == BLACK)
      {
        //去掉 w 和 x 的黑色
        //w 只有一层黑色，去掉变为红色，x 有多余的一层黑色，去掉后恢复原来颜色
        w->color = RED;
        //在 p[x]上补一层黑色
        x = x->p;
        //现在新 x 上有个额外的黑色，转入 for 循环继续处理
      }
      //第三种情况，w 是黑色的,w->right 是红色的,w->left 是黑色的
      else
      {
        if(w->left->color == BLACK)
        {
          //改变 w 和 right[x]的颜色
          w->right->color = BLACK;
          w->color = RED;
          //对 w 进行一次右旋
          Left_Rotate(w);
          //令 w 为 x 的新兄弟
          w = x->p->left;
          //此时转变为第四种情况
        }
        //第四种情况：w 是黑色的,w->right 是黑色的,w->left 是红色的
        //修改 w 和 p[x]的颜色
        w->color =x->p->color;
        x->p->color = BLACK;
        w->left->color = BLACK;
        //对 p[x]进行一次左旋
        Right_Rotate(x->p);
        //此时调整已经结束，将 x 置为根结点是为了结束循环
        x = root;
      }
    }
  }
  //吸收了额外的黑色
  x->color = BLACK;
}
//找最小值   
node *Os_Tree::Tree_Minimum(node *x)  
{  
  //只要有比当前结点小的结点   
  while(x->left != nil)  
    x = x->left;  
  return x;  
} 
//查找中序遍历下 x 结点的后继，后继是大于 key[x]的最小的结点   
node *Os_Tree::Tree_Successor(node *x)  
{  
  //如果有右孩子   
  if(x->right != nil)  
    //右子树中的最小值   
    return Tree_Minimum(x->right);  
  //如果 x 的右子树为空且 x 有后继 y，那么 y 是 x 的最低祖先结点，且 y 的左儿子也是   
  node *y = x->p;  
  while(y != NULL && x == y->right)  
  {  
    x = y;  
    y = y->p;  
  }  
  return y;  
}  
//递归地查询二叉查找树   
node *Os_Tree::Os_Search(node *x, int k)  
{  
  //找到叶子结点了还没找到，或当前结点是所查找的结点   
  if(x->key == -1 || k == x->key)  
    return x;  
  //所查找的结点位于当前结点的左子树   
  if(k < x->key)  
    return Os_Search(x->left, k);  
  //所查找的结点位于当前结点的左子树   
  else  
    return Os_Search(x->right, k);  
} 
//红黑树的删除
node *Os_Tree::Os_Delete(node *z)
{
  //找到结点的位置并删除，这一部分与二叉查找树的删除相同
  node *x, *y;
  if(z->left == nil || z->right == nil)
    y = z;
  else y = Tree_Successor(z);
  node *p = y->p;
  while(p != nil)
  {
    p->size--;
    p = p->p;
  }
  if(y->left != nil)
    x = y->left;
  else x = y->right;
  x->p = y->p;
  if(y->p == nil)
    root = x;
  else if(y == y->p->left)
    y->p->left = x;
  else
    y->p->right = x;
  if(y != z)
    z->key = y->key;
  //如果被删除的结点是黑色的，则需要调整
  if(y->color == BLACK)
    Os_Delete_Fixup(x);
  return y;
}
void Os_Tree::Print(node *x)
{
  if(x->key == -1)
    return;
  Print(x->left);
  cout<<x->key<<' '<<x->color<<endl;
  Print(x->right);
}
void Os_Tree::Print()
{
  Print(root);
  cout<<endl;
}
//查找以 x 为根结点的树中第 i 大的结点
node *Os_Tree::Os_Select(node *x, int i)
{
  //令 x 左子树中点的个数为 r-1,
  int r = x->left->size +1;
  //那么 x 是 x 树中第 r 大的结点
  if(r == i)
    return x;
  //第 i 大的元素在 x->left 中
  else if(i < r)
    return Os_Select(x->left, i);
  //第 i 大的元素在 x->right 中
  else
    return Os_Select(x->right, i - r);
}
//计算树 T 中进行顺序遍历后得到的线性序中 x 的位置
int Os_Tree::Os_Rank(node *x)
{
  //置 r 为以 x 为根的子树中 key[x]的秩
  int r = x->left->size + 1;
  node *y = x;
  while(y != root)
  {
    //若 y 是 p[y]的右孩子，p[y]和 p[y]左子树中所有结点前于 x
    if(y == y->p->right)
      r = r + y->p->left->size + 1;
    y = y->p;
  }
  return r;
}

2.main.cpp

#include <iostream>
#include "Os_Tree.h"
using namespace std;

int main()
{
  char ch;
  int x;
  //生成一棵顺序统计树
  Os_Tree *T = new Os_Tree;
  while(1)
  {
    cin>>ch;
    switch(ch)
    {
      //插入一个元素
    case 'I':
      {
        cin>>x;
        node *z = new node(T->nil, x);
        T->Os_Insert(z);
        break;
      }
      //删除一个元素
    case 'D':
      {
        cin>>x;
        node *z = T->Os_Search(T->root, x);
        if(z == NULL)
          cout<<"not exist"<<endl;
        else
          T->Os_Delete(z);
        break;
      }
      //计算第 x 小关键字
    case 'S':
      {
        cin>>x;
        node *z = T->Os_Select(T->root, x);
        if(z == NULL)
          cout<<"not exist"<<endl;
        else
          cout<<z->key<<endl;
        break;
      }
      //计算 x 的位置
    case 'R':
      {
        cin>>x;
        node *z = T->Os_Search(T->root, x);
        if(z == NULL)
          cout<<"not exist"<<endl;
        else
          cout<<T->Os_Rank(z)<<endl;
        break;  
      }
    case 'P':
      T->Print();
      break;
    default:
      break;
    }
  }
  return 0;
}