AATree

AA Tree

AA树真的很棒,虽然他没有普通红黑树那么厉害,但是AA树挺容易实现的,AA树是一棵右倾红黑树23树,注意! 这里是23树,不是234树。 ## AA树的由来 Arne Andersson教授在论文Balanced search trees made simple中提到,红黑树有7种特殊情况(图片源于wiki) 为了改进,他提出了使用23树并强行要求3节点(2key-3son-node)向右倾斜,于是,我们只剩下两种情况(图片源于wiki) 为了更加容易编码,他提出不再使用红黑来标识节点,而是选择高度,这里的高度指的是黑高度,即黑色节点的高度,学习过左偏树(左翼堆)或斜堆的读者应该对这里不太陌生,这里的高度其实和左偏树或斜堆中的右距离是同一个东西。 ## AA树的特性 >所有叶节点的level都是1 >每个左孩子的level恰好为其父亲的level减一 >每个右孩子的level等于其父亲的level或为其父亲的level减一 >每个右孙子的level严格小于其祖父节点的level >每一个level大于1的节点有两个子节点

AA树的skew

skew 是一个辅助函数,他的本质是zig,即如果发现一个节点的左儿子与自己黑高相同,则将左儿子选择至根。这将保证右倾。 ## AA树中的split split同样是一个辅助函数,他的本质是zag,即如果发现一个节点的右孙子与自己黑高相同,则将右儿子选择至根,并将黑高+1,这将保证不会出现4节点(3key-4son-node) ## AA树中的insert 递归向下,找到插入位置,然后插入,最后调整,调整的时候,树会变高,对每一层递归而言,左儿子变高我们就先让其skew,这可能导致出现4节点,我们再split,对于右儿子变高的情况,这时候可能右儿子本身是一个3节点,当他变高,导致根成为了4节点,我们调用skew即可,全部统一一下,就是先skew后split ## AA树中的erase 很多时候删除都是一件困难的事情,但是我们可以通过寻找前驱后继,可以保证删除的节点一定是叶子,对于删除叶子,可能树高下降,同样的,先删除后对每一层进行调整。我们前面说过,AA树只有两种结构。我们来分析一下树高下降产生的影响。

情况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 右儿子与自己不同黑高 #### 情况2.1 右儿子下降 让a节点高度降低 让a进行skew,最后因为b的右儿子高度,分两种情况 对于b的右儿子太高的时候,对a进行skew 然后对b进行split即可 #### 情况2.2 左儿子下降 让a下降 这里可能发生c的右儿子与c同高,split(a)即可

AA树erase总结

至此我们的删除已经讨论完了,实际细分只有4种情况,这要比普通红黑树简单多了,

AA树缺点

多次旋转导致性能不及红黑树,旋转次数较多

AA树代码

AA树代码
treeview raw
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 {
/*
* AA树是红黑树的一个变种,他的本质是右倾红黑树
*
* */

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;
}
// 这个函数仅仅处理左儿子跟自己同级的情况,rt只允许出现这一个错误
// skew以后可能会出现右孙子和自己同级情况
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); // 所有叶子节点的高度为1
if (rt->l != nullptr)
assert(rt->l->h == rt->h - 1); // 所有左孩子的高度为父亲的减1
if (rt->r != nullptr) {
assert(rt->r->h == rt->h - 1 ||
rt->r->h == rt->h); // 所有右孩子的高度为父亲或减1
if (rt->r->r != nullptr) assert(rt->r->r->h < rt->h); // 孙子严格小自己
}
if (rt->h > 1)
assert(rt->l != nullptr && rt->r != nullptr); // 大于1的节点有两个儿子
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); }
};
} // namespace data_structure