0%

23树的一种删除方法

23树的一种删除方法

似乎网上没有什么对于23树删除时候的教程

即使是有的那些也是躲躲闪闪,不讲个明白,本文尽我最大的可能将这个操作讲明白(最后还是鸽了

不同于本人的别的blog,这次本人花巨资画了示意图(

但是这个blog别人也看不到呀((

参考资料

网上的2-3树教程

挺可惜的是这篇2-3树有两种删除时候的情况没有讨论,可能是太简单了吧(

删除

分析大纲

为了保证排版我用缩进简单介绍一下思路

1
2
3
4
5
6
7
8
9
10
11
12
13
删除的是非叶子结点

删除的是叶子结点
删除的是3type结点

删除的是2type结点
2type结点的父亲是2type结点
2type结点的兄弟是2type结点
2type结点的兄弟是3type结点

2type结点的父亲是3type结点
2type结点存在一个兄弟是2type结点
2type结点存在一个兄弟是3type结点

首先我们要删除一个结点的话。

我们要找到那个结点在哪里。

我们首先根据删除结点的情况进行分类。

  1. 要删除的结点不是叶子结点

  2. 要删除的结点是叶子结点


删除的不是叶子结点

这时候我们找到这个结点的后继,然后把后继的值和要删除结点的值swap一下。

然后只需要删除后继就好了。

那…为什么要这么做呢,一来这样依旧能够保证整棵树的中序遍历的正确性。

此外这个结点的后继一定是一个叶子!我们接下来就来证明这个结论。


一个非叶子结点的后继一定是一个叶子

如果你学过其他的种类的平衡树的话,你会发现这个性质是一般平衡树所没有的。

例如

其中5结点的后继6就不是一个叶子

原因在于5的后继可能有右儿子,但是在2-3树中保证了除叶子节点外,每个分支节点的儿子数量是满的,于是意味着一个结点一旦有儿子,则一定有很多儿子,这个它是一个后继相矛盾,可以自己想想。


一个非叶子结点的后继一定在右儿子中

这个也是普通平衡树所没有的性质。

举个栗子。

考虑5的后继,显然得到了后继不一定在右儿子中的结论。

由于2-3保证了所有分支结点一定有多个儿子,于是证明显然。

有了以上两条性质的保证。我们就可以知道经过上面两个步骤,一个删除非叶子结点的操作,被转化成了一个删除叶子结点的操作。


删除的是叶子结点

于是本质上只有删除的是叶子结点的操作。

我们考虑接着来分析问题


删除的是3type结点

由于这个叶子结点有多个值,直接删掉那个,然后把这个结点改成2type结点就好了。

举个栗子。


删除的是2type结点

这个时候我们肯定不能直接把这个结点删了,不然树就不一样高了。

于是我们只能寻求它的父亲或者兄弟的帮助。

继续进行分类讨论

  1. 2type结点的父亲是3type结点
  2. 2type结点的父亲是2type结点

2type结点的父亲是2type结点 且有一个3type兄弟

其中A代表被删除的叶子,这样调整一下顺序就完成了调整过程。


2type结点的父亲是2type结点 且有一个2type兄弟

A是要被删除的结点,经过这样的调整,把A拉到了最上面,但是并没有完全处理完成,需要继续向上递归,不过我们先完成对删除叶子一步的操作,之后我们再统一讨论如果递归地处理。


2type结点的父亲是3type结点 且有一个兄弟是2type结点

删除A结点,只需要将B和C压成一个结点并且把父亲变成2type就好了,再次注意这里A是个叶子,A是子树的情况之后再讨论


2type结点的父亲是3type结点 且有一个兄弟是3type结点

思路类似在此不再赘述。


对于递归处理的讨论

可以发现对于删除A这个叶子的一步操作中只有2type结点的父亲是2type结点 且有一个2type兄弟这种情况下,我们必须要进行向上递归处理。

观察这个时候,向上处理时$A$是一颗子树,且之后一个儿子,这个性质非常关键。

事实上下面的讨论与上面的讨论的区别就在于,被删除的结点A从一个叶子,变成了一个只有一个儿子的且根为A的子树的根。

递归时A也会遇到

  1. 2type结点的父亲是2type结点 且有一个3type兄弟
  2. 2type结点的父亲是2type结点 且有一个2type兄弟
  3. 2type结点的父亲是3type结点 且有一个兄弟是2type结点
  4. 2type结点的父亲是3type结点 且有一个兄弟是3type结点

这4种情况


2type结点的父亲是2type结点 且有一个3type兄弟

由于现在A不再是叶子了,于是讨论要加上子树。

调整如图


2type结点的父亲是2type结点 且有一个2type兄弟

调整方式如下,可以发现这种情况下还需要继续向上递归


2type结点的父亲是3type结点 且有一个兄弟是2type结点

调整方式如下


2type结点的父亲是3type结点 且有一个兄弟是3type结点

调整方法如下


综合以上3种情况,可以发现还是只有一种情况需要继续向上递归,这时依旧满足子书中只有一个儿子,于是可以继续上面的过程

最终要么终止于没有父亲,要么终止于其他3种情况

递归过程中没有父亲

这时需要重新指定整个2-3树的根


完结散花(

贴个代码吧

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
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;
template<typename T>
class _23Tree{
private:
struct Node{
Node *ch[4], *fa;
T data[3];
unsigned int height;
bool isThree;
};
Node *createNode();
Node *root;
void maintain(Node *x);
void erase_maintain(Node *);
void _display(Node *x);
Node *_find(T);
public:
_23Tree();
unsigned int getHeight()const;
void insert(T);
void erase(T);
bool find(T);
void display();
};

template<typename T>
_23Tree<T>::_23Tree(){
root = nullptr;
}

template<typename T>
typename _23Tree<T>::Node *_23Tree<T>::createNode(){
Node *t = new Node();
// clear node
for(int i = 0; i < 3; i++)t->ch[i] = nullptr;
t->fa = nullptr;
t->height = 0;
t->isThree = false;
return t;
}

template<typename T>
void _23Tree<T>::maintain(_23Tree<T>::Node *x){
// maintain for a single tree
// whose father is to be inserted
// initially x's father exists
Node *y = x->fa;
if(y->isThree){
// when x's father is 3-type

//find the loc
int ch_loc = 0;
for(int i = 0; i < 3 ; i++){
if(y->ch[i] == x) {
ch_loc = i;
break;
}
}

//insert the pointers into y
for(int i = 3; i > ch_loc; i--){
y->ch[i] = y->ch[i - 1];
}
y->ch[ch_loc] = x->ch[0];
y->ch[ch_loc+1] = x->ch[1];
for(int i = 0 ; i < 4; i++){
y->ch[i]->fa = y;
}

//insert data into y
y->data[2] = x->data[0];
sort(y->data, y->data+3);

//split y
Node *tmp = createNode();
Node *p1 = createNode();
Node *p2 = createNode();
tmp->data[0] = y->data[1];
p1->data[0] = y->data[0];
p2->data[0] = y->data[2];

p1->ch[0] = y->ch[0];
p1->ch[1] = y->ch[1];
p2->ch[0] = y->ch[2];
p2->ch[1] = y->ch[3];
p1->fa = p2->fa = tmp;
p1->ch[0]->fa = p1->ch[1]->fa = p1;
p2->ch[0]->fa = p2->ch[1]->fa = p2;
tmp->ch[0] = p1;
tmp->ch[1] = p2;
p1->height = p2->height = y->height;
tmp->height = p1->height + 1;

// exchange y's father
Node *z = y->fa;
tmp->fa = z;
if(z == nullptr){
root = tmp;
}else{
int child_size = z->isThree ? 3 : 2;
for(int i=0;i<child_size ;i++){
if(z->ch[i] == y){
child_size = i;
break;
}
}
z->ch[child_size] = tmp;
delete y;
maintain(tmp);
}

}else{
// when x's father is 2-type
y->isThree = true;
//find the loc
int ch_loc = 0;
for(int i = 0; i < 2; i++){
if(y->ch[i] == x){
ch_loc = i;
break;
}
}
ch_loc ^= 1;

// insert the pointer into y
if(ch_loc == 0){
y->ch[1] = x->ch[0];
y->ch[2] = x->ch[1];
}else{
y->ch[2] = y->ch[1];
y->ch[0] = x->ch[0];
y->ch[1] = x->ch[1];
}
for(int i=0;i<3;i++){
y->ch[i]->fa = y;
}

//insert the data into y
y->data[1] = x->data[0];
std::sort(y->data, y->data+2);
delete x;
}
}

template<typename T>
unsigned int _23Tree<T>::getHeight()const{
return root->height;
}

template<typename T>
void _23Tree<T>::insert(T x){
Node *cur = root;
if(cur == nullptr){
root = createNode();
root->data[0] = x;
return;
}
Node *y = cur;
while(cur != nullptr){
int R = cur->isThree ? 2 : 1;
int i;
for(i = 0; i < R; i++){
if(cur -> data[i] < x){
// break;
}else{
break;
}
}
// i = min(i, R-1);
y = cur;
cur = cur->ch[i];
}
if(y->isThree){
//insert new node
y->data[2] = x;
std::sort(y->data, y->data+3);

// cur is y's father
cur = y->fa;

// split 4-type node
Node *tmp = createNode();
Node *p1 = createNode();
Node *p2 = createNode();
p1->data[0] = y->data[0];
tmp->data[0] = y->data[1];
p2->data[0] = y->data[2];
tmp->ch[0] = p1;
tmp->ch[1] = p2;
p1->fa = tmp;
p2->fa = tmp;
tmp->height = 1;
tmp->fa = y->fa;

//exchange cur's son to the new 3 node
//when father is nullptr
if(cur == nullptr){
root = tmp;
delete y;
return;
}
//when father exists
int child_size = (cur->isThree ? 3 : 2);
for(int i = 0; i < child_size; i++){
if(cur -> ch[i] == y){
child_size = i;
break;
}
}
cur->ch[child_size] = tmp;
tmp->fa = cur;
delete y;

//update recursively
maintain(tmp);

}else{
y->data[1] = x;
std::sort(y->data, y->data+2);
y->isThree = true;
}
}

template<typename T>
void _23Tree<T>::erase(T v) {
Node *x = _find(v);
if(x == nullptr) return;
if(x->ch[0] == nullptr){
// x is leaf
if(x->isThree){
int child_size = x->isThree ? 2 : 1;
x->isThree = false;
int loc = 0;
for(loc = 0; loc < child_size; loc++){
if(x->data[loc] != v)break;
}
swap(x->data[loc], x->data[0]);
x->data[1] = T{};
}else{
erase_maintain(x);
}
}else{
// x is not leaf
int loc = 0;
int child_size = x->isThree ? 2 : 1;
for(loc = 0; loc < child_size; loc ++){
if(x->data[loc] == v)break;
}
assert(loc < child_size);

// find next in InOrder
Node *y = x->ch[loc + 1];
while(y->ch[0] != nullptr)
y = y->ch[0];
x->data[loc] = y->data[0];

if(y->isThree){
int child_size = y->isThree ? 2 : 1;
y->isThree = false;
swap(y->data[1], y->data[0]);
y->data[1] = T{};
}else{
erase_maintain(y);
}

}

}

template<typename T>
bool _23Tree<T>::find(T v) {
return (_find(v) != nullptr);
}

template<typename T>
void _23Tree<T>::display() {
_display(root);
}

template<typename T>
void _23Tree<T>::_display(_23Tree::Node *x) {
// cout << x << endl;
if(x == nullptr) return;

int child_size = x->isThree ? 2 : 1;
//son list
_display(x->ch[0]);
for(int i=0;i<child_size;i++){
cout << x->data[i] << " " << x->height << endl;
_display(x->ch[i+1]);
}
}

template<typename T>
typename _23Tree<T>::Node *_23Tree<T>::_find(T v) {
Node *x = this->root;
while(x != nullptr){
int child_size = x->isThree ? 2 : 1;
bool flag = false;
for(int i=0;i<child_size;i++){
if(x->data[i] == v)flag = true;
}
if(flag) break;
int i = 0;
for(i=0;i<child_size;i++){
if(v < x->data[i])break;
}
x = x->ch[i];
}
return x;
}

template<typename T>
void _23Tree<T>::erase_maintain(_23Tree::Node *x) {
int child_size = x->isThree ? 2 : 1;
// x is 2-type node
Node *y = x->fa;
if(y == nullptr){
// when father doesn't exist
root = x->ch[1];
}else{
// when father exists

//find x's location in y
child_size = y->isThree ? 2 : 1;
int loc = -1;
for(int i=0; i<= child_size; i++){
if(y->ch[i] == x){
loc = i;
break;
}
}
assert(loc != -1);

if(y -> isThree){
// father is 3-type node
int to = 0;
if(loc == 0)to = 1;
if(loc == 1)to = 2;
if(loc == 2)to = 1;
Node *w = y->ch[to];
if(w->isThree){
if(loc == 0){
if(x->ch[0] == nullptr) x->ch[0] = x->ch[1];
x->data[0] = y->data[0];
y->data[0] = w->data[0];
w->data[0] = w->data[1];
w->data[1] = T{};
w->isThree = false;
x->ch[1] = w->ch[0];
for(int i=0;i<=1;i++)w->ch[i] = w->ch[i+1];
w->ch[2] = nullptr;
if(x->ch[1]!=nullptr)x->ch[1]->fa = x;
}else if(loc == 1){
if(x->ch[0] == nullptr) x->ch[0] = x->ch[1];
x->data[0] = y->data[1];
y->data[1] = w->data[0];
w->data[0] = w->data[1];
w->data[1] = T{};
w->isThree = false;
x->ch[1] = w->ch[0];
for(int i=0;i<=1;i++)w->ch[i] = w->ch[i+1];
w->ch[2] = nullptr;
if(x->ch[1]!=nullptr)x->ch[1]->fa = x;
}else{
if(x->ch[1] == nullptr) x->ch[1] = x->ch[0];
x->data[0] = y->data[1];
y->data[1] = w->data[1];
w->data[1] = T{};
w->isThree = false;
x->ch[0] = w->ch[2];
w->ch[2] = nullptr;
if(x->ch[0]!=nullptr)x->ch[0]->fa = x;
}
}else{
if(loc == 0){
w->isThree = true;
w->data[1] = w->data[0];
w->data[0] = y->data[0];
y->data[0] = y->data[1];
y->data[1] = T{};
y->isThree = false;
for(int i=0;i<=1;i++)y->ch[i] = y->ch[i+1];
y->ch[2] = nullptr;
for(int i=1;i>=0;i--)w->ch[i+1] = w->ch[i];
w->ch[0] = x->ch[0]==nullptr ? x->ch[1] : x->ch[0];
for(int i=0;i<=2;i++)if(w->ch[i]!=nullptr)w->ch[i]->fa = w;
delete x;
}else if(loc == 1){
w->isThree = true;
w->data[1] = w->data[0];
w->data[0] = y->data[1];
y->data[1] = T{};
y->isThree = false;
y->ch[1] = y->ch[2];
y->ch[2] = nullptr;
for(int i=1;i>=0;i--)w->ch[i+1] = w->ch[i];
w->ch[0] = x->ch[0]==nullptr ? x->ch[1] : x->ch[0];
for(int i=0;i<=2;i++)if(w->ch[i]!=nullptr)w->ch[i]->fa = w;
delete x;
}else{
w->isThree = true;
w->data[1] = y->data[1];
y->data[1] = T{};
y->isThree = false;
y->ch[2] = nullptr;
w->ch[2] = x->ch[0]==nullptr ? x->ch[1] : x->ch[0];
for(int i=0;i<=2;i++)if(w->ch[i]!=nullptr)w->ch[i]->fa = w;
delete x;
}
}
}else{
// father is 2-type node
Node* w = y->ch[loc^1];
if(w->isThree){
w->isThree = false;
if(loc == 1){
x->data[0] = y->data[0];
y->data[0] = w->data[1];
w->data[1] = T{};
if(x->ch[1] == nullptr) x->ch[1] = x->ch[0];
x->ch[0] = w->ch[2];
w->ch[2] = nullptr;
if(x->ch[0] != nullptr)x->ch[0]->fa = x;
}else{
x->data[0] = y->data[0];
y->data[0] = w->data[0];
w->data[0] = w->data[1];
w->data[1] = T{};
if(x->ch[0] == nullptr) x->ch[0] = x->ch[1];
x->ch[1] = w->ch[0];
w->ch[0] = w->ch[1];
w->ch[1] = w->ch[2];
w->ch[2] = nullptr;
if(x->ch[1] != nullptr)x->ch[1]->fa = x;
}
}else{
w->isThree = true;
w->data[1] = y->data[0];
//y->data[0] = 20000526;
sort(w->data, w->data+2);
if(x->ch[0] == nullptr) x->ch[0] = x->ch[1];
if(loc == 0){
w->ch[2] = w->ch[1];
w->ch[1] = w->ch[0];
w->ch[0] = x->ch[0];
if(w->ch[0] != nullptr)w->ch[0]->fa = w;
}else{
w->ch[2] = x->ch[0];
if(w->ch[2] != nullptr)w->ch[2]->fa = w;
}
y->ch[loc] = nullptr;
delete x;
erase_maintain(y);
}
}
}

}

int data[100000];
int main(int argc, char **argv){
// freopen("1.txt","w",stdout);
srand(0);
_23Tree<int> x;
int n = 20;
for(int i=1;i<=n;i++)
data[i] = i;
random_shuffle(data+1, data+1+n);
for(int i=1;i<=n;i++){
x.insert(data[i]);
}

for(int i=1;i<=n/4;i++){
x.erase(data[i]);
cout << "erase " << data[i] << endl;
// x.display();
}
x.display();
cout << x.getHeight() << endl;
return 0;
}
abab