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

# 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