最近“hiho一下”出了平衡树专题，这周的Splay一直出现RE，应该删除操作指针没处理好，还没找出原因。
不过其他操作运行正常，尝试用它写了一道之前用set做的平衡树的题http://codeforces.com/problemset/problem/675/D，运行效果居然还挺好的，时间快了大概10%，内存少了大概30%。
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <assert.h>
#define FREAD(fn) freopen((fn), "r", stdin)
#define RINT(vn) scanf("%d", &(vn))
#define PINT(vb) printf("%d", vb)
#define RSTR(vn) scanf("%s", (vn))
#define PSTR(vn) printf("%s", (vn))
#define CLEAR(A, X) memset(A, X, sizeof(A))
#define REP(N) for(i=0; i<(N); i++)
#define REPE(N) for(i=1; i<=(N); i++)
#define pb(X) push_back(X)
#define pn() printf("\n")
using namespace std;
const int MAX_N = ;
const int MAX_K = 0x7fffffff;
const int MIN_K = ; int a[MAX_N];
int n;
int i;
map<int, bool> left, right;//iostream里有和left, right冲突的命名! struct Node
{
int k;
Node *l, *r, *p;
Node():k(-), l(NULL), r(NULL), p(NULL){}
Node(int kk, Node* pp):k(kk), l(NULL), r(NULL), p(pp){}
~Node(){
l = r = p = NULL;
}
}; struct Splay
{
Node* root;
Node* _hot;
Splay():root(NULL), _hot(NULL){}
Splay(int k):root(new Node(k, NULL)), _hot(root){} void release(Node* cur){//释放子树cur的空间
if(cur == NULL) return ;//空树
release(cur->l);
cur->l = NULL;
release(cur->r);
cur->r = NULL; //不用加吧，cur马上就销毁了啊
//printf("deleted %d\n", cur->k); delete cur;
return ;
}
~Splay(){
release(root);
root = NULL;
}
void zig(Node* cur){
if(cur == NULL) return ;
Node* v = cur->l;
if(v == NULL) return ;
Node* g = cur->p; v->p = g;
if(g != NULL)
//祖先g与v连接
(cur == g->l) ? g->l = v : g->r = v; //v与cur孩子过继
cur->l = v->r;
if(cur->l != NULL) cur->l->p = cur; //v与cur角色转换
cur->p = v;
v->r = cur;
if(cur == root) root = v;
//printf("%d zigged\n", cur->k);
}
void zag(Node* cur){
if(cur == NULL) return ;
Node* v = cur->r;
if(v == NULL) return ;
Node* g = cur->p;
//printf("g=%d cur=%d v=%d\n", g->k, cur->k, v->k); v->p = g;
if(g != NULL)
(cur == g->l) ? g->l = v : g->r = v; cur->r = v->l;
if(cur->r != NULL) cur->r->p = cur; cur->p = v;
v->l = cur;
if(cur == root) root = v;
//printf("%d zagged\n", cur->k);
}
void splay(Node* x, Node* f){// make x become f's child
if(x == NULL) return ;
while(x->p != f){//逐步双层伸展
Node* p = x->p;
if(p == NULL) return ;
if(p->p == f)
(x == p->l) ? zig(p) : zag(p);
else{
Node* g = p->p;
if(g == NULL) return ;
if(g->l == p){
if(p->l == x){
zig(g); zig(p);
}else{
zag(p); zig(g);
}
}else{
if(p->l == x){
zig(p); zag(g);
}else{
zag(g); zag(p);
}
}
}
}
}
Node* search(Node* cur, int k){//在cur子树中查找关键码k
if(cur == NULL) return _hot;//查找失败还伸展吗？暂不伸展，待决定插入后再将新插入的节点伸展
if(cur->k == k){//查找成功
//printf("has %d\n", cur->k);
splay(cur, NULL);//将目标节点伸展至根
return cur;
}
_hot = cur;//需要深入子树查找
return (k < cur->k) ? search(cur->l, k) : search(cur->r, k);
}
Node* insert(Node* cur, int k){//将关键码k插入cur子树
if(cur == NULL){//找到目标插入位置
cur = new Node(k, _hot);
//printf("%d %d\n", _hot->k, k);
(k < _hot->k) ? _hot->l=cur : _hot->r=cur;
_hot = cur;
//printf("create %d\n", cur->k);
splay(cur, NULL);//将目标节点伸展至树根
return cur;
}
assert(cur);
_hot = cur;//进入子树
//printf("enter %d\n", cur->k);
return (k < cur->k) ? insert(cur->l, k) : insert(cur->r, k);//assert:关键码互异
}
Node* prev(int k){//寻找关键码k的中序前驱
splay(search(root, k), NULL);//将k伸展至树根
Node* cur = root->l;//根节点的左子树
//assert(cur);
if(!cur) return NULL;
while(cur->r != NULL) cur = cur->r;//前驱必然为左子树的最右节点
return cur;
}
Node* succ(int k){//寻找关键码k的中序后继, assert:k一定存在
splay(search(root, k), NULL);
Node* cur = root->r;
//assert(cur);
if(!cur) return NULL;
while(cur->l != NULL) cur = cur->l;
return cur;
}
void deleteK(int k){//删除关键码k
Node* p = prev(k);
Node* s = succ(k);
splay(p, NULL);
splay(s, p);
Node* q = s->l;
s->l = NULL;//解除父子关系
release(q);//释放子树空间，这里只有一个节点k
}
void deleteInterval(int a, int b){//删除区间[a,b]内的关键码
Node* pa = search(root, a);//pa为最后一个被访问的节点，必不空
assert(pa);
if(pa->k != a) pa = insert(pa, a);//查找失败，插入
//printf("pa->k = a = %d\n", pa->k); Node* pb = search(root, b);
assert(pb);
//printf("pb->k = b = %d\n", pb->k);
if(pb->k != b) pb = insert(pb, b); Node* p = prev(a);
assert(p);
Node* s = succ(b);//assert: p, s not null
assert(s);
//printf("prev %d succ %d\n", p->k, s->k);
splay(p, NULL);
//printf("%d splayed\n", p->k);
splay(s, p);
//printf("%d splayed\n", s->k);
Node* q = s->l;
_hot = s;
release(q);//释放子树空间
s->l = NULL;
}
}; int main()
{
FREAD("675d.txt");
RINT(n);
REP(n) RINT(a[i]);
Splay mySplay(a[]);
for(i=; i<n; i++){
// Node* p = mySplay.search(mySplay.root, a[i]);//必然失败
// if(p->k > a[i])
// printf("%d\n", mySplay.prev(p->k));
// else printf("%d\n", p->k);
int ans = ;
Node* q = mySplay.insert(mySplay.root, a[i]);
Node* p = mySplay.prev(a[i]);
if(p && right.count(p->k) == ){
right[p->k] = ;//前驱没有右孩子
ans = p->k;
}else{
Node* s = mySplay.succ(a[i]);
if(s && left.count(s->k) == ){
left[s->k] = ;
ans = s->k;
}
}
printf("%d\n", ans);
}
return ;
}
CF 675D Splay
再次做这道题，我对BST的认识更清晰了一些，在此梳理一下：
1. 首先，我们把中序遍历序列相同的二叉搜索树互称“等价BST”；可以看出，对于一个中序遍历序列，可以画出若干棵拓扑结构（即祖先后代的关系）不同的等价BST，且它们可以通过一些列“等价变换”而互相转换。常用的“等价变换”方法有我们熟悉的“旋转调整”，如下图（引自数据结构的课件）：
可以这样来记忆：zig是顺时针(clockwise)方向，zag是逆时针(anti-clockwise)方向；
而zig(p)或zag(p)可以形象地看成是“把p压下来，把它的孩子翘上去”。（注：hihocoder的教程和我的记法不太一样，习惯一种就好，不要搞混）
这样的zig/zag局部拓扑结构调整，在实现步骤上可以分如下三步走，代码上面有。
（1）v与p的祖先g建立连接 --->（2）v的孩子Y过继给p ---> （3）v与p角色互换
2. 平衡二叉搜索树在进行旋转调整时，树的拓扑结构发生了改变，而且这种改变如果不额外记录信息的话，是没办法直接从结果拓扑反推原始拓扑的。因为每一步调整都有若干种可能，纵使现成的红黑树set对外提供了父节点、孩子节点的接口，所返回的也是变换后的当前拓扑结构，无法直接得出原始拓扑。
3. 此题求的是原始拓扑结构中每次所插入的节点的父节点，数据范围10^5，不能承受退化情况的复杂度，故不可直接模拟，必须用平衡树来维护真实数据。而拓扑结构这一性质随着我们的旋转调整而发生了改变，所以必须想办法把原始拓扑结构记下来。而具体需要记录什么呢？
（1）经过上次博客的分析，我们发现节点v的父节点必然是其中序遍历的直接前驱或直接后继。我们先假设前驱和后继这个信息可以方便地得到，那么如何判定究竟是前驱还是后继呢？这个便是问题的关键所在了。由上次博客的结论，在原始拓扑中，若v作为前驱p的右孩子插入，则插入前p的右孩子必为空；与之对称的是s的左孩子为空的情况。那么我们只需记录原始拓扑中每个节点是否有左孩子、右孩子这一信息即可。因此用两个数组即可。不过这道题节点数值范围为10^9开不下，所以用了map。这个做法来自题目作者的题解。
（2）再来考虑如何确定v的前驱后继：无论怎么调整，等价BST的中序遍历序列是不变的，故节点v任意时刻的直接前驱和直接后继也不会改变，所以对前驱和后继的信息我们无需额外维护，而可以在任意时刻根据当前拓扑在O(logn)时间内求得。
说了这么多，一直在分析这道题，还没说到Splay。。。
Splay Tree（伸展树）是BBST家族中一种很“潇洒”的数据结构，实际上，它在很多情况下整体上并不处于“平衡状态”，即不能保证对所有节点的访问控制在O(logn)。但是它的设计很有现实意义，（最近复习计算机系统结构，发现它的设计理念十分符合“以经常性时间为重点”和“局部性原理”这两条系统结构设计的定量原理）。下面来具体看下它的设计思路：
1. 对于传统的平衡搜索树如AVL树，它假定每次对每个节点的访问是等概率的，所以每次动态操作后都“小心翼翼”地维护着平衡因子，从而使得最深的节点的访问成本也能控制在O(logn)。而现实情况中对数据的访问通常并不是等概率的，相反，它常具有局部性；在关注吞吐率而不是单次操作的场合，这一问题更为突出。
2. 这里我们转而关注连续访问一批数据的总体时间。要想总体时间少，我们采用贪心策略，让越经常被访问的节点访问成本越小，这一点和哈夫曼编码的设计如出一辙；然而此处的每个节点的“经常性”是动态变化的，可以有一部分历史数据作为“经验”，但通常要把每次访问的情况吸收到经验中作为下次调整的参考。
3. 由此得出Splay Tree的设计思路：按照“经常性”动态调整拓扑结构，一种实现方法就是：每次把刚刚访问过的节点调整到树根。
另，用教科书上的话说，这是一种“即用即调整的启发式策略”，是“自调整链表”的一种推广。（记得严蔚敏版《数据结构题集》线性表一章出现过“自调整链表”，当时我还傻傻地叫它“频度伸展链表”（https://github.com/helenawang/ywmDS/blob/master/LinkList/FreqList.c））
具体调整的实现，即伸展操作：和AVL树一样，伸展树的调整也分4种情况，而且其中“之字形”的两种的调整与AVL的双旋完全一致；
不同在于如下左图（再次盗用了数据结构的课件）这种“三代同侧”的情况：
（1）如左图上部，AVL通常只需做一次zig(p)的单旋便达到了局部的平衡；若想把v调成最高代，还要再做一次zig(g)的单旋；
（2）如左图下部，伸展树先做了一次zig(g)，再做一次zig(p)，把三代从“一边倒”调成了“另一边倒”；
（3）这两种做法的区别可从右图直观感受到，双层调整可以“折叠”沿途节点，从而降低树高。
注意伸展操作不只发生在动态操作后，每次查找操作也要进行伸展。对于删除操作，"hiho一下"的教程给出的做法很巧妙，即：找到待删除节点的前驱p和后继s，然后先把p伸展至树根，再把s伸展至p的右子树，至此，待删除节点（区间删除也可以）必然位于s的左子树，把左子树摘除并释放空间即可。代码如上，但是我提交后出现RE，原因尚不明，可能是释放空间后指针没置空。
hiho一下第104周 用java写的版本，可以AC
import java.util.*;
import java.util.Scanner; public class Main{
static int MIN_K = 0;
static int MAX_K = 1000000005;
public static void main(String[] args) {
Splay mySplay = new Splay(MIN_K);
mySplay.insert(mySplay.root, MAX_K); Scanner in = new Scanner(System.in);
int n = in.nextInt();
String c;
int k, a, b;
for(int i=0; i<n; i++){
c = in.next();
switch(c){
case "I":
k = in.nextInt();
mySplay.insert(mySplay.root, k);
break;
case "Q":
k = in.nextInt();
Node t = mySplay.search(mySplay.root, k);
if(k < t.k) t = mySplay.prev(k);
System.out.println(t.k);
break;
case "D":
a = in.nextInt(); b = in.nextInt();
mySplay.deleteInterval(a, b);
break;
default: break;
}
}
}
} class Splay {
Node root;
Node _hot;
Splay(){
root = _hot = null;
}
Splay(int k){
root = new Node(k, null);
_hot = root;
}
void zig(Node cur){
if(cur == null) return ;
Node v = cur.l;
if(v == null) return ;
Node g = cur.p; v.p = g;
if(g != null){
if(cur == g.l) g.l = v;
else g.r = v;
} cur.l = v.r;
if(cur.l != null) cur.l.p = cur; cur.p = v;
v.r = cur;
if(cur == root) root = v;
}
void zag(Node cur){
if(cur == null) return ;
Node v = cur.r;
if(v == null) return ;
Node g = cur.p; v.p = g;
if(g != null){
if(cur == g.l) g.l = v;
else g.r = v;
} cur.r = v.l;
if(cur.r != null) cur.r.p = cur; cur.p = v;
v.l = cur;
if(cur == root) root = v;
}
void splay(Node x, Node f){
if(x == null) return ;
while(x.p != f){
Node p = x.p;
if(p == null) return ;
if(p.p == f){
if(x == p.l){ zig(p);
}
else{
zag(p);
}
}else{
Node g = p.p;
if(g == null) return ;
if(g.l == p){
if(p.l == x){
zig(g); zig(p);
}else{
zag(p); zig(g);
}
}else{
if(p.l == x){
zig(p); zag(g);
}else{
zag(g); zag(p);
}
}
}
}
}
Node search(Node cur, int k){
if(cur == null) return _hot;
if(cur.k == k){
splay(cur, null);
return cur;
}
_hot = cur;
if(k < cur.k) return search(cur.l, k);
else return search(cur.r, k);
}
Node insert(Node cur, int k){
if(cur == null){
cur = new Node(k, _hot);
if(k < _hot.k) _hot.l = cur;
else _hot.r = cur;
_hot = cur;
//System.out.println("find place");
splay(cur, null);
//System.out.println(cur.k + "created");
return cur;
}
_hot = cur;
if(k < cur.k) return insert(cur.l, k);
else return insert(cur.r, k);
}
Node prev(int k){
splay(search(root, k), null);
Node cur = root.l;
if(cur == null) return null;
while(cur.r != null) cur = cur.r;
return cur;
}
Node succ(int k){
splay(search(root, k), null);
Node cur = root.r;
if(cur == null) return null;
while(cur.l != null) cur = cur.l;
return cur;
}
void deleteInterval(int a, int b){
Node pa = search(root, a);
if(pa.k != a) pa = insert(pa, a);
Node pb = search(root, b);
if(pb.k != b) pb = insert(pb, b); Node p = prev(a);
Node s = succ(b);
splay(p, null);
splay(s, p);
Node q = s.l;
_hot = s;
s.l = null;
}
}
class Node{
int k;
Node l, r;
Node p;
Node(){p = null;}
Node(int kk, Node pp){
k = kk;
p = pp;
l = r = null;
}
}
hiho104 Splay java版