紅黑樹插入修復錯誤

Question

我有一個關於在c＃中插入紅黑樹的作業問題。我編寫了下面的代碼，該程序在添加前3個數字時沒有任何問題。當我嘗試添加第4個數字時，我得到一個NullReferenceException。我試圖解決2天的錯誤，但我無法弄清楚。

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace Algoritmalar3b 
{ 
class rbtNode 
{ 
    public int? key; 
    public char? color; 
    public rbtNode left, right, p; 
    public rbtNode(int? key, char? color, rbtNode left, rbtNode right, rbtNode p) 
    { 
     this.key = key; 
     this.color = color; 
     this.left = left; 
     this.right = right; 
     this.p = p; 
    } 
} 

class Program 
{ 
    static rbtNode Tnil = new rbtNode(null, 'B', null, null, null); 

    static void Main(string[] args) 
    { 
     rbtNode root = new rbtNode(null, 'B', Tnil, Tnil, null); 

     RB_Insert(root, 7); 
     RB_Insert(root, 3); 
     RB_Insert(root, 89); 
     RB_Insert(root, 4); 
     RB_Insert(root, 9); 
     RB_Insert(root, 15); 
     RB_Insert(root, 35); 
     RB_Insert(root, 8); 
     RB_Insert(root, 24); 
     preOrderWalk(root); 
    } 

    static void RB_Insert(rbtNode T, int? deger) 
    { 
     rbtNode z = new rbtNode(deger, null, Tnil, Tnil, null); 

     if (T.key == null) 
      T.key = deger; 
     else 
     { 
      rbtNode y = new rbtNode(null, null, Tnil, Tnil, null); 
      y = Tnil; 
      rbtNode x = new rbtNode(null, null, Tnil, Tnil, null); 
      x = T; 
      while (x != Tnil) 
      { 
       y = x; 
       if (z.key < x.key) 
        x = x.left; 
       else 
        x = x.right; 
      } 
      z.p = y; 
      if (y == Tnil) 
       T = z; 
      else if (z.key < y.key) 
       y.left = z; 
      else 
       y.right = z; 
      z.left = Tnil; 
      z.right = Tnil; 
      z.color = 'R'; 
      RB_Insert_Fixup(T, z); 
     } 
    } 

    static void RB_Insert_Fixup(rbtNode T, rbtNode z) 
    { 
     rbtNode y = new rbtNode(null, null, Tnil, Tnil, null); 

     while (z.p.color == 'R') 
     { 
      if (z.p == z.p.p.left) 
      { 
       y = z.p.p.right; 
       if (y.color == 'R') 
       { 
        z.p.color = 'B'; 
        y.color = 'B'; 
        z.p.p.color = 'R'; 
        z = z.p.p; 
       } 
       else if (z == z.p.right) 
       { 
        z = z.p; 
        Left_Rotate(T, z); 
        z.p.color = 'B'; 
        z.p.p.color = 'R'; 
        Right_Rotate(T, z.p.p); 
       } 
      } 
      else 
      { 
       y = z.p.p.left; 
       if (y.color == 'R') 
       { 
        z.p.color = 'B'; 
        y.color = 'B'; 
        z.p.p.color = 'R'; 
        z = z.p.p; 
       } 
       else if (z == z.p.left) 
       { 
        z = z.p; 
        Left_Rotate(T, z); 
        z.p.color = 'B'; 
        z.p.p.color = 'R'; 
        Right_Rotate(T, z.p.p); 
       } 
      } 
     } 
     T.color = 'B'; 
    } 

    static void Left_Rotate(rbtNode T, rbtNode x) 
    { 
     rbtNode y = new rbtNode(null, null, Tnil, Tnil, null); 
     y = x.right; 
     x.right = y.left; 
     if (y.left != Tnil) 
      y.left.p = x; 
     y.p = x.p; 
     if (x.p == Tnil) 
      T = y; 
     else if (x == x.p.left) 
      x.p.left = y; 
     else 
      x.p.right = y; 
     y.left = x; 
     x.p = y; 
    } 

    static void Right_Rotate(rbtNode T, rbtNode x) 
    { 
     rbtNode y = new rbtNode(null, null, Tnil, Tnil, null); 
     y = x.left; 
     x.left = y.right; 
     if (y.right != null) 
      y.right.p = x; 
     y.p = x.p; 
     if (x.p == null) 
      T = y; 
     else if (x == x.p.right) 
      x.p.right = y; 
     else 
      x.p.left = y; 
     y.right = x; 
     x.p = y; 
    } 

    static void preOrderWalk(rbtNode T) 
    { 
     if (T.color == 'B') 
      Console.WriteLine("-{0}", T.key); 
     else 
      Console.WriteLine("{0}", T.key); 
     if (T.left != null) 
      preOrderWalk(T.left); 
     if (T.right != null) 
      preOrderWalk(T.right); 
    } 
} 

}

Answer 1

看來你有3個方面的問題：

• 的RB樹算法。但它看起來像你差不多
• 調試。只需要2分鐘的時間來回溯這樣的錯誤，如果你是新的，可能需要2小時。但不是2天。
• 問個好問題。你有一個nullref，但是在哪一行？那條線上的變量/字段的值是什麼？

---

當我快速瀏覽一下在一個修復程序方法，我懷疑你可能有一個P（父）的代碼的其餘部分REF在錯誤的點被空。

作爲一種診斷工具，改變.P成員在一個普通的屬性：

class rbtNode 
{  
    private rbtNode _parent; 

    public rbtNode Parent 
    { 
     get { return _parent; } 
     set 
     { 
      System.Diagnostics.Debug.Assert(value != null); 
      _parent = value; 
     } 
    } 
    .... 

我認爲你將不得不讓_parent = NULL，但只有在構造函數中。

get/set成員還爲您提供了一個放置（有條件）斷點的好地方。

Answer 2

我相信你在fix_up函數中出錯了。在while循環中添加一些條件，即

while (z != null && z.Getparent() != null && z.Getparent().Getcolor() == 'R') 

此外，您在while循環的其他部分發生了重大錯誤。改變LeftRotate和RightRotate功能的順序，應該是如下：

   else if (z == z.Getparent().Getleft()) 
        { 
         z = z.Getparent(); 
         **RightRotate(T, z);** 
         z.Getparent().Setcolor('B'); 
         z.Getparent().Getparent().Setcolor('R'); 
         **LeftRotate(T, z);** 
        } 

編輯：您還需要在兩個旋轉功能，增加一些更多的條件。