Null Exception When Balancing Red-Black Tree After Insertion

Question

I'm attempting to write a function to balance a red-black tree after inserting nodes into it, but I'm getting a null pointer exception. On line 156, when I assign temp to node.parent.parent.right, temp is null, meaning node.parent.parent.right is null. I'm not sure why. Would anyone be able to look at my code and try to help me figure out why this issue is occurring?

//Insert Fix function to balance tree after insertion
 public void InsertFix(Node<T,U> node)
 {
     Node<T,U> temp = node.parent.parent;
     if(node.parent == null)
     {
         System.out.println("parent is null");
     }
     while(node.parent.color == 1)
     {
         if(node.parent.equals(node.parent.parent.right))
        {
            temp = node.parent.parent.left; //uncle
            
             
            if(temp.color == 1) //if red parent has red child
            {
                temp.color = 0; //change color of parent
                node.parent.color = 0; //change color of uncle
                node.parent.parent.color = 1; //change color of g-parent
                node= node.parent.parent;
            }
            else 
            {
                if(node.equals(node.parent.left))
                {
                    node = node.parent;
                     
                    //Perform a right rotation
                    RightRotation(node);
                }
                
                node.parent.color = 0;
                node.parent.parent.color = 1;
                 
                //Perform a left rotation
                LeftRotation(node.parent.parent);
            }
         }
         
        else
        {
          temp = node.parent.parent.right; //uncle THIS VALUE IS NULL
          System.out.println(node.parent.parent.right);
          if(temp.color == 1)
          {
              temp.color = 0;
              node.parent.color = 0;
              node.parent.parent.color = 1;
              node = node.parent.parent;
          }
          
          else
          {
              if(node.equals(node.parent.right))
              {
                  node = node.parent;
                  LeftRotation(node);
              }
              
              node.parent.color = 0;
              node.parent.parent.color = 1;
              RightRotation(node.parent.parent);
          }
             
        }
        
        if (node == root)
        {
            break;
        }
     }
     
     root.color = 0;
 }

Does this answer your question? [What is a NullPointerException, and how do I fix it?](https://stackoverflow.com/questions/218384/what-is-a-nullpointerexception-and-how-do-i-fix-it) — Progman, Nov 03 '21 at 21:22

score 0 · Answer 1 · answered Nov 03 '21 at 18:59

If you have just inserted a node, that will be a leaf node and Red. If it's parent is Red that is a violation. Its's grandparent will automatically be Black. But the uncle may not exist and that was a valid Red-Black tree.

You should have function which determines the colour of a Node, bearing in mind that all Nil nodes are Black and you should write the code doing operations if "not Black".

If you climb the tree in the direction of the root, the "Uncle" will be a real node.

The same situation occurs if you delete a leaf Node for Deletion fixups. For deletion fixups, you need to find the parent, the sibling and the siblings children. The sibling will always exist but the sibling's children may be Nil nodes. If they are, they are automatically be black. If you have to climb tree to repair for deletion, then again, you will find the siblings children are real.

Null Exception When Balancing Red-Black Tree After Insertion

1 Answers1