Найти родителя в двоичном дереве поиска?

Question

Я хочу найти родителя для узла с определенным значением в BST. У моего класса node есть элемент атрибута (например, значение/ключ), слева и справа.

Идея найти родителей, как это:
1) Если значение (ключ) не существует, не возвращать None, None
2) Если корень равен значению (ключ) затем возвращают None , корень
3) Else найти значение (ключ) и возврата (пар, узел), где пар является родителем и узел

Моя функция выглядит следующим образом:

def findpar(self,key): 
    if not self._exists(key): 
     return None,None 
    elif self.root.item==key: 
     return None, self.root 
    p=self.root 
    found=False 
    while not found: 
     if p.left.item==key: 
      return p, p.left 
      found=True 
     elif p.right.item==key: 
      return p, p.right 
      found=True 
     elif p.item<key: 
      p=p.left 
     elif p.item>key: 
      p=p.right 

Как обрабатывать вопрос когда p.left или p.right - нет?

Answer 1

Поскольку ваш код в настоящее время работает, невозможно, чтобы вы обращались к левому или правому ребенку None. Это происходит потому, что ваш код начинается с

if not self._exists(key): 
    return None,None 

Так key должен существовать, и если оно должно существовать, оно должно существовать на пути поиска.

Следует отметить, что вы эффективно выполняете поиск дважды, хотя это и не так эффективно. Вместо этого вы можете попробовать что-то вроде этого:

def findpar(self,key): 
    parent, node = None, self.root 
    while True: 
     if node is None: 
      return (None, None) 

     if node.item == key: 
      return (parent, node) 

     parent, node = node, node.left if key < node.item else node, node.right