Python 方法没有返回红黑树的节点对象

Question

我正在 Python 中实现红黑树。我有两个类，RedBlackTree 和 TreeNode。 __setitem__ 在下面显示的代码之外定义。

我的代码的问题是，当我尝试将键 -1 添加到我的树时，在 _put 方法中创建了一个 TreeNode 对象，但该对象没有正确返回。调用方方法 'put' 没有接收到任何对象。

该代码适用于添加键 5 和 2，但由于某些原因，无法以我在下面尝试的方式返回键为 -1 的 TreeNode 对象.查看底部的控制台输出。

我们非常感谢您提供任何帮助。谢谢

class RedBlackTree:
  def put(self, key, val):
    if self.root:
        newNode = self._put(key, val, self.root)
        print("put RECEIVED ", newNode)
        print("put has newNode, who's key is ", newNode.key, 
              " and parent's key is ", newNode.parent.key)
        self.rbInsertFixup(newNode)
    else: # there is no root
        self.root = TreeNode(key, val, parent = self.sentinal, 
                             left = self.sentinal,
                             right = self.sentinal)
        newNode = self.root
        self.rbInsertFixup(newNode)

  def _put(self, key, val, currentNode):
    if key < currentNode.key:
        if currentNode.leftChild != self.sentinal:
            self._put(key, val, currentNode.leftChild)
        else: # currentNode has no child
            newNode = TreeNode(key, val, parent = currentNode, 
            left = self.sentinal, right = self.sentinal )
            currentNode.leftChild = newNode
            print("_put RETURNS ", newNode)
            return newNode
    else: # symetric to THEN clause above, with 'left' chnaged to 'right'
    ...
class TreeNode():
  def __init__(self, key, val, 
             left = None, right = None, 
             parent = None, color = 'red'):
    self.key = key
    self.payload = val
    self.leftChild = left
    self.rightChild = right
    self.parent = parent
    self.color = color
    ...
t = RedBlackTree()
t[5] = 'five'
t[2] = 'two'
t[-1] = 'negative one'

控制台输出低于...

('_put RETURN ', <__main__.TreeNode instance at 0x106bd45a8>)
('put RECEIVED ', <__main__.TreeNode instance at 0x106bd45a8>)
("put has newNode, who's key is ", 2, " and parent's key is ", 5)
('_put RETURN ', <__main__.TreeNode instance at 0x106bd45f0>)
('put RECEIVED ', None)
Traceback (most recent call last):
  File "RB-Tree.py", line 383, in <module>
    t[-1] = 'negative one'
  File "RB-Tree.py", line 105, in __setitem__
    self.put(k, v)
  File "RB-Tree.py", line 35, in put
    print("put has newNode, who's key is ", newNode.key, " and parent's     key is ", newNode.parent.key)
AttributeError: 'NoneType' object has no attribute 'key'

`

Answer 1

Return 值未存储在此 if 子句中

if currentNode.leftChild != self.sentinal:
    self._put(key, val, currentNode.leftChild)

改为

if currentNode.leftChild != self.sentinal:
    newNode = self._put(key, val, currentNode.leftChild)
    return newNode

问题已解决。

Python 方法没有返回红黑树的节点对象

Python method is not returning an node object for red black tree

python

oop

runtime-error

red-black-tree

data-structures