00001
00008 #ifndef DKUTIL_C_RED_BLACK_TREE_H
00009 #define DKUTIL_C_RED_BLACK_TREE_H
00010
00011
00012 typedef enum { edkcBLACK=0, edkcRED } edkRedBlackColor;
00013
00014 #if 0
00015 #include "dkcOSIndependent.h"
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027 typedef int T;
00028 #define compLT(a,b) (a < b)
00029 #define compEQ(a,b) (a == b)
00030
00031
00032 typedef enum { edkcBLACK = 0, edkcRED } edkRedBlackTreeColor;
00033
00034 typedef struct dkc_RedBlackNode{
00035 struct dkc_RedBlackNode *left;
00036 struct dkc_RedBlackNode *right;
00037 struct dkc_RedBlackNode *parent;
00038 uint8 color;
00039 void *data;
00040 size_t data_size;
00041 }DKC_RED_BLACK_NODE,DKC_RB_TREE_NODE;
00042
00043 typedef struct dkc_RedBlackRoot{
00044 DKC_RED_BLACK_NODE sentinel;
00045 DKC_RED_BACCK_NODE *root;
00046 }DKC_RED_BLACK_ROOT,DKC_RB_TREE_ROOT;
00047
00048 DKC_EXTERN DKC_RB_TREE_ROOT * WINAPI
00049 dkcAlloc2TreeRoot(size_t key_size,size_t pool_num,DKC_COMPARE_TYPE compare,size_t max_num);
00050
00051 DKC_EXTERN int WINAPI dkcFree2TreeRoot(DKC_2TREE_ROOT **ptr);
00052
00053 #if 0
00054 #define DEFINE_RED_BLACK_NODE(node_name,data_type) \
00055 typedef struct node_name##__ {
00056 struct node_name##__ *left; \
00057 struct node_name##__ *right; \
00058 struct node_name##__ *parent; \
00059 nodeColor color; \
00060 T data; \
00061 } node_name;
00062 #endif
00063 #define NIL &sentinel
00064 Node sentinel = { NIL, NIL, 0, BLACK, 0};
00065
00066 Node *root = NIL;
00067
00068 void rotateLeft(Node *x) {
00069
00070
00071
00072
00073
00074 Node *y = x->right;
00075
00076
00077 x->right = y->left;
00078 if (y->left != NIL) y->left->parent = x;
00079
00080
00081 if (y != NIL) y->parent = x->parent;
00082 if (x->parent) {
00083 if (x == x->parent->left)
00084 x->parent->left = y;
00085 else
00086 x->parent->right = y;
00087 } else {
00088 root = y;
00089 }
00090
00091
00092 y->left = x;
00093 if (x != NIL) x->parent = y;
00094 }
00095
00096 void rotateRight(Node *x) {
00097
00098
00099
00100
00101
00102 Node *y = x->left;
00103
00104
00105 x->left = y->right;
00106 if (y->right != NIL) y->right->parent = x;
00107
00108
00109 if (y != NIL) y->parent = x->parent;
00110 if (x->parent) {
00111 if (x == x->parent->right)
00112 x->parent->right = y;
00113 else
00114 x->parent->left = y;
00115 } else {
00116 root = y;
00117 }
00118
00119
00120 y->right = x;
00121 if (x != NIL) x->parent = y;
00122 }
00123
00124 void insertFixup(Node *x) {
00125
00126
00127
00128
00129
00130
00131
00132 while (x != root && x->parent->color == RED) {
00133
00134 if (x->parent == x->parent->parent->left) {
00135 Node *y = x->parent->parent->right;
00136 if (y->color == RED) {
00137
00138
00139 x->parent->color = BLACK;
00140 y->color = BLACK;
00141 x->parent->parent->color = RED;
00142 x = x->parent->parent;
00143 } else {
00144
00145
00146 if (x == x->parent->right) {
00147
00148 x = x->parent;
00149 rotateLeft(x);
00150 }
00151
00152
00153 x->parent->color = BLACK;
00154 x->parent->parent->color = RED;
00155 rotateRight(x->parent->parent);
00156 }
00157 } else {
00158
00159
00160 Node *y = x->parent->parent->left;
00161 if (y->color == RED) {
00162
00163
00164 x->parent->color = BLACK;
00165 y->color = BLACK;
00166 x->parent->parent->color = RED;
00167 x = x->parent->parent;
00168 } else {
00169
00170
00171 if (x == x->parent->left) {
00172 x = x->parent;
00173 rotateRight(x);
00174 }
00175 x->parent->color = BLACK;
00176 x->parent->parent->color = RED;
00177 rotateLeft(x->parent->parent);
00178 }
00179 }
00180 }
00181 root->color = BLACK;
00182 }
00183
00184 Node *insertNode(T data) {
00185 Node *current, *parent, *x;
00186
00187
00188
00189
00190
00191
00192 current = root;
00193 parent = 0;
00194 while (current != NIL) {
00195 if (compEQ(data, current->data)) return (current);
00196 parent = current;
00197 current = compLT(data, current->data) ?
00198 current->left : current->right;
00199 }
00200
00201
00202 if ((x = malloc (sizeof(*x))) == 0) {
00203 printf ("insufficient memory (insertNode)\n");
00204 exit(1);
00205 }
00206 x->data = data;
00207 x->parent = parent;
00208 x->left = NIL;
00209 x->right = NIL;
00210 x->color = RED;
00211
00212
00213 if(parent) {
00214 if(compLT(data, parent->data))
00215 parent->left = x;
00216 else
00217 parent->right = x;
00218 } else {
00219 root = x;
00220 }
00221
00222 insertFixup(x);
00223 return(x);
00224 }
00225
00226 void deleteFixup(Node *x) {
00227
00228
00229
00230
00231
00232
00233 while (x != root && x->color == BLACK) {
00234 if (x == x->parent->left) {
00235 Node *w = x->parent->right;
00236 if (w->color == RED) {
00237 w->color = BLACK;
00238 x->parent->color = RED;
00239 rotateLeft (x->parent);
00240 w = x->parent->right;
00241 }
00242 if (w->left->color == BLACK && w->right->color == BLACK) {
00243 w->color = RED;
00244 x = x->parent;
00245 } else {
00246 if (w->right->color == BLACK) {
00247 w->left->color = BLACK;
00248 w->color = RED;
00249 rotateRight (w);
00250 w = x->parent->right;
00251 }
00252 w->color = x->parent->color;
00253 x->parent->color = BLACK;
00254 w->right->color = BLACK;
00255 rotateLeft (x->parent);
00256 x = root;
00257 }
00258 } else {
00259 Node *w = x->parent->left;
00260 if (w->color == RED) {
00261 w->color = BLACK;
00262 x->parent->color = RED;
00263 rotateRight (x->parent);
00264 w = x->parent->left;
00265 }
00266 if (w->right->color == BLACK && w->left->color == BLACK) {
00267 w->color = RED;
00268 x = x->parent;
00269 } else {
00270 if (w->left->color == BLACK) {
00271 w->right->color = BLACK;
00272 w->color = RED;
00273 rotateLeft (w);
00274 w = x->parent->left;
00275 }
00276 w->color = x->parent->color;
00277 x->parent->color = BLACK;
00278 w->left->color = BLACK;
00279 rotateRight (x->parent);
00280 x = root;
00281 }
00282 }
00283 }
00284 x->color = BLACK;
00285 }
00286
00287 void deleteNode(Node *z) {
00288 Node *x, *y;
00289
00290
00291
00292
00293
00294 if (!z || z == NIL) return;
00295
00296
00297 if (z->left == NIL || z->right == NIL) {
00298
00299 y = z;
00300 } else {
00301
00302 y = z->right;
00303 while (y->left != NIL) y = y->left;
00304 }
00305
00306
00307 if (y->left != NIL)
00308 x = y->left;
00309 else
00310 x = y->right;
00311
00312
00313 x->parent = y->parent;
00314 if (y->parent)
00315 if (y == y->parent->left)
00316 y->parent->left = x;
00317 else
00318 y->parent->right = x;
00319 else
00320 root = x;
00321
00322 if (y != z) z->data = y->data;
00323
00324
00325 if (y->color == BLACK)
00326 deleteFixup (x);
00327
00328 free (y);
00329 }
00330
00331 Node *findNode(T data) {
00332
00333
00334
00335
00336
00337 Node *current = root;
00338 while(current != NIL)
00339 if(compEQ(data, current->data))
00340 return (current);
00341 else
00342 current = compLT (data, current->data) ?
00343 current->left : current->right;
00344 return(0);
00345 }
00346
00347 #endif //eo 0
00348
00349 #endif //end of include once