为什么RR的判断不需要加上node.left != null的判断，感觉会有空指针问题

首页课程实战体系课手记专栏慕课教程

来源：2-7 红黑树中添加新元素

thok8s

2023-09-06 12:25:41

为什么不是这么写：

if (isRed(node.left) && null != node.left && isRed(node.left.left)) {

rightRotate(node);

}

而是这样写：

(isRed(node.left) && isRed(node.left.left)) {

rightRotate(node);

}

比如添加一个值为1的元素，递归到 1 - 2 这个三节点 (1为红色，2为黑色），此时由于1已经存在了，所以不会有任何节点添加进行，然后就进入了LL/RR/flipColors这三个操作的判断，此时LL不成立，RR判断的时候，node.left.left 会有空指针问题的

但是实际上运行起来却没问题 -_-

希望老师帮忙解惑，谢谢

写回答

1回答

liuyubobobo

2023-09-06

已采纳

因为如果 node.left 是空的话， isRed(node.left) 就会返回 false（请看一下 isRed 的逻辑）。

isRed(node.left) 返回 false 以后，根据短路逻辑， if 里 && 的第二个条件根本不会执行，所以不会有空指针异常。

当然，从防御性编程的角度，按照你的写法完全没有问题。

继续加油！：）

hhok8s

hp>门儿清了，我忽视了红黑树叶子节点NULL都是黑色的这个性质，所以
if (isRed(node.left) && isRed(node.left.left))
这个写法完全没有问题。赞的！
谢谢bobo老师。

h023-09-06

共1条回复

算法与数据结构

波波老师5年集大成之作，算法与数据结构系统学习，考试、面试、竞赛通用

2636 学习 · 1090 问题

相似问题

回答 2

回答 2

回答 1

回答 2

回答 1