파이썬 메서드가 빨간색 검은 색 트리의 노드 객체를 반환하지 않습니다.

Question

파이썬에서 Red Black Tree를 구현 중입니다. 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

반환 값이

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

이

에 변경이 if 절에 저장되지 않습니다

문제가 해결되었습니다.