dimanche 4 octobre 2020

Object reference not set to an instance of an object on insertion avl tree [duplicate]

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