调Splay太恐怖了，虽然不难，但是为什么bug这么多。。。这里记一下原则性问题吧。。。

类名叫SplayTree

  • 在我的写法里，每个SplayTree对象不仅代表一个点，它代表整棵子树
  • 每个对象里有一个特殊的阈值，SplayTree *Nil，它代表不存在的点（即叶子结点的后继或者是总根节点的前驱），算法导论上好像称之为哨兵，预处理的时候所有的前驱后继都等于Nil（其实原来把Nil定义在了类的外面而不是类的阈值，但是这样会很麻烦。。所以干脆再开个变量叫Nil好了）
  • 下面的代码表示阈值：
    • ?
      1
      2
      3
      int v,size;//分别是键值，子树大小,
      bool pl;//place 表示该节点在父节点的哪个位置
      ST *pr,*suc[2],*Nil;//分别表示前驱，两个后继，和Nil节点的位置
  • 下面的代码声明了各种函数：
    • ?
      SplayTree类的函数声明
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      /*由于SpayTree太长了，一下所写为ST*/
      void mt();//maintain 即维护Splay，保证信息的正确性
      void ini();//初始化，将所有的前驱后继都改成Nil
      void trans(ST *tar,bool place);//将该子树移动到tar的place边（place=0表示左子树，反之右子树）
      void rotate();//旋转，一个函数搞定左旋/右旋
      void Splay();//核心操作，即将某节点提到根
      ST *find_v(int fv)//找到fv所在的位置，找不到返回它应该在的位置的根(按照数字值查询)
      void insert(int iv/*也可以是 ST*p */);//插入iv到相应位置
      void find_s(int pos);//按照size找第pos小的元素，也就是如果要求第pos小的元素是哪个，就可以用这个函数在O(lgn)的时间复杂度内完成
      ST *fmin/*或fmax*/();//找到最小值所在的位置（返回指针）
      void merge(ST *obj);//将obj所在的Splay合并到该节点所在的Splay...
  • 下面的代码描述了trans,rotate,Splay的过程
    • ?
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      void trans(ST *tar,bool place){//ST::移形换位
              pl=place;
              pr=tar;
              tar->suc[pl]=this;
      }
      void rotate(){//旋转
      bool ppl=pl;
      ST fprev=*pr;
          suc[!pl]->trans(pr,pl);//移动子树
          pr->trans(this,!pl);//移动原前驱
          trans(fprev.pr,fprev.pl);//移动该节点
          suc[!ppl]->mt();
          mt();
      }
      void Splay(){//Splay操作
          while(pr!=Nil){
              if(pl==pr->pl && pr->pr!=Nil)
                  pr->rotate();
              rotate();
          }
      }
  •  的
  • 的