紅黑樹 - 刪除

Question

我已經實現了RBT（基於Cormen）的刪除功能，它看起來像它的工作，但在preorder中測試刪除+打印樹給了我錯誤的答案。我花了幾個小時尋找的東西可能是錯誤的，但找不到任何...

這裏的FUNC打印樹序：

void print_out(rbt_node *root, rbt_node *NIL) 
{ 
    if(root != NIL) 
    { 
     printf("%d %s ", root->key, root->data.c_str()); 
     if(root->color == BLACK) 
      printf("black "); 
     else 
      printf("red "); 
     if(root->parent != NIL) 
      printf("%d ",root->parent->key); 
     else 
      printf("- "); 
     if(root->left != NIL) 
      printf("%d ",root->left->key); 
     else 
      printf("- "); 
     if(root->right != NIL) 
      printf("%d ",root->right->key); 
     else 
      printf("- "); 
     printf("\n"); 

     print_out(root->left, NIL); 
     if(root->right != NIL) 
     { 
      print_out(root->right, NIL); 
     } 
    } 
} 

這裏是缺失的重要的東西休息：

rbt_node *NIL = new rbt_node; 
NIL->color = BLACK; 
NIL->left = NIL->parent = NIL->right = NIL; 

rbt_node *tree_minimum(rbt_node *node, rbt_node *NIL) 
{ 
    while(node->left != NIL) 
     node = node->left; 

    return node; 
} 

rbt_node *tree_succesor(rbt_node *node, rbt_node *NIL) 
{ 
    if(node->right != NIL) 
     return tree_minimum(node->right, NIL); 

    rbt_node *helper = node->parent; 
    while(helper != NIL && node == helper->right) 
    { 
     node = helper; 
     helper = helper->parent; 
    } 

    return helper; 
} 

void delete_fixup(rbt_node *&root, rbt_node *&target, rbt_node *NIL) 
{ 
    rbt_node *helper = NIL; 
    while(target != root && target->color == BLACK) 
    { 
     if(target == target->parent->left) 
     { 
      helper = target->parent->right; 
      if(helper->color == RED) 
      { 
       helper->color = BLACK; 
       target->parent->color = RED; 
       left_rotate(root, target->parent, NIL); 
       helper = target->parent->right; 
      } 
      if(helper->left->color == BLACK && helper->right->color == BLACK) 
      { 
       helper->color = RED; 
       target = target->parent; 
      } 
      else if(helper->right->color== BLACK) 
      { 
       helper->left->color = BLACK; 
       helper->color = RED; 
       right_rotate(root, helper, NIL); 
       helper = target->parent->right; 
      } 
      else 
      { 
       helper->color = target->parent->color; 
       target->parent->color = BLACK; 
       helper->right->color = BLACK; 
       left_rotate(root, target->parent, NIL); 
       target = root; 
      } 
     } 
     else 
     { 
      helper = target->parent->left; 
      if(helper->color == RED) 
      { 
       helper->color = BLACK; 
       target->parent->color = RED; 
       right_rotate(root, target->parent, NIL); 
       helper = target->parent->left; 
      } 
      if(helper->right->color == BLACK && helper->left->color == BLACK) 
      { 
       helper->color = RED; 
       target = target->parent; 
      } 
      else if(helper->left->color== BLACK) 
      { 
       helper->right->color = BLACK; 
       helper->color = RED; 
       left_rotate(root, helper, NIL); 
       helper = target->parent->left; 
      } 
      else 
      { 
       helper->color = target->parent->color; 
       target->parent->color = BLACK; 
       helper->left->color = BLACK; 
       right_rotate(root, target->parent, NIL); 
       target = root; 
      } 
     } 
    } 

    target->color = BLACK; 
} 

void rbt_delete(rbt_node *&root, int key, rbt_node *NIL) 
{ 
    rbt_node *victim = to_delete(root, key, NIL); 
    if(victim != NIL) 
    { 
     rbt_node *help_one = NIL; 
     rbt_node *help_two = NIL; 
     if(victim->left == NIL || victim->right == NIL) 
      help_one = victim; 
     else 
      help_one = tree_succesor(victim, NIL); 

     if(help_one->left != NIL) 
      help_two = help_one->left; 
     else 
      help_two = help_one->right; 

     help_two->parent = help_one->parent; 

     if(help_one->parent == NIL) 
      root = help_two; 
     else if(help_one == help_one->parent->left) 
      help_one->parent->left = help_two; 
     else 
      help_two->parent->right = help_two; 

     if(help_one != victim) 
     { 
      victim->key = help_one->key; 
      victim->data = help_one->data; 
     } 

     if(help_one->color == BLACK) 
      delete_fixup(root, help_two, NIL); 
    } 

    root->color = BLACK; 
} 

Answer 1

至少IMO，你的print_out是不是真的應該如此。具體問題是它試圖（直接）爲子節點打印數據。

當你處理一個二叉樹（任何種類 - 不平衡，AVL，RB等）穿越通常會看起來大致是這樣的：

void print_out(node *current_node) { 
    if current_node != NIL { 
     show_data(current_node); 

     print_out(current_node->left); 
     print_out(current_node->right); 
    } 
} 

原樣，這是預購;後續訂單或訂單只是重新排列print_data而不是遞歸調用print_out（對於它們之後的訂單，因爲它們之間是中間的）。

但是，print_out尤其不應將任何東西用於左子樹或右子樹，除了在遞歸調用中將它們作爲參數傳遞以外。它也不應該檢查它們是否爲NIL/NULL - 它應該只是進行遞歸調用，並讓if (current_node != NIL)在遞歸調用中處理我們碰到葉節點的可能性。

叫我懶，如果你願意，但是這大約相當於我願意沒有至少檢查約我在尋找什麼樣的問題，對於一些指導，並至少爲合理保證它的正確的地方看看。例如，如果您顯示可以插入少數節點並獲得預期的結構，那麼將會很有幫助，然後顯示當您刪除節點時出錯。節點還在嗎？其他節點是否迷路？所有的節點都是正確的，但平衡是錯誤的？如果是這樣，那麼天平有什麼問題？