I'm trying to insert a thousand random numbers in an AVL tree but in random occasions I get a NullReferenceException
error on either right
or left
. See my minimal reproducable example below for the code that I'm having problems with. To get the error, debug on: thousand_tree.insert(f.Next(1,1000));
. i
is not always the same for this error to happen. The error will show on right = right.left;
or left = left.right;
in the rotateLeft()
or rotateRight()
functions.
MRE:
using System;
namespace TestAVL
{
class Node
{
public int number;
public int ld = 1, rd = 1;
public bool lb = true, rb = true;
public int _depth;
public Node left, right;
public Node(int number)
{
this.number = number;
}
public Node insert(int n)
{
if (n == number)
{
if (left == null)
{
left = new Node(n);
}
else
{
right = new Node(n);
}
return this;
}
if (n <= number)
{
if (left == null)
{
left = new Node(n); // Inserts 'n' as a left child if 'n' is lower than the root or equal.
}
else
{
left.insert(n); // Recursion if the left child of the root is not empty.
}
}
else if (n >= number)
{
if (right == null)
{
right = new Node(n); // Inserts 'n' as a right child if 'n' is higher than the root or equal.
}
else
{
right.insert(n); // Recursion if the right child of the root is not empty.
}
}
this._depth = depth();
// left left
if (ld > rd && n < left.number && !isBalanced())
{
return rotateRight();
}
// left right
if (ld > rd && n > left.number && !isBalanced())
{
left = left.rotateLeft();
return rotateRight();
}
// right right
if (rd > ld && n > right.number && !isBalanced())
{
return rotateLeft();
}
// right left
if (rd > ld && n < right.number && !isBalanced())
{
right = right.rotateRight();
return rotateLeft();
}
return this;
}
public Node rotateLeft()
{
Node pivot = right;
right = right.left;
pivot.left = this;
return pivot;
}
public Node rotateRight()
{
Node pivot = left;
left = left.right;
pivot.right = this;
return pivot;
}
public bool isBalanced()
{
this.depth();
if (left != null)
{
lb = left.isBalanced();
}
if (right != null)
{
rb = right.isBalanced();
}
if (Math.Abs(ld - rd) <= 1 && lb == true && rb == true)
{
return true;
}
else
{
return false;
}
}
public int depth()
{
if (left != null)
{
ld = left.depth();
}
else
{
ld = 0;
}
if (right != null)
{
rd = right.depth();
}
else
{
rd = 0;
}
if (ld > rd)
{
return ld + 1;
}
else
{
return rd + 1;
}
}
}
class AVLTree
{
public Node root;
public void insert(int number)
{
if(root != null)
{
this.root = this.root.insert(number);
}
else
{
root = new Node(number);
}
}
}
class SetupCode
{
static public void Main(String[] args)
{
Console.WriteLine("Main Method");
AVLTree thousand_tree = new AVLTree();
Random f = new Random();
for(int i = 0; i < 1000; i++)
{
thousand_tree.insert(f.Next(1, 1000));
} // This gives a 'NullReferenceException', depending on the random number that's being inserted.
AVLTree hundred_inserts = new AVLTree();
for (int i = 1; i <= 100; i++)
{
hundred_inserts.insert(i);
} // This works.
}
}
}
Aucun commentaire:
Enregistrer un commentaire