首页 > 代码库 > 红黑树
红黑树
参考资料：红黑树
我的实现
1 #define BLACK 1 2 #define RED 0 3 4 struct node 5 { 6 int value; 7 node *left, *right, *parent; 8 bool color; 9 10 void set(int v, node *l, node *r, node *p, bool c) 11 { 12 value =http://www.mamicode.com/ v; 13 left = l; 14 right = r; 15 parent = p; 16 color = c; 17 } 18 19 node* grandparent() 20 { 21 return parent->parent; 22 } 23 24 node* uncle() 25 { 26 node *gp = grandparent(); 27 if (parent == gp->left) 28 return gp->right; 29 else 30 return gp->left; 31 } 32 } 33 34 struct rbt 35 { 36 node *root, *nil; 37 38 void leftRotate(node *x) 39 { 40 node *y = x->right; //find x‘s right son 41 42 x->right = y->left; //link y‘s left son to x 43 if ( y->left != nil ) 44 y->left->parent = x; 45 46 y->parent = x->parent; //link y to x‘s parent 47 if ( x->parent == nil ) 48 root = y; 49 else { 50 if (x == x->parent->left) { 51 x->parent->left = y; 52 } 53 else 54 x->parent->right = y; 55 } 56 57 y->left = x; //link x and y 58 x->parent = y; 59 } 60 61 void rightRotate( node *x ) 62 { 63 node *y = x->left; 64 65 x->left = y->right; //link y‘s right son to x 66 if (y->right != nil) 67 y->right->parent = x; 68 69 y->parent = x->parent; //link y to x‘s parent 70 if (x->parent == nil ) 71 root = y; 72 else { 73 if ( x == x->parent->left) 74 x->parent->left = y; 75 else 76 x->parent->right = y; 77 } 78 79 y->right = x; //link x and y 80 x->parent = y; 81 } 82 83 void insertFixup(node *n) 84 { 85 while (n->parent->color == RED) { 86 if (n->uncle() != nil && n->uncle()->color == RED) {//case 1 87 n->grandparent()->color = RED; 88 n->parent->color = BLACK; 89 n->uncle()->color = BLACK; 90 n = n->grandparent(); //iterate the operation 91 } 92 else if (n->parent == n->grandparent()->left) { 93 if (n == n->parent->right) { //case 2 tranform to case 3 94 leftRotate(n->parent); 95 n = n->left; //now case 2 have been transformed to case 3 96 } 97 n->parent->color = BLACK; //case 3 98 n->grandparent()->color = RED; 99 rightRotate(n->grandparent());100 }101 else { 102 if (n == n->parent->left) { //case 2103 rightRotate(n->parent);104 n = n->right;105 }106 n->parent->color = BLACK; //case 3107 n->grandparent()->color = RED;108 leftRotate(n->grandparent());109 }110 }111 root->color = BLACK;112 }113 114 void insert(int value) 115 {116 if (root == nil) { //117 root->value =http://www.mamicode.com/ value;118 root->color = BLACK;119 root->left = root->right = nil;120 }121 else {122 node *newNode;123 (*newNode).set(value, nil, nil, nil, RED);124 125 node *x = root;126 node *p;127 while (x != nil) { //search the position to insert128 p = x;129 if (value < x->value)130 x = x->left;131 else 132 x = x->right;133 }134 135 newNode->parent = p; //insert the new node136 if (p->value > value) 137 p->left = newNode;138 else 139 p->right = newNode;140 insertFixup(newNode); //rebuild the structure141 }142 }143 144 node *successor(node *n) //search the successor node145 {146 if (n->right != nil) {147 n = n->right;148 while (n->left != nil) {149 n = n->left;150 }151 }152 else {153 while (n == n->parent->right) {154 n = n->parent;155 }156 n = n->parent;157 }158 return n;159 }160 161 162 void delFixup(node *n)163 {164 if (n->color == RED) { 165 n->color = BLACK;166 return;167 }168 169 while (n->color == BLACK) {170 if (n == root) return; 171 node *s;172 if (n == n->parent->left) {173 s = n->parent->right; // brother node174 175 if (s->color == RED) { // case 1176 n->parent->color = RED;177 s->color = BLACK;178 leftRotate(n->parent); // transformed to case 2,3,4,5179 }180 181 if (s->left->color == BLACK &&s->right->color == BLACK) { //case 2,3182 s->color = RED;183 if (n->parent->color == RED) { //case 2184 n->parent->color = BLACK;185 return;186 }187 n = n->parent; //case 3188 }189 else { //case 4,5190 if (s->left->color == RED) { //case 4191 s->color = RED;192 s->left->color = BLACK;193 rightRotate(s);194 s = n->parent->right; //transformed to case 5195 }196 197 s->right->color = BLACK; //case 5198 s->color = n->parent->color;199 n->parent->color = BLACK;200 leftRotate(n->parent);201 return;202 }203 }204 205 else { // similar as the upper situation 206 s = n->parent->left;207 if (s->color == RED) {208 n->parent->color = RED;209 s->color = BLACK;210 rightRotate(n->parent);211 }212 213 if (s->left->color == BLACK && s->right->color == BLACK) {214 s->color = RED;215 if (n->parent->color == RED) {216 n->parent->color = BLACK;217 return;218 }219 n = n->parent;220 }221 else {222 if (s->right->color == RED) {223 s->color = RED;224 s->right->color = BLACK;225 leftRotate(s);226 s = n->parent->right;227 }228 229 s->left->color = BLACK;230 s->color = n->parent->color;231 n->parent->color = BLACK;232 rightRotate(n->parent);233 return;234 }235 }236 } 237 }238 239 void del(node *n) //delete a node240 {241 node *or = n;242 node *nn;243 if (n->left != nil && n->right != nil) 244 n = successor(n); //if have two child, then delete the succesor245 246 if (n->left != nil) 247 nn = n->left;248 else 249 nn = n->right;250 251 nn->parent = n->parent;252 if (n->parent == nil)253 root = nn;254 else {255 if (n == n->parent->left)256 n->parent->left = nn;257 else 258 n->parent->right = nn;259 }260 if (n != or) { 261 or->value = http://www.mamicode.com/n->value; //replaced with the successor262 }263 264 if (n->color != RED) {265 delFixup(nn); //rebuild the structure266 }267 free(n);268 }269 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。