红黑树 - fixTree 实现无法正常工作

Question

插入几个数字后显示红黑树出现问题。可能 fixTree 函数包含一些错误（插入数字后仅显示第一个数字 = 38）。

有人知道哪里出了问题吗？

#include <stdio.h>
#include <stdlib.h>
#define swap(type, i, j) {type t = i; i = j; j = t;}

typedef enum COLOR{
  RED,
  BLACK
} NodeColor;

typedef struct BST{
  struct BST *up, *left, *right;
  int key, color;
} RedBlackTree;

RedBlackTree *tree = NULL;

RedBlackTree *createNode(int key){
  RedBlackTree *temp;
  temp = (RedBlackTree*) malloc(sizeof(RedBlackTree));
  temp->left = NULL;
  temp->right = NULL;
  temp->key = key;
  temp->color = RED;
  return temp;
}

void rotateLeft(RedBlackTree *root, RedBlackTree *temp){
  RedBlackTree *rightSon = temp->right;
  temp->right = rightSon->left;
  if (temp->right != NULL){
    temp->right->up = temp;
  }
  rightSon->up = temp->up;
  if (temp->up == NULL){
    root = rightSon;
  }
  else if (temp == temp->up->left){
    temp->up->left = rightSon;
  }
  else{
    temp->up->right = rightSon;
  }
  rightSon->left = temp;
  temp->up = rightSon;
}

void rotateRight(RedBlackTree *root, RedBlackTree *temp){
  RedBlackTree *leftSon = temp->left;
  temp->left = leftSon->right;
  if (temp->left != NULL){
    temp->left->up = temp;
  }
  leftSon->up = temp->up;
  if (temp->up == NULL){
    root = leftSon;
  }
  else if (temp == temp->up->left){
    temp->up->left = leftSon;
  }
  else{
    temp->up->right = leftSon;
  }
  leftSon->right = temp;
  temp->up = leftSon;
}

void fixTree(RedBlackTree *root, RedBlackTree *temp){
  RedBlackTree *parent = NULL;
  RedBlackTree *grandparent = NULL;
  while ((temp != root) && (temp->color != BLACK) && (temp->up->color == RED)){
    parent = temp->up;
    grandparent = temp->up->up;
    if (parent == grandparent->left){
       RedBlackTree *uncle = grandparent->right;
      if (uncle != NULL && uncle->color == RED){
        grandparent->color = RED;
        parent->color = BLACK;
        uncle->color = BLACK;
        temp = grandparent;
      }
      else{
        if (temp == parent->right){
          rotateLeft(root, parent);
          temp = parent;
          parent = temp->up;
        }
        rotateRight(root, grandparent);
        swap(int, parent->color, grandparent->color);
        temp = parent;
      }
    }
    else{
      RedBlackTree *uncle = grandparent->left;
      if ((uncle != NULL) && (uncle->color == RED)){
        grandparent->color = RED;
        parent->color = BLACK;
        uncle->color = BLACK;
        temp = grandparent;
      }
      else{
        if (temp == parent->left){
          rotateRight(root, parent);
          temp = parent;
          parent = temp->up;
        }
        rotateLeft(root, grandparent);
        swap(int, parent->color, grandparent->color);
        temp = parent;
      }
    }
  }
  root->color = BLACK;
}

RedBlackTree *insertNode(RedBlackTree *root, RedBlackTree *temp){
  if (root == NULL){
    return temp;
  }
  if (temp->key < root->key){
    root->left = insertNode(root->left, temp);
    root->left->up = root;
  }
  else if (temp->key > root->key){
    root->right = insertNode(root->right, temp);
    root->right->up = root;
  }
  return root;
}

void insert(int key){
  RedBlackTree *temp = createNode(key);
  tree = insertNode(tree, temp);
  fixTree(tree, temp);
}

void printTree(RedBlackTree *root){
  if (root){
    printTree(root->left);
    printf("%d %s\n", root->key, root->color == 0 ? "RED" : "BLACK");
    printTree(root->right);
  }
}

int main(){
  insert(38);
  insert(31);
  insert(22);
  insert(8);
  insert(20);
  insert(5);
  insert(10);
  insert(9);
  insert(21);
  insert(27);
  insert(29);
  insert(25);
  insert(28);
  printTree(tree);
  return 0;
}

Answer 1

void fixTree(RedBlackTree *root, RedBlackTree *temp)

您通过值传递根的地址，因此对 root 内部 fixTree 的任何更改都不会在调用代码中可见。特别是rotateLeft和rotateRight，你再把copy的地址改进去，不会修改调用代码中的变量。

您需要传递一个指向根指针的指针。这意味着您的原型应该是

void fixTree(RedBlackTree **p_root, RedBlackTree *temp)

自然而然地调整了操作，因此它们在 *p_root 上执行。比如下面这行rotateLeft：

*p_root = rightSon;

红黑树 - fixTree 实现无法正常工作

Red Black Tree - fixTree implementtation doesn't work correctly

c

red-black-tree