0

在我的红黑树中，我有来自红色节点的红色孩子，我的代码有什么问题？

RBTree 的结构：

    num COLOR { RED, BLACK };
    
    // struct RBT
    typedef struct treeRBTnode {
      int key;
      enum COLOR color;
      struct treeRBTnode* parent;  // padre
      struct treeRBTnode* left;    // figlio sinistro
      struct treeRBTnode* right;   // figlio sinistro
    } RBTNode;
    
    typedef struct {
      int cardinality;
      struct treeRBTnode* root;
      struct treeRBTnode* Nil;
    } RBTree;

函数用 T->Nil sentinel 创建一个 RBTree 并创建一个新节点：

    //Initialize RBT
    RBTree* InitializeRBT() {
      RBTree* T = (RBTree*)malloc(sizeof(RBTree));
      T->Nil = (RBTNode*)malloc(sizeof(RBTNode));
      T->cardinality = 0;
      T->Nil->left = T->Nil->right = T->Nil->parent = NULL;
      T->Nil->color = BLACK;
      T->Nil->key = 0;
      T->root = T->Nil;
      return T;
    }
 
//Create a new Node;
    //create a new node
    RBTNode* RBTnewNode(int key) {
      RBTNode* tmp = (RBTNode*)malloc(sizeof(RBTNode));
      tmp->key = key;
      tmp->color=RED;
      tmp->left = tmp->right = NULL;
      return tmp;

现在用insertfixup、insertfixupleft和right、左右旋转的insert算法代码：

void BSTreeRightRotate(RBTree* T, RBTNode* x) {
  RBTNode* y = x->left;
  x->left = y->right;
  if (y->right != T->Nil)
    y->right->parent = x;
  y->parent = x->parent;
  if (x->parent == T->Nil)
    T->root = y;
  if (x->parent != T->Nil && x == x->parent->left)
    x->parent->left = y;
  if (x->parent != T->Nil && x == x->parent->right)
    x->parent->right = y;
  y->right = x;
  x->parent = y;
}

//leftRotate 相同，但左右颠倒

void RBTreeInsertFixupRight(RBTree* T, RBTNode* x) {
  RBTNode* y = x->parent->parent->left;
  if (y->color == RED) {
    x->parent->color = BLACK;
    y->color = BLACK;
    x->parent->parent->color = RED;
    x = x->parent->parent;
  } else {
    if (x == x->parent->left) {
      x = x->parent;
      BSTreeRightRotate(T, x);
    }
    x->parent->color = BLACK;
    x->parent->parent->color = RED;
    BSTreeLeftRotate(T, x->parent->parent);
  }
}

// 与 fixupleft 相同，但左右颠倒

void RBTreeInsertFixup(RBTree* T, RBTNode* x) {
  while (x->parent->color == RED) {
    if (x->parent == x->parent->parent->left) 
      RBTreeInsertFixupLeft(T, x);
    else
      RBTreeInsertFixupRight(T, x);
  }
  T->root->color = BLACK;
}

void RBTreeInsert(RBTree* T, RBTNode* x) {
  RBTNode* y = T->Nil;
  RBTNode* z = T->root;
  while (z != T->Nil) {
    y = z;
    if (x->key < z->key)
      z = z->left;
    else
      z = z->right;
  }
  x->parent = y;
  if (y == T->Nil)
    T->root = x;
  if (y != T->Nil && x->key < y->key)
    y->left = x;
  if (y != T->Nil && x->key >= y->key)
    y->right = x;
  x->left = T->Nil;
  x->right = T->Nil;
  x->color = RED;
  RBTreeInsertFixup(T, x);
}

现在通过 insert 在树中插入元素后，我意识到一些红色节点有时会有一个红色的孩子，不尊重红黑的有效性。我在我的代码中找不到错误，有人可以帮助我吗？

4

0 回答 0