Алгоритм вставки для дерева двоичного поиска не работает

Question

Я пытаюсь написать функцию, которая вставляет узел в двоичное дерево поиска. Я видел несколько примеров, и мне кажется, что мой алгоритм должен работать, но по какой-то причине он не тестирует.

def insert(tr, el): 
 
    """ function to insert an element into a binary search tree 
 
    following the rules of binary search trees. 
 
    
 
    return: an updated tree 
 
    precondition: assumed all elements unique 
 
    """ 
 

 
    if tr == None: 
 
     return createEyecuBST(el, None) 
 
    elif el < tr.value: 
 
     if tr.left == None: 
 
      tr.left = createEyecuBST(el, tr) 
 
      return tr 
 
     else: return insert(tr.left, el) 
 
    elif el > tr.value: 
 
     if tr.right == None: 
 
      tr.right = createEyecuBST(el, tr) 
 
      return tr 
 
     else: return insert(tr.right, el) 
 
    return None

Answer 1

Есть две линии, которые появляются проблематичной в коде:

else: return insert(tr.left, el) 

и

else: return insert(tr.right, el) 

В этих случаях ваша функция будет возвращать поддерево (или слева или справа) от tr, тогда как вы хотите, чтобы ваша функция возвращала обновленное дерево tr. Я думаю, вы должны заменить эти строки на:

else: 
    insert(tr.left, el) 
    return tr 

И аналогично для tr.right.