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

Question

在bst的常规递归代码中，树的左右元素在每个递归调用中都设置了（Int.left=andt.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（元素6，5）（*表示我们在三个元素中的位置）。

   *6
   / \
  4   8

该方法将跳过第一个if-语句，并继续检查与方法参数中的当前元素相关的值5。5小于6，因此执行以下行，t.left=插入（t.left， toInert）（将其视为elem6.left=插入（元素4,5））。

    6
   / \
 *4   8

现在我们进入第二个方法调用insert，这次是insert（元素4，5）。再次跳过第一个if语句，并将4与5进行比较。5大于4，因此执行以下行，t.right=insert（t.right，toInsert）（将其视为elem4.right=insert（null，5））。

    6
   / \
  4   8
   \
    *

现在我们进入了第三个方法调用“insert”，这次调用了insert（null，5），因此第一个if语句被实际执行，并返回了Elem类型的新对象。也就是说，执行这一行时，返回新元素（toInsert，null，null）（将其视为返回新元素（5，null，null））。

    6
   / \
  4   8
   \
    *

在这一点上，调用堆栈在增长到三个调用后开始减少。回到这一行，t.right=插入（t.right， toInsert），但不是插入（t.right， toInsert），现在是new Elem（5， null， null）。所以元素5已分配给元素4的右侧。然后，执行方法的其余部分，以返回t结尾。t在这种情况下是通过方法元素4传递的Elem。

    6
   / \
 *4   8
   \
    5

回到这一行（沿着调用堆栈往下看），t.left=insert（t.left，toInsert）但是现在不是insert（t.left，toInsert），而是元素4。元素6的左边被分配给元素4。然后，执行该方法的其余部分，以return t结束t在这种情况下是通过方法元素6传递的Elem。然后，第5元素的插入就结束了。

   *6
   / \
  4   8
   \
    5