-1

在将节点插入红黑树之后，我正在尝试编写一个函数来平衡红黑树，但是我得到了一个空指针异常。在第 156 行，当我将 temp 分配给 node.parent.parent.right 时，temp 为 null，这意味着 node.parent.parent.right 为 null。我不确定为什么。任何人都可以查看我的代码并尝试帮助我弄清楚为什么会出现这个问题吗？

//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;
 }
4

1 回答 1

0

如果您刚刚插入了一个节点，那将是一个叶节点和红色。如果它的父母是红色的，那就是违规。它的祖父母将自动成为黑色。但是叔叔可能不存在，那是一棵有效的红黑树。

您应该具有确定节点颜色的函数，请记住所有 Nil 节点都是黑色的，如果“不是黑色”，您应该编写执行操作的代码。

如果你沿着根的方向爬树，“叔叔”将是一个真正的节点。

如果您为删除修复删除一个叶节点，也会出现同样的情况。对于删除修复，您需要找到父级、兄弟级和兄弟级子级。兄弟姐妹将永远存在，但兄弟姐妹的孩子可能是 Nil 节点。如果是，它们将自动变为黑色。如果你必须爬树修复删除，那么再次，你会发现兄弟姐妹的孩子是真实的。

于 2021-11-03T18:59:06.017 回答