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
| #pragma once
#include "../algorithm/general.h"
#include "../memery_management/memery_pool.h"
#include "search_tree.h"
namespace data_structure {
template <class T>
class aa_tree : public search_tree<T> {
struct node {
node *l, *r;
int h;
T key;
};
memery_pool<node> pool;
node* root;
void copy_self(node*& rt, node* cp) {
if (cp == nullptr) return;
rt = pool.get();
rt->key = cp->key;
rt->h = cp->h;
copy_self(rt->l, cp->l);
copy_self(rt->r, cp->r);
}
void delete_self(node* rt) {
if (rt == nullptr) return;
delete_self(rt->l);
delete_self(rt->r);
pool.erase(rt);
}
node* newnode(const T& w) {
node* res = pool.get();
res->l = res->r = nullptr;
res->h = 1;
res->key = w;
return res;
}
node* zig(node* rt) {
node* ls = rt->l;
rt->l = ls->r;
ls->r = rt;
return ls;
}
node* zag(node* rt) {
node* rs = rt->r;
rt->r = rs->l;
rs->l = rt;
return rs;
}
node* skew(node* rt) {
if (rt == nullptr) return rt;
if (rt->l != nullptr && rt->l->h == rt->h) {
rt = zig(rt);
}
return rt;
}
node* split(node* rt) {
if (rt == nullptr) return rt;
if (rt->r != nullptr && rt->r->r != nullptr && rt->h == rt->r->r->h) {
rt = zag(rt);
rt->h++;
}
return rt;
}
node*& search(node*& rt, const T& w) {
if (rt == nullptr)
return rt;
else if (w < rt->key)
return search(rt->l, w);
else if (rt->key < w)
return search(rt->r, w);
else
return rt;
}
node* insert(node* rt, const T& w) {
if (rt == nullptr)
return newnode(w);
else if (w < rt->key)
rt->l = insert(rt->l, w);
else if (rt->key < w)
rt->r = insert(rt->r, w);
return split(skew(rt));
}
node* erase(node* rt, const T& w) {
if (rt == nullptr) {
return rt;
} else if (w < rt->key) {
rt->l = erase(rt->l, w);
} else if (rt->key < w) {
rt->r = erase(rt->r, w);
} else {
if (rt->l != nullptr) {
node* tmp = rt->l;
while (tmp->r != nullptr) tmp = tmp->r;
rt->l = erase(rt->l, rt->key = tmp->key);
} else if (rt->r != nullptr) {
node* tmp = rt->r;
while (tmp->l != nullptr) tmp = tmp->l;
rt->r = erase(rt->r, rt->key = tmp->key);
} else {
pool.erase(rt);
return nullptr;
}
}
int hl = rt->l == nullptr ? 0 : rt->l->h;
int hr = rt->r == nullptr ? 0 : rt->r->h;
if (hl == rt->h - 2) {
if (hr == rt->h - 1) {
rt->h--;
rt = split(rt);
} else {
rt->h--;
rt->r->h--;
rt->r = skew(rt->r);
if (rt->r != nullptr) rt->r->r = skew(rt->r->r);
rt = split(rt);
rt->r = split(rt->r);
}
} else if (hr == rt->h - 2) {
rt->h--;
rt = skew(rt);
rt->r = skew(rt->r);
rt = split(rt);
}
return rt;
}
void preorder(node*& rt, void (*f)(const T&)) {
if (rt == nullptr) return;
f(rt->key);
preorder(rt->l, f);
preorder(rt->r, f);
}
void midorder(node*& rt, void (*f)(const T&)) {
if (rt == nullptr) return;
midorder(rt->l, f);
f(rt->key);
midorder(rt->r, f);
}
void test(node* rt) {
if (rt == nullptr) return;
if (rt->l == nullptr && rt->r == nullptr)
assert(rt->h == 1);
if (rt->l != nullptr)
assert(rt->l->h == rt->h - 1);
if (rt->r != nullptr) {
assert(rt->r->h == rt->h - 1 ||
rt->r->h == rt->h);
if (rt->r->r != nullptr) assert(rt->r->r->h < rt->h);
}
if (rt->h > 1)
assert(rt->l != nullptr && rt->r != nullptr);
test(rt->l);
test(rt->r);
}
public:
aa_tree() { root = nullptr; }
aa_tree(const aa_tree<T>& rhs) { copy_self(root, rhs.root); }
aa_tree<T> operator=(const aa_tree<T>& rhs) {
delete_self(root);
copy_self(root, rhs.root);
return *this;
}
~aa_tree() { delete_self(root); }
void insert(const T& w) { root = insert(root, w); }
node*& search(const T& w) { return search(root, w); }
void erase(const T& w) { root = erase(root, w); }
void preorder(void (*f)(const T&)) { preorder(root, f); }
void midorder(void (*f)(const T&)) { midorder(root, f); }
void test() { test(root); }
};
}
|
为了改进，他提出了使用23树并强行要求3节点(2key-3son-node)向右倾斜，于是，我们只剩下两种情况(图片源于wiki) 
为了更加容易编码，他提出不再使用红黑来标识节点，而是选择高度，这里的高度指的是黑高度，即黑色节点的高度，学习过左偏树(左翼堆)或斜堆的读者应该对这里不太陌生，这里的高度其实和左偏树或斜堆中的右距离是同一个东西。 ## AA树的特性 >所有叶节点的level都是1 >每个左孩子的level恰好为其父亲的level减一 >每个右孩子的level等于其父亲的level或为其父亲的level减一 >每个右孙子的level严格小于其祖父节点的level >每一个level大于1的节点有两个子节点
#### 情况1.1 右儿子下降 
这种情况是合法的，不需要调整 #### 情况1.2 左儿子下降 
我们观察到这里是一种较为复杂的情况，可以这样处理，让节点a和c同时黑下降，得到了 
然后我们考虑到c节点的左右儿子,注意到c和a以前黑同高，所以c的右儿子cr，一定比c矮，当c下降以后，cl、c、cr同高 
根据定义，这里最多还能拖出两个同黑高的，cl的右儿子clr，cr的右儿子crr 
这时候我们对c执行skew，然后clr成了c的左儿子，我们再次对c执行skew，最终a-cl-clr-c-cr-crr同黑高， 
接下来的一步是让我最吃惊的，非常漂亮，我们先对a进行split，然后对根的右儿子再次split，就结束了。对a进行split后我们得到,注意到这里根的高度提高了 
对根对右儿子split,就结束了 
### 情况2 右儿子与自己不同黑高 
让a节点高度降低 
让a进行skew,最后因为b的右儿子高度，分两种情况 
对于b的右儿子太高的时候，对a进行skew 
然后对b进行split即可 #### 情况2.2 左儿子下降 
让a下降 
这里可能发生c的右儿子与c同高，split（a）即可