红黑树实现中self.null和none的区别

Question

我不明白红黑树实现中的部分代码，特别是

self.null

的使用。您能解释一下

self.null

代表什么以及它与

None

有何不同吗？为什么有些地方用

None

，而另一些地方用

self.null

？如果我将

self.null

替换为

None

，这会对代码的功能产生什么影响？

class Node():
    def __init__(self,val):
        self.val = val                                   # Value of Node
        self.parent = None                               # Parent of Node
        self.left = None                                 # Left Child of Node
        self.right = None                                # Right Child of Node
        self.color = 1                                   # Red Node as new node is always inserted as Red Node

# Define R-B Tree
class RBTree():
    def __init__(self):
        self.NULL = Node ( 0 )
        self.NULL.color = 0
        self.NULL.left = None
        self.NULL.right = None
        self.root = self.NULL


    # Insert New Node
    def insertNode(self, key):
        node = Node(key)
        node.parent = None
        node.val = key
        node.left = self.NULL
        node.right = self.NULL
        node.color = 1                                   # Set root colour as Red

        y = None
        x = self.root

        while x != self.NULL :                           # Find position for new node
            y = x
            if node.val < x.val :
                x = x.left
            else :
                x = x.right

我试图理解 self.null 和 none 之间的区别，但我做不到。尤其是这一行x！ self.null

Answer 1

Self.NULL

被称为“哨兵节点”。它是一个实际的

Node

对象，用于代替树中缺少节点的所有位置的

None

或

null

值。

这在红黑树中常用来简化代码。代码更简单，因为您可以检查哨兵节点的颜色（空值是黑色），而无需先测试该节点是否存在。如果

if node == None

检查本来需要的内容，这会删除很多内容。