python - None 对象的返回值

Question

我已经在我的 AVL 树实现中添加了方法。

class Node:    
    def __init__(self, data, left = None, right = None, height = -1):
        self.data = data
        self.left = left
        self.right = right
        self.height = height
    def addNode(self, data):
        if self.data > data:
            '''Adding to left subtree'''
            if self.left is None:
                self.left = Node(data)
            else:
                self.left.addNode(data)
                if ( abs(self.right.height - self.left.height) == 2):
                    ''' Then we need to balance a subtree''' 
                    print("Rebalancing after inserting", data)
                    if (data < self.left.data):
                        self.rotateLeft()
                    else:
                        self.doubleRotateLeft()

        elif self.data < data:
            '''Adding to right subtree'''
            if self.right is None:
                self.right = Node(data)
            else:
                self.right.addNode(data)
                if ( abs(self.right.height - self.left.height) == 2):
                    ''' Then we need to balance a subtree'''
                    print("Rebalancing after inserting", data)
                    if (data < self.right.data):
                        self.rotateRight()
                    else:
                        self.doubleRotateRight()

但是当我尝试做的时候

self.right.height

如果 self 没有得到正确的对象，那么它不会返回高度，即使默认值为 -1。我该如何解决？我正在尝试尽可能减少此方法中的重复代码

Answer 1

如果 self.right 设置为 None 你不能使用 self.right.height，不行。如果该表达式必须有效，请不要使用 None。请改用定义该属性的哨兵。

哨兵可以只是一个没有值也没有子节点的自定义类。您可以像 None 一样将其设为单例:

class Sentinel(object):
    value = left = right = None
    height = -1

sentinel = Sentinel()

class Node:    
    def __init__(self, data, left=sentinel, right=sentinel, height=-1):
        # ...

然后在您的代码中测试 is sentinel 而不是 is None。通过使用 sentinel 作为 left 和 right 关键字参数的默认值，self.left.height 和 self.right.height 将始终有效(前提是 self 是 Node 的实例)。

不要忘记在每次创建新节点时增加高度。

您可以通过使用本地引用稍微简化您的 addNone() 方法:

def addNode(self, data):
    if self.data == data: return
    left = self.data > data
    testnode = self.left if left else self.right
    if testnode is sentinel:
        node = Node(data)
        setattr(self, 'left' if left else 'right', node)
    else:
        testnode.addNode(data)
        if abs(self.right.height - self.left.height) == 2:
            if data < testnode.data:
                rotation = self.rotateLeft if left else self.rotateRight
            else:
                rotation = self.doubleRotateLeft if left else self.doubleRotateRight
            rotation()