メインページ | アルファベット順一覧 | 構成 | ファイル一覧 | 構成メンバ | ファイルメンバ | 関連ページ

dkcRedBlackTree.h

説明を見る。
00001 
00008 #ifndef DKUTIL_C_RED_BLACK_TREE_H
00009 #define DKUTIL_C_RED_BLACK_TREE_H
00010 
00011 /* Red-Black tree description */
00012 typedef enum { edkcBLACK=0, edkcRED } edkRedBlackColor;      
00013 
00014 #if 0
00015 #include "dkcOSIndependent.h"
00016 
00017 
00018 /*
00019 The below red-black tree implementation of was
00020  written by Thomas Niemann
00021  and is available on his algorithm collection webpages.
00022  This code is not subject to copyright restrictions. 
00023  */
00024 /* red-black tree */
00025  
00026  
00027  typedef int T;                  /* type of item to be stored */
00028  #define compLT(a,b) (a < b)
00029  #define compEQ(a,b) (a == b)
00030  
00031  /* Red-Black tree description */
00032  typedef enum { edkcBLACK = 0, edkcRED } edkRedBlackTreeColor;
00033 
00034 typedef struct dkc_RedBlackNode{
00035     struct dkc_RedBlackNode *left;         /* left child */ 
00036     struct dkc_RedBlackNode *right;        /* right child */
00037     struct dkc_RedBlackNode *parent;       /* parent */
00038     uint8 color;            /* node color (BLACK, RED) */
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;         /* left child */ \
00057    struct node_name##__ *right;        /* right child */\
00058    struct node_name##__ *parent;       /* parent */\
00059    nodeColor color;            /* node color (BLACK, RED) */\
00060    T data;                     /* data stored in node */\
00061 } node_name;
00062 #endif
00063  #define NIL &sentinel           /* all leafs are sentinels */
00064  Node sentinel = { NIL, NIL, 0, BLACK, 0};
00065  
00066  Node *root = NIL;               /* root of Red-Black tree */
00067  
00068  void rotateLeft(Node *x) {
00069  
00070     /**************************
00071      *  rotate node x to left *
00072      **************************/
00073  
00074      Node *y = x->right;
00075  
00076      /* establish x->right link */
00077      x->right = y->left;
00078      if (y->left != NIL) y->left->parent = x;
00079  
00080      /* establish y->parent link */
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      /* link x and y */
00092      y->left = x;
00093      if (x != NIL) x->parent = y;
00094  }
00095  
00096  void rotateRight(Node *x) {
00097  
00098     /****************************
00099      *  rotate node x to right  *
00100      ****************************/
00101  
00102      Node *y = x->left;
00103  
00104      /* establish x->left link */
00105      x->left = y->right;
00106      if (y->right != NIL) y->right->parent = x;
00107  
00108      /* establish y->parent link */
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      /* link x and y */
00120      y->right = x;
00121      if (x != NIL) x->parent = y;
00122  }
00123  
00124  void insertFixup(Node *x) {
00125  
00126     /*************************************
00127      *  maintain Red-Black tree balance  *
00128      *  after inserting node x           *
00129      *************************************/
00130  
00131      /* check Red-Black properties */
00132      while (x != root && x->parent->color == RED) {
00133          /* we have a violation */
00134          if (x->parent == x->parent->parent->left) {
00135              Node *y = x->parent->parent->right;
00136              if (y->color == RED) {
00137  
00138                  /* uncle is RED */
00139                  x->parent->color = BLACK;
00140                  y->color = BLACK;
00141                  x->parent->parent->color = RED;
00142                  x = x->parent->parent;
00143              } else {
00144  
00145                  /* uncle is BLACK */
00146                  if (x == x->parent->right) {
00147                      /* make x a left child */
00148                      x = x->parent;
00149                      rotateLeft(x);
00150                  }
00151  
00152                  /* recolor and rotate */
00153                  x->parent->color = BLACK;
00154                  x->parent->parent->color = RED;
00155                  rotateRight(x->parent->parent);
00156              }
00157          } else {
00158  
00159              /* mirror image of above code */
00160              Node *y = x->parent->parent->left;
00161              if (y->color == RED) {
00162  
00163                  /* uncle is RED */
00164                  x->parent->color = BLACK;
00165                  y->color = BLACK;
00166                  x->parent->parent->color = RED;
00167                  x = x->parent->parent;
00168              } else {
00169  
00170                  /* uncle is BLACK */
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      *  allocate node for data and insert in tree  *
00189      ***********************************************/
00190  
00191      /* find where node belongs */
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      /* setup new node */
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      /* insert node in tree */
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      *  maintain Red-Black tree balance  *
00230      *  after deleting node x            *
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      *  delete node z from tree  *
00292      *****************************/
00293  
00294      if (!z || z == NIL) return;
00295  
00296  
00297      if (z->left == NIL || z->right == NIL) {
00298          /* y has a NIL node as a child */
00299          y = z;
00300      } else {
00301          /* find tree successor with a NIL node as a child */
00302          y = z->right;
00303          while (y->left != NIL) y = y->left;
00304      }
00305  
00306      /* x is y's only child */
00307      if (y->left != NIL)
00308          x = y->left;
00309      else
00310          x = y->right;
00311  
00312      /* remove y from the parent chain */
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      *  find node containing data  *
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

dkutil_cに対してSat Sep 10 09:23:56 2005に生成されました。  doxygen 1.4.4