红黑树插入节点后执行平衡操作时触发Null Exception的问题求助

核心问题触发原因 #

• 校验顺序错误：函数第一行直接访问node.parent.parent，随后才判断node.parent == null，如果传入的node的父节点就是根节点（父节点的父节点为null），或是node本身就是根节点，第一行代码就会触发空指针，你的空校验完全没有起到前置拦截的作用。同时while循环入口直接访问node.parent.color，也没有提前判断父节点是否存在。
• 未处理叔节点为空的场景：红黑树规则中不存在的叔节点默认视为黑色，但你在获取到叔节点temp后，没有做非空校验直接访问temp.color，当叔节点不存在时temp为null，自然触发空指针，也就是你遇到的第156行报错的情况。
• 缺少NIL哨兵节点设计：标准红黑树实现会定义一个全局的黑色NIL哨兵节点，所有空的左右子节点指针都指向这个哨兵，避免出现null访问的情况，你当前用null表示空节点，所有属性访问前都需要额外判空。

修复方案 #

1. 调整校验逻辑顺序 #

进入函数首先处理根节点场景，再进入循环：

//Insert Fix function to balance tree after insertion
 public void InsertFix(Node<T,U> node)
 {
     // 前置校验：如果当前节点父节点为空，说明是根节点，直接染黑返回
     if(node.parent == null)
     {
         node.color = 0;
         root = node;
         return;
     }
     Node<T,U> temp;
     // 循环条件先判断父节点存在且为红色
     while(node.parent != null && node.parent.color == 1)
     {
         // 先判断祖父节点存在，否则直接跳出循环
         if(node.parent.parent == null){
             break;
         }
         if(node.parent.equals(node.parent.parent.right))
        {
            temp = node.parent.parent.left; //uncle
            // 访问color前先判空，null默认是黑色
            if(temp != null && 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.left))
                {
                    node = node.parent;
                    RightRotation(node);
                }
                node.parent.color = 0;
                node.parent.parent.color = 1;
                LeftRotation(node.parent.parent);
            }
         }
        else
        {
          temp = node.parent.parent.right; //uncle
          // 访问color前先判空，null默认是黑色
          if(temp != null && 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;
 }

2. 优化建议（可选） #

引入全局NIL哨兵节点替代null：
定义一个静态的NIL节点，初始color为0（黑色），所有节点创建时左右指针默认指向NIL，根节点的父节点也指向NIL，这样就不需要每次访问属性前做非空校验，代码逻辑更简洁。

内容的提问来源于stack exchange，提问作者Lucky_13