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

类名叫SplayTree

• 在我的写法里，每个SplayTree对象不仅代表一个点，它代表整棵子树
• 每个对象里有一个特殊的阈值，SplayTree *Nil，它代表不存在的点（即叶子结点的后继或者是总根节点的前驱），算法导论上好像称之为哨兵，预处理的时候所有的前驱后继都等于Nil（其实原来把Nil定义在了类的外面而不是类的阈值，但是这样会很麻烦。。所以干脆再开个变量叫Nil好了）
• 下面的代码表示阈值：

  • int v,size;//分别是键值，子树大小,
    bool pl;//place 表示该节点在父节点的哪个位置
    ST *pr,*suc[2],*Nil;//分别表示前驱，两个后继，和Nil节点的位置

• 下面的代码声明了各种函数：

  • /*由于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的过程

  • 	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();
    		}
    	}

•  的
• 的