在递归插入过程中重构二叉搜索树吗？

Question

在bst的常规递归代码中，树的左右元素在每次递归调用中都设置（在t.left =和t.right =中）。 这不是再构建树吗？

将存储对前一个节点的引用，然后将新节点添加到左侧还是右侧（取决于值）还是我在此处丢失了某些东西？谢谢！

 public Elem insert (Elem t, int toInsert) 
     { 
     if (t == null) 
      return new Elem(toInsert,null,null); 
     else { 
      if (toInsert < t.value) 
      t.left = insert(t.left, toInsert); 
      else 
      t.right = insert(t.right,toInsert); 
      return t; 
     } 
    } 

要插入一个新元素，代码将每个元素或子树分配为左侧和右侧。我的问题是，这不是一个开销？要插入链表，我们只需导航到最后一个节点并在那里执行链接。在这里，我们对每个插入的树进行链接。有没有其他方法可以避免这种情况？

Answer 1

它不是重建树，而是通过递归调用遍历树来到树中的叶（空点），以便新元素可以添加到那里。例如，考虑这个BST，

6 
/\ 
    4 8 

而让你叫insert(element 6, 5)（*标志着我们在哪里，而通过三个遍历）。

*6 
/\ 
    4 8 

的方法，将通过所述第一if语句跳过，然后继续相对于检查的5值来在所述方法中放慢参数的当前元素。 5小于6，因此执行以下行，t.left = insert(t.left, toInsert)（将此视为elem6.left = insert（element 4,5））。

6 
/\ 
*4 8 

现在，我们对insert第二个方法调用，此时insert(element 4, 5)。第一个if语句再次被跳过，4与5进行比较。5大于4，因此执行以下行，t.right = insert(t.right,toInsert)（将此视为elem4.right = insert（null，5））。

6 
/\ 
    4 8 
    \ 
    * 

现在，我们在“插入”的第三个方法调用，此时insert(null, 5)被称为所以第一个if语句实际执行并返回Elem类型的新对象。又行这一行，return new Elem(toInsert,null,null)（认为这是返回新的Elem（5，null，null））。

6 
/\ 
    4 8 
    \ 
    * 

此时调用堆栈已经增长到三次调用后开始减少。回到这一行，t.right = insert(t.right,toInsert)，而不是insert(t.right, toInsert)，现在是new Elem(5, null, null)。因此元素5已被分配给元素4的右侧。然后，执行其余的方法，结束于return t。 t在这种情况下是通过该方法通过Elem，元件4

6 
/\ 
*4 8 
    \ 
    5 

回到这条线（下降调用栈），t.left = insert(t.left, toInsert)但不是insert(t.left, toInsert)，它现在是元素4.因此元素的左侧6已被分配给元素4.然后，执行该方法的其余部分，结束于return t。 t在这种情况下是Elem通过方法元素6.然后元素5的插入已结束。

*6 
/\ 
    4 8 
    \ 
    5