紅色黑色修正

Question

我實施了一個紅色的黑色樹，但效果不佳。它以不正確的方式插入節點。我認爲這是因爲FixUp。有誰知道我在哪裏錯了？ 當我插入（1，4，9，16）。在節點16處，它將根顏色設置爲紅色。然後停止。

我調試過它，但我無法自己找到錯誤。我是新的C＃和 進一步，我現在正在它上面工作大約3個小時。沒有成功。

這是我的代碼：

public void insert(int score, int spelersnummer) 
    { 
     size++; 
     Node z = new Node(score, spelersnummer); 
     z.leftChilds++; 
     Node y = null; 
     Node x = this.root; 
     while (x != null) 
     { 
      y = x; 
      if (z.boom < x.boom) // boom staat voor score! 
      { 
       x.leftChilds++; 
       x = x.left; 
      } 
      else 
      { 
       x = x.right; 
      } 

     } 

     if (y == null) 
     { 
      this.root = z; 

     } 
     else if (z.boom < y.boom) 
     { 
      y.left = z; 
      y.leftChilds++; 
      z.parent = y; 

     } 
     else 
     { 
      y.right = z; 
      z.parent = y; 

     } 
     // Z heeft automatisch left = null, right = null, color = red 
     insertFixUp(z); 
    } 

    public void insertFixUp(Node z) 
    { 
     // check of parent bestaat en parent.parent NullPointerException? 
     if(z.parent != null && z.parent.parent != null) 
     { 
      while (z != null && z.parent != null && z.parent.parent != null && !z.parent.isBlack) // ass long as color is not black, thus red 
      { 
       if (z.parent == z.parent.parent.left) 
       { 
        Node y = z.parent.parent.right; 
        if (y != null && !y.isBlack) 
        { 
         z.parent.isBlack = true; 
         y.isBlack = true; 
         z.parent.parent.isBlack = false; 
         z = z.parent.parent; 
        } 
        else if (z == z.parent.right) 
        { 
         z = z.parent; 
         leftRotate(z); 
        } 
        z.parent.isBlack = true; 
        z.parent.parent.isBlack = false; 
        rightRotate(z.parent.parent); 

       } 
       else 
       { 

        Node y = z.parent.parent.left; // left instead of right 
        if (y != null && !y.isBlack) // is red? 
        { 
         z.parent.isBlack = true; // color = black 
         y.isBlack = true; // color = black 
         z.parent.parent.isBlack = false; // color = red 
         z = z.parent.parent; 
        } 
        else 
        { 
         if (z == z.parent.left) // left instead of right 
         { 
          z = z.parent; 
          rightRotate(z); 
         } 
         z.parent.isBlack = true; // color is black 
         z.parent.parent.isBlack = false; // color is red 
         leftRotate(z.parent.parent); 
        } 
       } 

      } 
     } 
    } 

    public void leftRotate(Node x) 
    { 
     Node y = x.right; 
     x.right = y.left; 
     if (y != null && y.left != null) 
     { 
      y.left.parent = x; 
     } 
     y.parent = x.parent; 
     if (x.parent == null) 
     { 
      root = y; 
     } 
     else if (x.parent.left != null && x == x.parent.left) 
     { 
      x.parent.left = y; 
     } 
     else 
     { 
      x.parent.right = y; 
     } 
     y.left = x; 

     x.parent = y; 

     int lefts; 
     lefts = (x.left != null) ? x.left.leftChilds : 0; 

     x.leftChilds = lefts + 1; 

     lefts= (y.left != null) ? y.left.leftChilds : 0; 

     y.leftChilds = lefts + 1; 
    } 

    public void rightRotate(Node x) 
    { 
     Node y = x.left; 
     x.left = y.right; 
     if (y != null && x != null && y.right != null) 
     { 
      y.right.parent = x; 
     } 
     y.parent = x.parent; 
     if (x.parent == null) 
     { 
      root = y; 
     } 
     else if (x.parent.right != null && x == x.parent.right) 
     { 
      x.parent.right = y; 
     } 
     else 
     { 
      x.parent.left = y; 
     } 
     y.right = x; 
     x.parent = y; 

     int lefts; 
     lefts = (x.left != null) ? x.left.leftChilds : 0; 

     x.leftChilds = lefts + 1; 

     lefts = (y.left != null) ? y.left.leftChilds : 0; 

     y.leftChilds = lefts + 1; 
    } 

Answer 1

這個實現是C.希望你可以把它轉換成C＃。

struct node { 
    int key; 
    char cl; 
    struct node *left; 
    struct node *right; 
    struct node *parent; 
} *p; 

void left_rotate(struct node *r, struct node *q) { 
    struct node *y; 
    y = q -> right; 
    q -> right = y -> left; 
    y -> left -> parent = q; 
    y -> parent = q -> parent; 
    if (q -> parent != NULL) { 
     if (q == q -> parent -> left) q -> parent -> left = y; 
     else q -> parent -> right = y; 
    } 
    else p = y; 
    y -> left = q; 
    q -> parent = y; 
} 
void right_rotate(struct node *r, struct node *q) { 
    struct node *y; 
    y = q -> left; 
    q -> left = y -> right; 
    y -> right -> parent = q; 
    y -> parent = q -> parent; 
    if (q -> parent != NULL) { 
     if (q == q -> parent -> left) q -> parent -> left = y; 
     else q -> parent -> right = y; 
    } 
    else p = y; 
    y -> right = q; 
    q -> parent = y; 
} 

void ins_fix(struct node *r, struct node *q) { 
    while (q != r &&q -> parent -> cl == 'r') { 
     if (q -> parent == q -> parent -> parent -> left) { 
      if (q -> parent -> parent -> right -> cl == 'r') { 
       q -> parent -> cl = 'b'; 
       q -> parent -> parent -> cl = 'r'; 
       q -> parent -> parent -> right -> cl = 'b'; 
       q = q -> parent -> parent; 
      } 
      else { 
       if (q == q -> parent -> right) { 
        q = q -> parent; 
        left_rotate(p, q); 
       } 
       q -> parent -> cl = 'b'; 
       q -> parent -> parent -> cl = 'r'; 
       right_rotate(p, q -> parent -> parent); 
      } 
     } 
     else { 
      if (q -> parent -> parent -> left -> cl == 'r') { 
       q -> parent -> cl = 'b'; 
       q -> parent -> parent -> cl = 'r'; 
       q -> parent -> parent -> left -> cl = 'b'; 
       q = q -> parent -> parent; 
      } 
      else { 
       if (q == q -> parent -> left) { 
        q = q -> parent; 
        right_rotate(p, q); 
       } 
       q -> parent -> cl = 'b'; 
       q -> parent -> parent -> cl = 'r'; 
       left_rotate(p, q -> parent -> parent); 
      } 
     } 
    } 
    p -> cl = 'b'; 
} 

void add(int num) { 
    struct node *temp, *r, *nil; 
    temp = (struct node *) malloc(sizeof(struct node)); 
    nil = (struct node *) malloc(sizeof(struct node)); 
    temp -> key = num; 
    temp -> right = nil; 
    temp -> left = nil; 
    temp -> parent = NULL; 
    temp -> cl = 'r'; 
    nil -> parent = temp; 
    nil -> cl = 'b'; 
    nil -> right = NULL; 
    nil -> left = NULL; 
    nil -> key = NULL; 
    r = p; 
    if (p == NULL || p -> key == NULL) { 
     p = temp; 
     p -> parent = NULL; 
     p -> cl = 'b'; 
     return; 
    } 
    while (1) { 
     if (r -> left -> key == NULL &&r -> key >= num) { 
      r -> left = temp; 
      temp -> parent = r; 
      ins_fix(p, temp); 
      return; 
     } 
     else if (r -> right -> key == NULL &&r -> keyright = temp; 
     temp -> parent = r; 
     ins_fix(p, temp); 
     return; 
     } 
     else if (r -> key >= num) r = r -> left; 
     else if (r -> keyright; 
     } 
    } 

    struct node *tree_min(struct node *r) { 
     while (r -> left -> key != NULL) { 
      r = r -> left; 
     } 
     return r; 
    } 
    struct node *successor(struct node *r) { 
     struct node *y; 
     if (r -> right -> key != NULL) return tree_min(r -> right); 
     y = r -> parent; 
     while (y != NULL &&r == y -> right) { 
      r = y; 
      y = y -> parent; 
     } 
     return y; 
    } 

    void RB_Del_Fix(struct node *r, struct node *x) { 
     struct node *w; 
     while (x != r &&x -> cl == 'b') { 
      if (x == x -> parent -> left) { 
       w = x -> parent -> right; 
       if (w -> cl == 'r') { 
        w -> cl = 'b'; 
        x -> parent -> cl = 'r'; 
        left_rotate(p, x -> parent); 
        w = x -> parent -> right; 
       } //if closed 
       if (w -> left -> cl == 'b' &&w -> right -> cl == 'b') { 
        w -> cl = 'r'; 
        x = x -> parent; 
       } //if closed 
       else { 
        if (w -> right -> cl == 'b') { 
         w -> left -> cl = 'b'; 
         w -> cl = 'r'; 
         right_rotate(p, w); 
         w = x -> parent -> right; 
        } //if closed 
        w -> cl = x -> parent -> cl; 
        x -> parent -> cl = 'b'; 
        w -> right -> cl = 'b'; 
        left_rotate(p, x -> parent); 
        x = r; 
       } //else closed 
      } //if main closed 
      else { 
       w = x -> parent -> left; 
       if (w -> cl == 'r') { 
        w -> cl = 'b'; 
        x -> parent -> cl = 'r'; 
        right_rotate(p, x -> parent); 
        w = x -> parent -> left; 
       } //if closed 
       if (w -> left -> cl == 'b' &&w -> right -> cl == 'b') { 
        w -> cl = 'r'; 
        x = x -> parent; 
       } //if closed 
       else { 
        if (w -> left -> cl == 'b') { 
         w -> right -> cl = 'b'; 
         w -> cl = 'r'; 
         left_rotate(p, w); 
         w = x -> parent -> left; 
        } //if closed 
        w -> cl = x -> parent -> cl; 
        x -> parent -> cl = 'b'; 
        w -> left -> cl = 'b'; 
        right_rotate(p, x -> parent); 
        x = r; 
       } //else closed 
      } //else main closed 
     } //while closed 
     x -> cl = 'b'; 
    } 
    void del(int num) { 
     struct node *r, *temp, *y; 
     r = p; 
     if (r == NULL) { 
      printf("Tree is Empty."); 
      return; 
     } 
     while (r -> key != num || r -> key == NULL) { 
      if (r -> key == NULL) { 
       printf("Number not in Tree."); 
       return; 
      } 
      if (r -> key >= num) r = r -> left; 
      else r = r -> right; 
     } 
     if (r -> left -> key == NULL || r -> right -> key == NULL) y = r; 
     else y = successor(r); 
     if (y -> left -> key == NULL) temp = y -> right; 
     else temp = y -> left; 
     temp -> parent = y -> parent; 
     if (y -> parent == NULL) p = temp; 
     else { 
      if (y == y -> parent -> left) y -> parent -> left = temp; 
      else y -> parent -> right = temp; 
     } 
     if (y != r) r -> key = y -> key; 
     if (y -> cl == 'b') RB_Del_Fix(p, temp); 
    } 
    void display(struct node *r) { 

     if (r -> key == NULL) return; 
     display(r -> left); 
     printf(" (%d<->%c) ->", r -> key, r -> cl); 
     display(r -> right); 

    } 

    void main() { 

     int i, num; 
     clrscr(); 
     do { 
      printf("\n\tEnter the number for following work"); 
      printf("\n\n\t1=>Enter number to add"); 
      printf("\n\n\t2=>Display sorted element"); 
      printf("\n\n\t3=>Enter the number to delete from list\n\n"); 
      scanf("%d", &i); 
      switch (i) { 
      case 1: 
       { 
        printf("\nEnter the number to enter\n"); 
        scanf("%d", &num); 
        add(num); 
        break; 
       } 

      case 2: 
       { 
        display(p); 
        getch(); 
        break; 
       } 
      case 3: 
       { 
        printf("Enter the number"); 
        scanf("%d", &num); 
        del(num); 
        getch(); 
        break; 
       } 

      default: 
       exit(1); 
      } 
      clrscr(); 
     } while (1); 

    }​ 

希望你會找到你的解決方案。