伸展树深入解析（第三部分）：核心代码详解与应用

 上一篇里把源代码贴出来了&＃xff01;这里就一点点来分析&＃xff01;

首先第一步建树&＃xff1a;

1.  #define INF ~0u>>1 
2.  #define NIL SPLAY 
3.  #define MN 200005 
4.  using namespace std; 
5.  int n,m,l,r,x,pos; 
6.  char s[10]; 
7.  struct SPLAYTREE{ 
8.      struct NODE{ 
9.          int key,minv,size,add; 
10.          bool rev; 
11.          NODE *left,*right,*father; 
12.          NODE (){} 
13.          NODE(int _key):key(_key){minv&＃61;_key,size&＃61;1,add&＃61;0,rev&＃61;false;} 
14.      }SPLAY[MN],*SP,*root,*head,*tail; 
15. }tree; 

这句宏定义&＃xff1a;

1. #define INF ~0u>>1 

的意思等同于&＃xff1a;

1. #define INF 0x7FFFFFFF 

"u"是表示unsigned int&＃xff0c;这里呢就是先把无符号整型0取反&＃xff0c;然后右移一位。

第二点很难理解的就是: NODE(int _key):key(_key)

这句代码主要是理解C&＃43;&＃43;中new关键字的应用&＃xff1a;(http://sbp810050504.blog.51cto.com/2799422/1026483)这里面讲得挺好的&＃xff01;

head指针与tail指针在《运用伸展树解决数列维护问题》中讲到了&＃xff0c;就是在提取一段区间时&＃xff0c;为了更方便操作&＃xff0c;人为了增加两个结点&＃xff0c;这两个结点不能影响树的结构。

接着就是树的初始化了&＃xff1a;

1. //对伸展树进行初始化&＃xff0c;也就是把head和tail加入到树中&＃xff0c; 
2.     void init(){ 
3.         SP&＃61;NIL; 
4.         NIL->key&＃61;NIL->minv&＃61;INF; 
5.         NIL->size&＃61;0; 
6.         NIL->rev&＃61;false;NIL->add&＃61;0;//用于懒操作的 
7.         NIL->left&＃61;NIL->right&＃61;NIL->father&＃61;NIL; 
8.         head&＃61;new(&＃43;&＃43;SP)Node(INF); 
9.         head->left&＃61;head->right&＃61;head->father&＃61;NIL; 
10.         tail&＃61;new(&＃43;&＃43;SP)Node(INF); 
11.         tail->left&＃61;tail->right&＃61;tail->father&＃61;NIL; 
12.         head->right&＃61;tail;tail->father&＃61;head; 
13.         head->size&＃43;&＃43;; 
14.         root&＃61;head; 
15.     } 

把初始化与前面的关键字new的用法结合起来&＃xff0c;就能体会到作者C&＃43;&＃43;语言的功底了&＃xff1a;西漂亮&＃xff0c;优雅&＃xff01;也能理解到SP指针是干嘛的了&＃xff01;

   为了更好的理解&＃xff0c;我把树打印出来&＃xff1a;即先插入一段数据&＃xff0c;然后按下标的顺序把数据打印出来&＃xff01;

1. #include  
2.  
3. #define INF ~0u>>1 
4. #define MN 200005 
5. #define NIL SPLAY 
6. using namespace std; 
7. struct SplayTree{ 
8.          struct Node{ 
9.              int key,minv,size,add; 
10.              bool rev; 
11.              Node *left,*right,*father; 
12.              Node(){} 
13.              Node(int _key):key(_key){minv&＃61;_key,size&＃61;1,add&＃61;0,rev&＃61;false;} 
14.          }SPLAY[MN],*SP,*root,*head,*tail; 
15. // 
16. //  //对伸展树进行初始化&＃xff0c;也就是把head和tail加入到树中&＃xff0c; 
17.     void init(){ 
18.         SP&＃61;NIL; 
19.         NIL->key&＃61;NIL->minv&＃61;INF; 
20.         NIL->size&＃61;0; 
21.         NIL->rev&＃61;false;NIL->add&＃61;0;//用于懒操作的 
22.         NIL->left&＃61;NIL->right&＃61;NIL->father&＃61;NIL; 
23.         head&＃61;new(&＃43;&＃43;SP)Node(INF); 
24.         head->left&＃61;head->right&＃61;head->father&＃61;NIL; 
25.         tail&＃61;new(&＃43;&＃43;SP)Node(INF); 
26.         tail->left&＃61;tail->right&＃61;tail->father&＃61;NIL; 
27.         head->right&＃61;tail;tail->father&＃61;head; 
28.         head->size&＃43;&＃43;; 
29.         root&＃61;head; 
30.     } 
31.     //暂时只维护区间&＃xff0c;不作伸展操作 
32.     void splay(Node *&root,Node *&t){ 
33.  
34.     } 
35.     //往第pos位后插入key 
36.     void insert(int key,int pos){ 
37.         Node *t;t&＃61;new(&＃43;&＃43;SP)Node(key); 
38.         t->left&＃61;t->right&＃61;t->father&＃61;NIL; 
39.  
40.         Node *r,*p;r&＃61;root; 
41.         bool flag&＃61;false;//默认朝左边走 
42.         while(r!&＃61;NIL){ 
43.             p&＃61;r;r->size&＃43;&＃43;; 
44.             if(r->left->size&＃43;1>pos)r&＃61;r->left,flag&＃61;false; 
45.             else pos-&＃61;r->left->size&＃43;1,r&＃61;r->right,flag&＃61;true; 
46.         } 
47.         if(flag)p->right&＃61;t; 
48.         else p->left&＃61;t; 
49.         t->father&＃61;p; 
50.         splay(root,t); 
51.     } 
52.     void inorder(Node *t){ 
53.         if(t->left!&＃61;NIL) 
54.             inorder(t->left); 
55.         printf("%d ",t->key); 
56.         if(t->right!&＃61;NIL) 
57.             inorder(t->right); 
58.  
59.     } 
60. }tree; 
61. //这里需要注意的是&＃xff0c;SplayTree一定要定义成全局变量&＃xff0c;不然会因为栈溢出而报内存错误 
62. int main(){ 
63.     int a[10]&＃61;{0,9,8,7,6,5,4,3,2,1};//a[0]位置的数据不用 
64.     int i; 
65.     //初始化 
66.     tree.init(); 
67.     //插入数据 
68.     for(i&＃61;1;i<10;i&＃43;&＃43;){ 
69.         tree.insert(a[i],i); 
70.     } 
71.     //按下标的顺序输出 
72.     tree.inorder(tree.head); 
73.     return 0; 
74. } 

 这里的伸展树退化成了一棵维护区间的二叉查找树&＃xff01;记住是维护区间&＃xff0c;像线段树一样&＃xff0c;不会数据进行排序&＃xff0c;只会维护区间。由于伸展树跟线段树很像&＃xff0c;所以有的代码写法很像线段树&＃xff01;其本质我觉得是一样的&＃xff0c;只是代码组织的方式不同罢了。当然上面这样我更容易理解&＃xff01;

    而实际上&＃xff0c;如果不做伸展操作&＃xff0c;加入的数据在树中就会变成如下的形式&＃xff1a;链式的数据其性能的很低的&＃xff0c;所以必须做伸展操作&＃xff1a;

这恰恰与《运用伸展树解决数列维护问题》中描述的“在伸展树中对区间进行操作”是一样的&＃xff01;而根结点的右孩子的左子树就是要维护的区间。