首页 > 代码库 > [数据结构]替罪羊树简介
[数据结构]替罪羊树简介
<style></style>
替罪羊树是不通过旋转而是重构的一种平衡树。当某一棵子树的节点总数超过其父节点的一定时，就进行重构操作。
目录
- 节点定义
- 重构操作
- 插入操作
- 删除操作
- 其他各种操作
- 完整代码&总结
[节点定义]
为了判断是否需要重构，所以需要加入cover（实际节点个数）域。这次直接加入可重操作，所以还需要增加一个size域。为了体现C++面向对象的思想（分明就是Java用多了），所以判断一个子树是否需用重构写成成员函数bad()。（真开心，因为是重构，不需要那么多的father，终于可以轻松地删掉父节点指针）
1 template<typename T> 2 class ScapegoatTreeNode{ 3 private: 4 static const float factora = 0.69; //平衡因子 5 public: 6 T data; 7 int size, cover; //数的个数， 实际节点个数 8 int count; 9 ScapegoatTreeNode* next[2];10 11 ScapegoatTreeNode():size(1), cover(1), count(1){12 memset(next, 0, sizeof(next));13 }14 15 ScapegoatTreeNode(T data):data(data), size(1), cover(1), count(1){16 memset(next, 0, sizeof(next));17 }18 19 void maintain(){ //维护大小 20 cover = 1, size = count;21 for(int i = 0; i < 2; i++)22 if(next[i] != NULL)23 cover += next[i]->cover, size += next[i]->size; 24 }25 26 int cmp(T data){27 if(this->data =http://www.mamicode.com/= data) return -1;28 return (data < this->data) ? (0) : (1);29 }30 31 boolean bad(){32 for(int i = 0; i < 2; i++)33 // if(next[i] != NULL && next[i]->cover > this->cover * factora)34 if(next[i] != NULL && next[i]->cover > (this->cover + 3) * factora)35 return true;36 return false; 37 }38 39 inline void addCount(int val){40 if(count == 0 && val > 0) cover += 1;41 size += val;42 count += val;43 if(size == 0) cover -= 1;44 }45 };
[重构操作]
首先将要重构的子树拍平（遍历一次得到一个数组），然后利用这个数组进行重构。每次的节点为这个区间的中点，然后递归调用去把[l, mid - 1]重构左子树，[mid + 1, r]重构有子树。记得在每层函数返回之前进行子树大小的维护。
可能这段文字不好帮助理解，那就把上面那棵树重构了（虽然它很平衡，但是长得太丑了）。首先中序遍历得到一个有序的数组（由于我比较懒，所以用的vector，建议保存节点的地址或下标，不要只保存数据）
找到mid，然后递归生成它的左子树和右子树:
、
为了体现当l > r时，直接return NULL，特此注明的键值为7的左子树。
1 //查找操作，因为重构后，有一些节点会消失，需要重新维护一下cover 2 static ScapegoatTreeNode<T>* find(ScapegoatTreeNode<T>*& node, T data){ 3 if(node == NULL) return NULL; 4 int d = node->cmp(data); 5 if(d == -1) return node; 6 ScapegoatTreeNode<T>* s = find(node->next[d], data); 7 node->maintain(); 8 return s; 9 }10 11 //中序遍历得到一个数组12 void getLis(ScapegoatTreeNode<T>*& node){13 if(node == NULL) return;14 getLis(node->next[0]);15 if(node->count > 0) lis.push_back(node);16 getLis(node->next[1]);17 if(node->count <= 0) delete node;18 }19 20 //重构的主要过程21 ScapegoatTreeNode<T>* rebuild(int from, int end){22 if(from > end) return NULL;23 if(from == end){24 ScapegoatTreeNode<T>* node = lis[from];25 node->next[0] = node->next[1] = NULL;26 node->size = node->count;27 node->cover = 1;28 return node; 29 }30 int mid = (from + end) >> 1;31 ScapegoatTreeNode<T>* node = lis[mid];32 node->next[0] = rebuild(from, mid - 1);33 node->next[1] = rebuild(mid + 1, end);34 node->maintain();35 return node;36 }37 38 //调用39 void rebuild(ScapegoatTreeNode<T>*& node, ScapegoatTreeNode<T>*& father){40 lis.clear();41 getLis(node);42 ScapegoatTreeNode<T>* ret = rebuild(0, (unsigned)lis.size() - 1);43 if(father == NULL) root = ret;44 else{45 father->next[father->cmp(ret->data)] = ret;46 find(root, ret->data);47 }48 }
[插入操作]
插入操作还是按照BST的性质进行插入。只不过中途要找到最后一个极其不平衡的子树的根节点(试想一下，一遇到有问题的就重构，那么替罪羊树的复杂度会变为多少)。这个节点又叫『替罪羊节点』。其它就没有可以多说的内容了。
1 static void insert(ScapegoatTreeNode<T>*& node, T data, ScapegoatTreeNode<T>*& last, ScapegoatTreeNode<T>*& father){ 2 if(node == NULL){ 3 node = new ScapegoatTreeNode<T>(data); 4 return; 5 } 6 int d = node->cmp(data); 7 if(d == -1){ 8 node->addCount(1); 9 return;10 }11 insert(node->next[d], data, last, father);12 node->maintain();13 if(father == NULL && last != NULL) father = node;14 if(node->bad()) last = node, father = NULL;15 }16 17 void insert(T data){18 ScapegoatTreeNode<T>* node = NULL, *father = NULL;19 insert(root, data, node, father);20 if(node != NULL) rebuild(node, father);21 }
[删除操作]
试想一下用Treap的删除方式，然而并不存在旋转操作。如果暴力重构，时间复杂度又会太高。
如果节点的count为1，那么惰性删除（相当于打lazy标记，也就是说，当重构的时候，这个节点才被真正地删除）。否则就在count上减1就好了。
如果是项目开发之类的，最好加入一些容错处理，而不是像，只是为了去ac一道模板题。
1 static boolean remove(ScapegoatTreeNode<T>*& node, T data, ScapegoatTreeNode<T>*& last, ScapegoatTreeNode<T>*& father){ 2 if(node == NULL) return false; 3 int d = node->cmp(data); 4 if(d == -1){ 5 node->addCount(-1); 6 return true; 7 } 8 boolean res = remove(node->next[d], data, last, father); 9 if(res) node->maintain();10 if(father == NULL && last != NULL) father = node;11 if(node->bad()) last = node, father = NULL;12 return res;13 }14 15 boolean remove(T data){16 ScapegoatTreeNode<T>* node = NULL, *father = NULL;17 boolean res = remove(root, data, node, father);18 if(node != NULL) rebuild(node, father);19 return res;20 }
[其它各种操作]
·各种bound
思路可以参照Splay中的思路，唯一注意一点，如果当前的节点不存在，且按照cmp指示的方向并不存在，那么就得向另外一个方向来找（之前被坑了好多好多次，除非本来就要比这个数据大，然而在右子树中没找到，就这个意思，理解了就好）。
下面以lower_bound为例:
1 static ScapegoatTreeNode<T>* upper_bound(ScapegoatTreeNode<T>*& node, T val){2 if(node == NULL) return node;3 int to = node->cmp(val);4 if(val == node->data) to = 1;5 ScapegoatTreeNode<T>* ret = upper_bound(node->next[to], val);6 if(to == 0 && ret == NULL) ret = upper_bound(node->next[1], val);7 return ((ret == NULL || node->data < ret->data) && node->data > val && node->count > 0) ? (node) : (ret);8 }
·名次操作（没有变动，参照Splay内的名次操作）
[完整代码和总结]
替罪羊树的思路可以算是我见过的平衡树中最简单的，然而实现起来处处被坑，处处RE。另外可以通过多次实践来调整平衡因子和bad()函数，可以不通过改变主体过程就可以做到提高效率。下面是bzoj 3224的AC完整代码，另外加有不同参数的耗时。
1 /** 2 * bzoj 3 * Problem#3224 4 * Accepted 5 * Time:500ms / 436ms 6 * Memory:2628k / 2628k 7 */ 8 /** A table for factora 9 * factora 0.75 0.7 0.69 0.68 0.67 0.65 10 * Time 436ms 388ms 384ms 398ms 388ms 444ms 11 */ 12 #include<iostream> 13 #include<fstream> 14 #include<sstream> 15 #include<cstdio> 16 #include<cstdlib> 17 #include<cstring> 18 #include<ctime> 19 #include<cctype> 20 #include<cmath> 21 #include<algorithm> 22 #include<stack> 23 #include<queue> 24 #include<set> 25 #include<map> 26 #include<vector> 27 using namespace std; 28 typedef bool boolean; 29 #define smin(a, b) (a) = min((a), (b)) 30 #define smax(as, b) (a) = max((a), (b)) 31 template<typename T> 32 inline boolean readInteger(T& u){ 33 char x; 34 int aFlag = 1; 35 while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1); 36 if(x == -1) return false; 37 if(x == ‘-‘){ 38 x = getchar(); 39 aFlag = -1; 40 } 41 for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 3) + (u << 1) + x - ‘0‘); 42 ungetc(x, stdin); 43 u *= aFlag; 44 return true; 45 } 46 47 template<typename T> 48 class ScapegoatTreeNode{ 49 private: 50 static const float factora = 0.69; //平衡因子 51 public: 52 T data; 53 int size, cover; //数的个数， 实际节点个数 54 int count; 55 ScapegoatTreeNode* next[2]; 56 57 ScapegoatTreeNode():size(1), cover(1), count(1){ 58 memset(next, 0, sizeof(next)); 59 } 60 61 ScapegoatTreeNode(T data):data(data), size(1), cover(1), count(1){ 62 memset(next, 0, sizeof(next)); 63 } 64 65 void maintain(){ //维护大小 66 cover = 1, size = count; 67 for(int i = 0; i < 2; i++) 68 if(next[i] != NULL) 69 cover += next[i]->cover, size += next[i]->size; 70 } 71 72 int cmp(T data){ 73 if(this->data =http://www.mamicode.com/= data) return -1; 74 return (data < this->data) ? (0) : (1); 75 } 76 77 boolean bad(){ 78 for(int i = 0; i < 2; i++) 79 // if(next[i] != NULL && next[i]->cover > this->cover * factora) 80 if(next[i] != NULL && next[i]->cover > (this->cover + 3) * factora) //+1 384ms +3 376ms +5 448ms 81 return true; 82 return false; 83 } 84 85 inline void addCount(int val){ 86 if(count == 0 && val > 0) cover += 1; 87 size += val; 88 count += val; 89 if(size == 0) cover -= 1; 90 } 91 }; 92 93 template<typename T> 94 class ScapegoatTree{ 95 protected: 96 static void insert(ScapegoatTreeNode<T>*& node, T data, ScapegoatTreeNode<T>*& last, ScapegoatTreeNode<T>*& father){ 97 if(node == NULL){ 98 node = new ScapegoatTreeNode<T>(data); 99 return;100 }101 int d = node->cmp(data);102 if(d == -1){103 node->addCount(1);104 return;105 }106 insert(node->next[d], data, last, father);107 node->maintain();108 if(father == NULL && last != NULL) father = node;109 if(node->bad()) last = node, father = NULL;110 }111 112 static boolean remove(ScapegoatTreeNode<T>*& node, T data, ScapegoatTreeNode<T>*& last, ScapegoatTreeNode<T>*& father){113 if(node == NULL) return false;114 int d = node->cmp(data);115 if(d == -1){116 node->addCount(-1);117 return true;118 }119 boolean res = remove(node->next[d], data, last, father);120 if(res) node->maintain();121 if(father == NULL && last != NULL) father = node;122 if(node->bad()) last = node, father = NULL;123 return res;124 }125 126 static ScapegoatTreeNode<T>* less_bound(ScapegoatTreeNode<T>*& node, T val){127 if(node == NULL) return node;128 int to = node->cmp(val);129 if(val == node->data) to = 0;130 ScapegoatTreeNode<T>* ret = less_bound(node->next[to], val);131 if(to == 1 && ret == NULL) ret = less_bound(node->next[0], val);132 return ((ret == NULL || node->data > ret->data) && node->data < val && node->count > 0) ? (node) : (ret);133 }134 135 static ScapegoatTreeNode<T>* upper_bound(ScapegoatTreeNode<T>*& node, T val){136 if(node == NULL) return node;137 int to = node->cmp(val);138 if(val == node->data) to = 1;139 ScapegoatTreeNode<T>* ret = upper_bound(node->next[to], val);140 if(to == 0 && ret == NULL) ret = upper_bound(node->next[1], val);141 return ((ret == NULL || node->data < ret->data) && node->data > val && node->count > 0) ? (node) : (ret);142 }143 144 static ScapegoatTreeNode<T>* findKth(ScapegoatTreeNode<T>*& node, int k){145 int ls = (node->next[0] == NULL) ? (0) : (node->next[0]->size);146 int count = node->count;147 if(k >= ls + 1 && k <= ls + count) return node;148 if(k <= ls) return findKth(node->next[0], k);149 return findKth(node->next[1], k - ls - count);150 }151 152 static ScapegoatTreeNode<T>* find(ScapegoatTreeNode<T>*& node, T data){153 if(node == NULL) return NULL;154 int d = node->cmp(data);155 if(d == -1) return node;156 ScapegoatTreeNode<T>* s = find(node->next[d], data);157 node->maintain();158 return s;159 }160 public:161 ScapegoatTreeNode<T>* root;162 vector<ScapegoatTreeNode<T>*> lis;163 164 ScapegoatTree():root(NULL){ }165 166 void getLis(ScapegoatTreeNode<T>*& node){167 if(node == NULL) return;168 getLis(node->next[0]);169 if(node->count > 0) lis.push_back(node);170 getLis(node->next[1]);171 if(node->count <= 0) delete node;172 }173 174 ScapegoatTreeNode<T>* rebuild(int from, int end){175 if(from > end) return NULL;176 if(from == end){177 ScapegoatTreeNode<T>* node = lis[from];178 node->next[0] = node->next[1] = NULL;179 node->size = node->count;180 node->cover = 1;181 return node; 182 }183 int mid = (from + end) >> 1;184 ScapegoatTreeNode<T>* node = lis[mid];185 node->next[0] = rebuild(from, mid - 1);186 node->next[1] = rebuild(mid + 1, end);187 node->maintain();188 return node;189 }190 191 void rebuild(ScapegoatTreeNode<T>*& node, ScapegoatTreeNode<T>*& father){192 lis.clear();193 getLis(node);194 ScapegoatTreeNode<T>* ret = rebuild(0, (unsigned)lis.size() - 1);195 if(father == NULL) root = ret;196 else{197 father->next[father->cmp(ret->data)] = ret;198 find(root, ret->data);199 }200 }201 202 void insert(T data){203 ScapegoatTreeNode<T>* node = NULL, *father = NULL;204 insert(root, data, node, father);205 if(node != NULL) rebuild(node, father);206 }207 208 boolean remove(T data){209 ScapegoatTreeNode<T>* node = NULL, *father = NULL;210 boolean res = remove(root, data, node, father);211 if(node != NULL) rebuild(node, father);212 return res;213 }214 215 void out(ScapegoatTreeNode<T>*& node){ //调试使用函数，打印树 216 if(node == NULL) return;217 cout << node->data << "(" << node->size << "," << node->cover << "," << node->count << "){";218 out(node->next[0]);219 cout << ",";220 out(node->next[1]);221 cout << "}";222 }223 224 ScapegoatTreeNode<T>* less_bound(T data){225 return less_bound(root, data);226 }227 228 ScapegoatTreeNode<T>* upper_bound(T data){229 return upper_bound(root, data);230 }231 232 ScapegoatTreeNode<T>* findKth(int k){233 return findKth(root, k);234 }235 236 inline int rank(T data){237 ScapegoatTreeNode<T>* p = root;238 int r = 0;239 while(p != NULL){240 int ls = (p->next[0] != NULL) ? (p->next[0]->size) : (0);241 if(p->data =http://www.mamicode.com/= data) return r + ls + 1;242 int d = p->cmp(data);243 if(d == 1) r += ls + p->count;244 p = p->next[d];245 }246 return r + 1;247 }248 };249 250 int n;251 ScapegoatTree<int> s;252 253 void printTree(){254 s.out(s.root);255 putchar(‘\n‘);256 }257 258 inline void solve(){259 int opt, x; 260 readInteger(n);261 while(n--){262 readInteger(opt);263 readInteger(x);264 if(opt == 1) s.insert(x);265 else if(opt == 2) s.remove(x);266 else if(opt == 3) printf("%d\n", s.rank(x));267 else if(opt == 4) printf("%d\n", s.findKth(x)->data);268 else if(opt == 5) printf("%d\n", s.less_bound(x)->data);269 else printf("%d\n", s.upper_bound(x)->data);270 }271 }272 273 int main(){274 solve();275 return 0;276 }
[数据结构]替罪羊树简介
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。