Erreur de correction d'insertion d'arbre rouge-noir
-
28-10-2019 - |
Question
J'ai un problème de devoirs à propos de l'insertion dans des arbres rouge-noir en c #.J'ai écrit le code ci-dessous et le programme fonctionne sans aucun problème pour ajouter les 3 premiers chiffres.Quand j'essaye d'ajouter le 4ème nombre, j'obtiens une NullReferenceException.J'essaye de résoudre l'erreur pendant 2 jours, mais je n'arrive pas à comprendre.
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);
}
}
}
La solution
Il semble que vous ayez des problèmes dans 3 domaines:
- L'algorithme d'arborescence RB.Mais il semble que vous y êtes presque
- Débogage.Cela ne devrait prendre que 2 minutes pour revenir sur une erreur comme celle-ci, peut-être 2 heures si vous êtes nouveau.Mais pas 2 jours.
- Poser une bonne question.Vous avez un nullref, mais sur quelle ligne?et quelles sont les valeurs des variables / champs sur cette ligne?
Quand je regarde rapidement la méthode Fixup et le reste du code, je soupçonne que vous pouvez avoir une référence p (Parent) nulle au mauvais moment.
En tant qu'outil de diagnostic, modifiez le membre .p dans une propriété standard:
class rbtNode
{
private rbtNode _parent;
public rbtNode Parent
{
get { return _parent; }
set
{
System.Diagnostics.Debug.Assert(value != null);
_parent = value;
}
}
....
Je pense que vous devrez autoriser _parent= null mais uniquement dans le constructeur.
Les membres get / set vous donnent également un bon endroit pour placer des points d'arrêt (conditionnels).
Autres conseils
Je pense que vous vous trompez un peu dans votre fonction fix_up .Ajoutez certaines conditions dans la boucle while, c'est-à-dire
while (z != null && z.Getparent() != null && z.Getparent().Getcolor() == 'R')
De plus, vous faites une erreur majeure dans l'autre partie de votre boucle while.Changez l'ordre des fonctions LeftRotate et RightRotate, cela devrait être comme suit:
else if (z == z.Getparent().Getleft())
{
z = z.Getparent();
**RightRotate(T, z);**
z.Getparent().Setcolor('B');
z.Getparent().Getparent().Setcolor('R');
**LeftRotate(T, z);**
}
EDIT: vous devrez également ajouter quelques conditions supplémentaires dans les deux fonctions Rotation.