Pythonメソッドが赤い黒いツリーのノードオブジェクトを返さない

Question

私はPythonでRed Black Treeを実装しています。私は2つのクラス、RedBlackTreeとTreeNodeを持っています。 __setitem__は、以下に示すコードの外で定義されています。

私のコードの問題は、-1というキーをツリーに追加しようとすると、_putメソッド内にTreeNodeオブジェクトが作成されますが、オブジェクトが正しく返されないということです。呼び出し側メソッド 'put'はオブジェクトを受け取りません。

コードは、キー5と2を追加するために動作しますが、何らかの理由でそのキーTreeNodeオブジェクトは、-1私は以下しようとしてきた方法で返すことができないです。一番下のコンソール出力を参照してください。

私たちのアドバイスをいただければ幸いです。ありがとうござい以下

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

戻り値は、このif句

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

に格納されていない

にそれを変更

問題を解決しました。