Treap=Tree+Heap
Treap是一棵二叉搜索树，它的左子树和右子树分别是一个Treap，和一般的二叉搜索树不同的是，Treap结构中每个节点x有两个域，一个是其关键字值key，一个是优先级数priority（他是一个独立选取的随机数），对于Treap结构，其关键字遵循二叉搜索树性质，其优先级遵循堆性质。但是这里要注意的是Treap和二叉堆有一点不同，就是二叉堆必须是完全二叉树，而Treap可以并不一定是。
在这里用的链表实现的旋转的Treap，简单实现是思路比较简单，但代码稍微有点繁琐。有点懒，不想整理了。
TreapNode结构如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| template<class T>
struct treapNode
{
int key;//用于二叉搜索树的关键字
int pri;//用于堆性质的优先级数字
T element;//其中的元素
treapNode<T> *leftChild, //左子树
*rightChild,
*father; //右子树
treapNode() {leftChild = rightChild = father=NULL;}//构造函数
treapNode(const T& theElement):element(theElement)
{
leftChild = rightChild = father=NULL;
}
treapNode(const T& theElement,
treapNode *theLeftChild,
treapNode *theRightChild,
treapNode *theFather)
:element(theElement)
{
leftChild = theLeftChild;
rightChild = theRightChild;
father=theFather;
}
treapNode(int theKey,int thePri,T theElement)
{
key=theKey;
pri=thePri;
element=theElement;
leftChild = rightChild = father=NULL;
}
treapNode(int theKey,T theElement)
{
key=theKey;
pri=rand();
element = theElement;
leftChild=rightChild=father=NULL;
}
};
|
在节点中加入了父节点的指针，为了后面的旋转操作能够更简单一点，不加也是可以的，不过就要稍微复杂一点了。
插入操作：
不满足：当插入的节点为其父节点的左孩子时，应该右旋，否则左旋。
插入方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
| template<class T>
void treap<T>::insert(treapNode<T> *t)//插入方法，参数为一个treap节点。
{ t->leftChild=t->rightChild=t->father=NULL;
if(root==NULL)//当treap为空的时候情况
{
root=t;
treapSize++;
return ;
}
else//当treap不为空的时候，要找到要删除的位置
{
treapNode<T> *pp=root;
treapNode<T> *p=NULL;
while(pp!=NULL)
{ p=pp;
if(t->key<pp->key)//小于关键字时
pp=pp->leftChild;
else
{
if(t->key>pp->key)//大于关键字时
pp=pp->rightChild;
else//要插入的节点已经重复时
{
pp->element=t->element;
treapSize--;
return;
}
}
}
if(t->key>p->key)
{
p->rightChild=t;
t->father=p;
}
else
{
p->leftChild=t;
t->father=p;
}
}
treapNode<T> *q=t->father;//获取插入节点的父节点
//treapNode<T> *w=t->father;
int com;//判断是否循环继续的量
do//采用do-while结构，保证循环至少进行一次
{ com=0;
if(t->pri<q->pri&&t->key<q->key)//当优先级不满足堆的性质并且插入的节点在左孩子的位置时，此时应该右旋
{ if(t->rightChild!=NULL)//当插入节点的右孩子不为空的时候
{
q->leftChild=t->rightChild;//插入节点的右孩子变成其父节点的左孩子
t->rightChild->father=q;//插入节点的右孩子的父母指向插入节点的父母
t->rightChild=q;//父节点变为插入节点的右孩子
if(q->father!=NULL)//在这里分情况讨论，当其父节点的父节点不为空的时候
{
t->father=q->father;//插入节点的父节点为其父节点的父节点
if(q->father->leftChild==q)//判断父节点是否是父节点的父节点的左孩子
q->father->leftChild=t;//父节点的父节点左孩子变成插入节点
else
q->father->rightChild=t;
q->father=t; //父节点的父母变成插入节点
}
else//当其父节点的父节点为空时
{
t->father=NULL;//插入节点的父节点为空
root=t;
q->father=t;//父节点的父母变为插入节点
}
}
else//当插入节点的右孩子为空的时候
{ t->rightChild=q;
if(q->father!=NULL)//当其父节点的父节点不为空时
{
t->father=q->father;
if(q->father->leftChild==q) //判断父节点是否是父节点的父节点的左孩子
q->father->leftChild=t;
else
q->father->rightChild=t;
q->father=t;
q->leftChild=NULL;
}
else//当其父节点的父节点为空时
{
t->father=NULL;//父节点变为空
root=t;//此时根节点为当前插入的节点
t->rightChild=q;//插入节点的右孩子变为原来节点的父节点
q->father=t; //插入节点的父节点改成当前节点
q->leftChild=NULL;//插入节点的原来的父节点改为空值
}
} com=1;
}
if(t->pri<q->pri&&t->key>q->key)//当优先级不满足堆的性质并且插入的节点在右孩子的位置时，此时应该左旋
{ if(t->leftChild!=NULL)//当插入节点的左孩子不为空的时候
{
q->rightChild=t->leftChild;//插入节点的左孩子变成其父节点的右孩子
t->leftChild->father=q;//插入节点的左孩子的父母指向插入节点的父母
t->leftChild=q;//父节点变为插入节点的左孩子
if(q->father!=NULL)//在这里分情况讨论，当其父节点的父节点不为空的时候
{
t->father=q->father;//插入节点的父节点为其父节点的父节点
if(q->father->leftChild==q)//判断父节点是否是父节点的父节点的左孩子
q->father->leftChild=t;//父节点的父节点左孩子变成插入节点
else
q->father->rightChild=t;
q->father=t; //父节点的父母变成插入节点
}
else//当其父节点的父节点为空时
{
t->father=NULL;//插入节点的父节点为空
root=t;
q->father=t;//父节点的父母变为插入节点
q->leftChild=NULL;
}
}
else//当插入节点的左孩子为空的时候
{ t->leftChild=q;
if(q->father!=NULL)//当其父节点的父节点不为空时
{
t->father=q->father;
if(q->father->leftChild==q) //判断父节点是否是父节点的父节点的左孩子
q->father->leftChild=t;
else
q->father->rightChild=t;
q->father=t;
q->rightChild=NULL;
}
else//当其父节点的父节点为空时
{
t->father=NULL;
root=t;
t->leftChild=q;
q->father=t;
q->rightChild=NULL;
}
} com=1;
}
q=t->father;//更新插入节点的父节点
} while(q!=NULL&&com==1);//
treapSize++;
}
|
删除操作:
先找到要删除的节点的位置，然后判断要删除的节点的有几个孩子，然后再根据情况具体实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
| template<class T>
void treap<T>::erase(int key)
{
treapNode<T> *t=root;
while(t!=NULL)//首先找到要删除的节点
{
if(t->key<key)
t=t->rightChild;
else
{
if(t->key>key)
t=t->leftChild;
else//当相等时即找到要删除的节点了，跳出循环
break;
}
}
if(t==NULL)//treap中没有要删除的关键字的元素
{
cout<<"please put in correct data"<<key<<" ";
return ;
}
else//找到要删除的节点后
{
treapNode<T> *q=t->father;//找到要删除的节点的父节点
if(t->leftChild==NULL&&t->rightChild==NULL)//最简单的情况：当要删除的节点为叶节点时 ，并且此种情况下优先级的顺序不会改变
{
if(t==root)//其中的特殊情况：只有一个节点，即根节点
root=NULL;
else//不为根节点
{
if(key<q->key)//判断是左孩子还是右孩子
q->leftChild=NULL;
else
q->rightChild=NULL;
t->father=NULL;//让此节点的父节点为空
//t=NULL;//释放此节点
}
}
if((t->leftChild==NULL&&t->rightChild!=NULL)||(t->leftChild!=NULL&&t->rightChild==NULL))//当要删除的节点为有一个孩子时
{
if(q==NULL)//当要删除的节点为根节点时
{
if(t->leftChild!=NULL)//如果左孩子不为空
{ t->leftChild->father=NULL;
root=t->leftChild;
t->leftChild=NULL;
}
else//右孩子不为空
{
t->rightChild->father=NULL;
root=t->rightChild;
t->rightChild=NULL;
}
}
else//删除的节点不为根节点时
{
if(t->key<q->key)//当为其左孩子时
{
if(t->leftChild!=NULL)//当要删除的节点的左孩子不为空时
{
q->leftChild=t->leftChild;//删除节点的父节点的左孩子指向删除节点的左孩子
t->leftChild->father=q;//删除节点的左孩子的父亲指向删除节点的父亲
t->leftChild=NULL;//删除节点的左孩子指针指向空
t->father=NULL;//其父节点的指针指向空
}
else//当要删除的右孩子不为空时
{
q->leftChild=t->rightChild;
t->rightChild->father=q;
t->rightChild=NULL;
t->father=NULL;
}
}
else//当为其右孩子时
{
if(t->leftChild!=NULL)//当要删除的节点的左孩子不为空时
{
q->rightChild=t->leftChild;
t->leftChild->father=q;
t->leftChild=NULL;
t->father=NULL;
//t=NULL;
}
else//当删除的节点的右孩子不为空时
{
q->rightChild=t->rightChild;
t->rightChild->father=q;
t->rightChild=NULL;
t->father=NULL;
//t=NULL;
}
}
}
}
if(t->leftChild!=NULL&&t->rightChild!=NULL)//左右孩子均不为空的情况
{
if(t->leftChild->pri<t->rightChild->pri)//找出左右孩子中优先级较小的那个
{treapNode<T> *p=t->leftChild;//记录下当前节点的左孩子
if(p->rightChild==NULL)//当左孩子的右孩子为空时
{
if(q==NULL)//如果待删节点为根节点
{
p->rightChild=t->rightChild;
p->father=NULL;
t->rightChild->father=p;
t->leftChild=t->rightChild=NULL;
//t=NULL;
root=p;
}
else//待删节点不为根节点
{
p->rightChild=t->rightChild;
t->rightChild->father=p;
p->father=q;
if(q->leftChild==t)
q->leftChild=p;
else
q->rightChild=p;
t->father=t->leftChild=t->rightChild=NULL;
//t=NULL;
}
}
else//当左孩子的右孩子不为空时
{
t->father=p;
t->leftChild=p->rightChild;
p->rightChild->father=t;
p->rightChild=t;
if(q==NULL)
{
p->father=NULL;
root=p;
}
else
{
p->father=q;
if(q->leftChild==t)
q->leftChild=p;
else
q->rightChild=p;
}
erase(key);
}
}
else//找出左右孩子中优先级较小的那个
{treapNode<T> *p=t->rightChild;//记录下当前节点的右孩子
if(t->rightChild->leftChild==NULL)//当右孩子的左孩子为空时
{
if(q==NULL)//如果待删节点为根节点
{
p->leftChild=t->leftChild;
p->father=NULL;
t->leftChild->father=p;
t->leftChild=t->rightChild=NULL;
//t=NULL;
root=p;
}
else//待删节点不为根节点
{
p->leftChild=t->leftChild;
t->leftChild->father=p;
p->father=q;
if(q->leftChild==t)
q->leftChild=p;
else
q->rightChild=p;
t->father=t->leftChild=t->rightChild=NULL;
//t=NULL;
}
}
else//当右孩子的左孩子不为空时
{
t->father=p;
t->rightChild=p->leftChild;
p->leftChild->father=t;
p->leftChild=t;
if(q==NULL)
{
p->father=NULL;
root=p;
}
else
{
p->father=q;
if(q->leftChild==t)
q->leftChild=p;
else
q->rightChild=p;
}
erase(key);
}
}
}
treapSize--;
}
}
|