java - 递归插入时是否会重建二叉搜索树？

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”的第三个方法，这次是 insert(null, 5)被调用，因此第一个 if 语句实际上被执行，并且创建了一个 Elem 类型的新对象。被返回。又名此行被执行，return new Elem(toInsert,null,null) (将此视为 return new 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