递归插入时是否重构二叉搜索树？

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 )).

现在我们正在进行 'insert' 的第三次方法调用，这次调用 insert(null, 5) 所以第一个 if 语句实际上被执行并且一个新的类型 Elem 的对象是 returned。又名执行此行，return new Elem(toInsert,null,null)（将其视为 return new Elem(5, null, null)）。

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

回到这一行（沿着调用堆栈向下），t.left = insert(t.left, toInsert) 但现在是元素 4 而不是 insert(t.left, toInsert)。所以元素 6 的左边已分配给元素 4。然后，方法的其余部分被执行，以 return t 结束。 t 在本例中是通过方法传递的 Elem，元素 6。然后元素 5 的插入结束。

递归插入时是否重构二叉搜索树？

Is binary search tree reconstructed during recursive insertion?

java

recursion

binary-tree

insert

binary-search-tree