第一道SBT的题，十分简单，1y。
这题用优先级来排序，查找优先级最小/最大的元素，返回其值并删除节点。
构造popHead和popTail两个函数，搜索最小/最大的节点。因为构树的时候没有构造父节点指针，所以对节点修改的函数都必须用引用符号来继承上一结点的属性。
View Code 1 #include2 #include 3 #include 4 #include 5 6 using namespace std; 7 8 struct SBTNode{ 9 SBTNode *left, *right; 10 int key, size, id; 11 SBTNode(int k, int i){ 12 key = k; 13 id = i; 14 size = 1; 15 left = right = NULL; 16 } 17 }; 18 19 struct SBT{ 20 SBTNode *root; 21 22 SBT(){ 23 root = NULL; 24 } 25 26 void rightRotate(SBTNode *&x){ 27 SBTNode *y = x->left; 28 29 x->left = y->right; 30 y->right = x; 31 y->size = x->size; 32 33 int ls = x->left ? x->left->size : 0; 34 int rs = x->right ? x->right->size : 0; 35 36 x->size = ls + rs + 1; 37 x = y; 38 } 39 40 void leftRotate(SBTNode *&x){ 41 SBTNode *y = x->right; 42 43 x->right = y->left; 44 y->left = x; 45 y->size = x->size; 46 47 int ls = x->left ? x->left->size : 0; 48 int rs = x->right ? x->right->size : 0; 49 50 x->size = ls + rs + 1; 51 x = y; 52 } 53 54 void maintain(SBTNode *&T, bool rightDeeper){ 55 if (!T) return ; 56 if (!rightDeeper){ 57 if (T->left == NULL) return ; 58 59 int rs = T->right ? T->right->size : 0; 60 61 if (T->left->left && T->left->left->size > rs){ 62 rightRotate(T); 63 } 64 else if (T->left->right && T->left->right->size > rs){ 65 leftRotate(T->left); 66 rightRotate(T); 67 } 68 else return ; 69 } 70 else { 71 if (T->right == NULL) return ; 72 73 int ls = T->left ? T->left->size : 0; 74 75 if (T->right->right && T->right->right->size > ls){ 76 leftRotate(T); 77 } 78 else if (T->right->left && T->right->left->size > ls){ 79 rightRotate(T->right); 80 leftRotate(T); 81 } 82 else return ; 83 } 84 maintain(T->left, false); 85 maintain(T->right, true); 86 maintain(T, false); 87 maintain(T, true); 88 } 89 90 void ins(SBTNode *&T, SBTNode *x){ 91 if (!T){ 92 T = x; 93 return ; 94 } 95 T->size++; 96 if (x->key < T->key){ 97 ins(T->left, x); 98 } 99 else{100 ins(T->right, x);101 }102 maintain(T, x->key >= T->key);103 }104 105 void del(SBTNode *&T, int key){106 if (!T) return ;107 T->size--;108 if (key < T->key) del(T->left, key);109 else if (key > T->key) del(T->right, key);110 else{111 SBTNode *t;112 113 if (!T->left && !T->right){114 delete T;115 T = NULL;116 }117 else if (!T->right){118 t = T;119 T = T->left;120 delete t;121 }122 else if (!T->left){123 t = T;124 T = T->right;125 delete t;126 }127 else{128 t = T->right;129 while (t->left) t = t->left;130 T->key = t->key;131 T->id = t->id;132 del(T->right, t->key);133 }134 }135 }136 137 /******the following two funtions is modeled after the delete funtion******/138 int popHead(SBTNode *&T){139 SBTNode *p = T;140 141 if (!T) return 0;142 T->size--;143 if (T->left) return popHead(T->left);144 else{145 T = T->right;146 147 int ret = p->id;148 149 delete p;150 return ret;151 }152 }153 154 int popTail(SBTNode *&T){155 SBTNode *p = T;156 157 if (!T) return 0;158 T->size--;159 if (T->right) return popTail(T->right);160 else{161 T = T->left;162 163 int ret = p->id;164 165 delete p;166 return ret;167 }168 }169 170 void print(SBTNode *T){171 if (!T) return ;172 printf("cur %d : id %d key %d left %d right %d size %d\n", T, T->id, T->key, T->left, T->right, T->size);173 print(T->left);174 print(T->right);175 }176 }T;177 178 void work(){179 int op;180 181 T.root = NULL;182 while (~scanf("%d", &op)){183 switch (op){184 case 1:{185 int id, wt;186 187 scanf("%d%d", &id, &wt);188 189 SBTNode *tmp = new SBTNode(wt, id);190 T.ins(T.root, tmp);191 //T.print(T.root);192 }193 break;194 case 2:{195 printf("%d\n", T.popTail(T.root));196 //T.print(T.root);197 }198 break;199 case 3:{200 printf("%d\n", T.popHead(T.root));201 //T.print(T.root);202 }203 break;204 default: return ;205 }206 }207 }208 209 int main(){210 //freopen("in", "w", stdout);211 work();212 213 return 0;214 }
——written by Lyon