红黑树插入修复错误

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);** 
        } 

编辑：您还需要在两个旋转功能，增加一些更多的条件。