红黑树实现中self.NULL与None的区别及替换影响咨询

1. self.NULL代表什么，与None有何区别？ #

self.NULL是红黑树实现里的哨兵节点，是用Node类实例化出来的特殊对象：

• 它具备Node类的所有属性（val、color、left、right），其中color被设为黑色（0），用来模拟红黑树规则里的「外部叶子节点」。
• None是Python内置的空值，表示不存在任何对象，没有任何属性。
  简单说：self.NULL是一个有属性的「空节点」，None是真正的「无对象状态」。

2. 为何代码中部分场景使用None，部分场景使用self.NULL？ #

• 用None的场景：比如Node类的parent初始值为None，这是因为节点刚创建时还未加入红黑树，没有父节点，此时用None表示「未关联到树的状态」。
• 用self.NULL的场景：红黑树要求所有真正的内部节点的左右孩子都必须是黑色外部节点。用self.NULL作为统一的哨兵，能让树的边界操作（插入找位置、颜色调整、旋转）不用额外判断是否为None，简化逻辑，避免大量空值检查。

3. 若将self.NULL替换为None，会对代码功能产生哪些影响？ #

直接替换会导致代码崩溃，核心问题包括：

• 属性访问报错：比如插入逻辑里的while x != self.NULL，如果换成x != None，当遍历到树的叶子位置时，x会变成None，但之前的if node.val < x.val已经会因为x是None触发AttributeError（None没有val属性）。
• 破坏红黑树规则：红黑树的颜色调整、旋转等操作依赖所有叶子都是黑色哨兵。用None代替后，无法满足「外部节点为黑色」的规则，后续平衡修复逻辑完全无法正常运行。
• 增加大量冗余判断：如果要兼容None，所有访问节点属性（val、color、left等）的地方都要先判断x is not None，代码会变得臃肿且容易出错。

关于x != self.NULL的逻辑解释 #

这行是红黑树插入时寻找插入位置的循环条件：

• 初始时x是树的根节点（self.root，初始值为self.NULL）。
• 循环中不断将x移动到左/右孩子，直到x等于self.NULL——也就是找到了树的「空叶子位置」，此时y就是新节点的父节点，停止循环后即可把新节点挂载到y的左/右孩子上。
• 因为self.NULL是一个Node对象，所以可以安全访问它的属性，不用担心空值报错，这就是哨兵节点的核心作用。

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