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

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

Answer 1

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

哨兵可以只是一个自定义 class，没有值也没有子节点。您可以像 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()

None 对象的返回值

Returning value of None object

python

oop

algorithm

methods

avl-tree