无对象的返回值

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的一个实例)。

但是，不要忘记每次创建新节点时都要增加height。

您可以通过使用本地引用来稍微简化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()