bst红黑色不起作用

Question

这有什么问题？

// rbt.cpp : Defines the entry point for the console application. 
// 

#include "stdafx.h" 

#ifndef rbth 
#define rbth 

typedef enum { 
    RBT_STATUS_OK, 
    RBT_STATUS_MEM_EXHAUSTED, 
    RBT_STATUS_DUPLICATE_KEY, 
    RBT_STATUS_KEY_NOT_FOUND 
} RbtStatus; 

typedef void *RbtIterator; 
typedef void *RbtHandle; 

RbtHandle rbtNew(int(*compare)(void *a, void *b)); 
// create red-black tree 
// parameters: 
//  compare pointer to function that compares keys 
//    return 0 if a == b 
//    return < 0 if a < b 
//    return > 0 if a > b 
// returns: 
//  handle use handle in calls to rbt functions 


void rbtDelete(RbtHandle h); 
// destroy red-black tree 

RbtStatus rbtInsert(RbtHandle h, void *key, void *value); 
// insert key/value pair 

RbtStatus rbtErase(RbtHandle h, RbtIterator i); 
// delete node in tree associated with iterator 
// this function does not free the key/value pointers 

RbtIterator rbtNext(RbtHandle h, RbtIterator i); 
// return ++i 

RbtIterator rbtBegin(RbtHandle h); 
// return pointer to first node 

RbtIterator rbtEnd(RbtHandle h); 
// return pointer to one past last node 

void rbtKeyValue(RbtHandle h, RbtIterator i, void **key, void **value); 
// returns key/value pair associated with iterator 

RbtIterator rbtFind(RbtHandle h, void *key); 
// returns iterator associated with key 

#endif 

// reentrant red-black tree 

#include <stdlib.h> 
#include <rbtr.h> 

typedef enum { BLACK, RED } NodeColor; 

typedef struct NodeTag { 
    struct NodeTag *left;  // left child 
    struct NodeTag *right;  // right child 
    struct NodeTag *parent;  // parent 
    NodeColor color;   // node color (BLACK, RED) 
    void *key;     // key used for searching 
    void *val;    // user data 
} NodeType; 

typedef struct RbtTag { 
    NodeType *root; // root of red-black tree 
    NodeType sentinel; 
    int (*compare)(void *a, void *b); // compare keys 
} RbtType; 

// all leafs are sentinels 
#define SENTINEL &rbt->sentinel 

RbtHandle rbtNew(int(*rbtCompare)(void *a, void *b)) { 
    RbtType *rbt; 

    if ((rbt = (RbtType *)malloc(sizeof(RbtType))) == NULL) { 
     return NULL; 
    } 

    rbt->compare = rbtCompare; 
    rbt->root = SENTINEL; 
    rbt->sentinel.left = SENTINEL; 
    rbt->sentinel.right = SENTINEL; 
    rbt->sentinel.parent = NULL; 
    rbt->sentinel.color = BLACK; 
    rbt->sentinel.key = NULL; 
    rbt->sentinel.val = NULL; 

    return rbt; 
} 

static void deleteTree(RbtHandle h, NodeType *p) { 
    RbtType *rbt = h; 

    // erase nodes depth-first 
    if (p == SENTINEL) return; 
    deleteTree(h, p->left); 
    deleteTree(h, p->right); 
    free(p); 
} 

void rbtDelete(RbtHandle h) { 
    RbtType *rbt = h; 

    deleteTree(h, rbt->root); 
    free(rbt); 
} 

static void rotateLeft(RbtType *rbt, NodeType *x) { 

    // rotate node x to left 

    NodeType *y = x->right; 

    // establish x->right link 
    x->right = y->left; 
    if (y->left != SENTINEL) y->left->parent = x; 

    // establish y->parent link 
    if (y != SENTINEL) y->parent = x->parent; 
    if (x->parent) { 
     if (x == x->parent->left) 
      x->parent->left = y; 
     else 
      x->parent->right = y; 
    } else { 
     rbt->root = y; 
    } 

    // link x and y 
    y->left = x; 
    if (x != SENTINEL) x->parent = y; 
} 

static void rotateRight(RbtType *rbt, NodeType *x) { 

    // rotate node x to right 

    NodeType *y = x->left; 

    // establish x->left link 
    x->left = y->right; 
    if (y->right != SENTINEL) y->right->parent = x; 

    // establish y->parent link 
    if (y != SENTINEL) y->parent = x->parent; 
    if (x->parent) { 
     if (x == x->parent->right) 
      x->parent->right = y; 
     else 
      x->parent->left = y; 
    } else { 
     rbt->root = y; 
    } 

    // link x and y 
    y->right = x; 
    if (x != SENTINEL) x->parent = y; 
} 

static void insertFixup(RbtType *rbt, NodeType *x) { 

    // maintain red-black tree balance after inserting node x 

    // check red-black properties 
    while (x != rbt->root && x->parent->color == RED) { 
     // we have a violation 
     if (x->parent == x->parent->parent->left) { 
      NodeType *y = x->parent->parent->right; 
      if (y->color == RED) { 

       // uncle is RED 
       x->parent->color = BLACK; 
       y->color = BLACK; 
       x->parent->parent->color = RED; 
       x = x->parent->parent; 
      } else { 

       // uncle is BLACK 
       if (x == x->parent->right) { 
        // make x a left child 
        x = x->parent; 
        rotateLeft(rbt, x); 
       } 

       // recolor and rotate 
       x->parent->color = BLACK; 
       x->parent->parent->color = RED; 
       rotateRight(rbt, x->parent->parent); 
      } 
     } else { 

      // mirror image of above code 
      NodeType *y = x->parent->parent->left; 
      if (y->color == RED) { 

       // uncle is RED 
       x->parent->color = BLACK; 
       y->color = BLACK; 
       x->parent->parent->color = RED; 
       x = x->parent->parent; 
      } else { 

       // uncle is BLACK 
       if (x == x->parent->left) { 
        x = x->parent; 
        rotateRight(rbt, x); 
       } 
       x->parent->color = BLACK; 
       x->parent->parent->color = RED; 
       rotateLeft(rbt, x->parent->parent); 
      } 
     } 
    } 
    rbt->root->color = BLACK; 
} 

RbtStatus rbtInsert(RbtHandle h, void *key, void *val) { 
    NodeType *current, *parent, *x; 
    RbtType *rbt = h; 

    // allocate node for data and insert in tree 

    // find future parent 
    current = rbt->root; 
    parent = 0; 
    while (current != SENTINEL) { 
     int rc = rbt->compare(key, current->key); 
     if (rc == 0) 
      return RBT_STATUS_DUPLICATE_KEY; 
     parent = current; 
     current = (rc < 0) ? current->left : current->right; 
    } 

    // setup new node 
    if ((x = malloc (sizeof(*x))) == 0) 
     return RBT_STATUS_MEM_EXHAUSTED; 
    x->parent = parent; 
    x->left = SENTINEL; 
    x->right = SENTINEL; 
    x->color = RED; 
    x->key = key; 
    x->val = val; 

    // insert node in tree 
    if(parent) { 
     if(rbt->compare(key, parent->key) < 0) 
      parent->left = x; 
     else 
      parent->right = x; 
    } else { 
     rbt->root = x; 
    } 

    insertFixup(rbt, x); 

    return RBT_STATUS_OK; 
} 

void deleteFixup(RbtType *rbt, NodeType *x) { 

    // maintain red-black tree balance after deleting node x 

    while (x != rbt->root && x->color == BLACK) { 
     if (x == x->parent->left) { 
      NodeType *w = x->parent->right; 
      if (w->color == RED) { 
       w->color = BLACK; 
       x->parent->color = RED; 
       rotateLeft (rbt, x->parent); 
       w = x->parent->right; 
      } 
      if (w->left->color == BLACK && w->right->color == BLACK) { 
       w->color = RED; 
       x = x->parent; 
      } else { 
       if (w->right->color == BLACK) { 
        w->left->color = BLACK; 
        w->color = RED; 
        rotateRight (rbt, w); 
        w = x->parent->right; 
       } 
       w->color = x->parent->color; 
       x->parent->color = BLACK; 
       w->right->color = BLACK; 
       rotateLeft (rbt, x->parent); 
       x = rbt->root; 
      } 
     } else { 
      NodeType *w = x->parent->left; 
      if (w->color == RED) { 
       w->color = BLACK; 
       x->parent->color = RED; 
       rotateRight (rbt, x->parent); 
       w = x->parent->left; 
      } 
      if (w->right->color == BLACK && w->left->color == BLACK) { 
       w->color = RED; 
       x = x->parent; 
      } else { 
       if (w->left->color == BLACK) { 
        w->right->color = BLACK; 
        w->color = RED; 
        rotateLeft (rbt, w); 
        w = x->parent->left; 
       } 
       w->color = x->parent->color; 
       x->parent->color = BLACK; 
       w->left->color = BLACK; 
       rotateRight (rbt, x->parent); 
       x = rbt->root; 
      } 
     } 
    } 
    x->color = BLACK; 
} 

RbtStatus rbtErase(RbtHandle h, RbtIterator i) { 
    NodeType *x, *y; 
    RbtType *rbt = h; 
    NodeType *z = i; 

    if (z->left == SENTINEL || z->right == SENTINEL) { 
     // y has a SENTINEL node as a child 
     y = z; 
    } else { 
     // find tree successor with a SENTINEL node as a child 
     y = z->right; 
     while (y->left != SENTINEL) y = y->left; 
    } 

    // x is y's only child 
    if (y->left != SENTINEL) 
     x = y->left; 
    else 
     x = y->right; 

    // remove y from the parent chain 
    x->parent = y->parent; 
    if (y->parent) 
     if (y == y->parent->left) 
      y->parent->left = x; 
     else 
      y->parent->right = x; 
    else 
     rbt->root = x; 

    if (y != z) { 
     z->key = y->key; 
     z->val = y->val; 
    } 


    if (y->color == BLACK) 
     deleteFixup (rbt, x); 

    free (y); 

    return RBT_STATUS_OK; 
} 

RbtIterator rbtNext(RbtHandle h, RbtIterator it) { 
    RbtType *rbt = h; 
    NodeType *i = it; 

    if (i->right != SENTINEL) { 
     // go right 1, then left to the end 
     for (i = i->right; i->left != SENTINEL; i = i->left); 
    } else { 
     // while you're the right child, chain up parent link 
     NodeType *p = i->parent; 
     while (p && i == p->right) { 
      i = p; 
      p = p->parent; 
     } 

     // return the "inorder" node 
     i = p; 
    } 
    return i != SENTINEL ? i : NULL; 
} 

RbtIterator rbtBegin(RbtHandle h) { 
    RbtType *rbt = h; 

    // return pointer to first value 
    NodeType *i; 
    for (i = rbt->root; i->left != SENTINEL; i = i->left); 
    return i != SENTINEL ? i : NULL; 
} 

RbtIterator rbtEnd(RbtHandle h) { 
    // return pointer to one past last value 
    return NULL; 
} 

void rbtKeyValue(RbtHandle h, RbtIterator it, void **key, void **val) { 
    NodeType *i = it; 

    *key = i->key; 
    *val = i->val; 
} 


void *rbtFind(RbtHandle h, void *key) { 
    RbtType *rbt = h; 

    NodeType *current; 
    current = rbt->root; 
    while(current != SENTINEL) { 
     int rc = rbt->compare(key, current->key); 
     if (rc == 0) return current; 
     current = (rc < 0) ? current->left : current->right; 
    } 
    return NULL; 
#include <stdio.h> 
#include <stdlib.h> 
#include "rbtr.h" 

int compare(void *a, void *b) { 
    return *(int *)a - *(int *)b; 
} 

int main(int argc, char **argv) { 
    int maxnum, ct; 

    // command-line: 
    // 
    // rbtmain 2000 
    //  process 2000 records 

    RbtIterator i; 
    RbtHandle h; 
    RbtStatus status; 

    maxnum = atoi(argv[1]); 

    // obtain handle to red-black tree 
    h = rbtNew(compare); 

    printf("maxnum = %d\n", maxnum); 
    for (ct = maxnum; ct; ct--) { 
     int key = rand() % 90 + 1; 

     if ((i = rbtFind(h, &key)) != rbtEnd(h)) { 
      // found an existing node 
      void *keyp, *valuep; 

      // get key-value pointers 
      rbtKeyValue(h, i, &keyp, &valuep); 

      // check to see they contain correct data 
      if (*(int *)keyp != key) printf("fail keyp\n"); 
      if (*(int *)valuep != 10*key) printf("fail valuep\n"); 

      // erase node in red-black tree 
      status = rbtErase(h, i); 
      if (status) printf("fail: status = %d\n", status); 

      // free the pointers allocated by main 
      free(keyp); free(valuep); 

     } else { 
      // create a new node 
      int *keyp, *valuep; 

      // allocate key/value data 
      keyp = (int *)malloc(sizeof(int)); 
      valuep = (int *)malloc(sizeof(int)); 

      // initialize with values 
      *keyp = key; 
      *valuep = 10*key; 

      // insert in red-black tree 
      status = rbtInsert(h, keyp, valuep); 
      if (status) printf("fail: status = %d\n", status); 
     } 
    } 

    // output nodes in order 
    for (i = rbtBegin(h); i != rbtEnd(h); i = rbtNext(h, i)) { 
     void *keyp, *valuep; 
     rbtKeyValue(h, i, &keyp, &valuep); 
     printf("%d %d\n", *(int *)keyp, *(int *)valuep); 
    } 

    // delete my allocated memory 
    for (i = rbtBegin(h); i != rbtEnd(h); i = rbtNext(h, i)) { 
     void *keyp, *valuep; 
     rbtKeyValue(h, i, &keyp, &valuep); 
     free(keyp); free(valuep); 
    } 

    // delete red-black tree 
    rbtDelete(h); 

    return 0; 
} 
} 

Answer 1

有什么不对呢？

这是一段文字，没有明显的努力来缩小问题的范围。可能是因为您有权利认为我们将采取您的完整程序并为您进行完整的回归测试，而对于我们所寻找的问题没有任何指导，否则它不起作用。