向二叉查找树插入n个数字的复杂性
我有一个问题，它说“计算在二元搜索树中插入n个数字的过程的时间复杂度”。它并不表示这是否是一个平衡树。那么，对于这样一个问题，我们能给出什么答案呢？如果这是一个平衡树，那么高度是logn，插入n个数字需要O（nlogn）时间。但这是不平衡的，在最坏的情况下甚至需要O（n2）时间。在bst中插入n个数字的时间复杂度很高，这意味着什么？我错过什么了吗？谢谢
共有2个答案
wiki所说的是正确的。由于给定的树是BST，因此不需要搜索整个树，只需将要插入的元素与树/子树的根进行比较即可获得该元素的适当节点。这需要O（log2n）。一旦我们有了这样的节点，我们就可以在那里插入键bht，之后需要将右aub-tree中的所有元素向右推送，这样BST的搜索属性就不会受到侵犯。如果要插入的地方是最后一个，我们需要担心第二个过程。如果注意到这个过程可能需要O（n），最坏的情况！。因此，在BST中插入元素的总体最坏情况复杂性将是O（n）。谢谢！
即使树是平衡的，它也可能是O（n^2）。
假设您要添加一个排序的数字列表，这些数字都大于树中最大的数字。在这种情况下，所有数字都将添加到树中最右边叶子的右子节点，因此为O（n^2）。
例如，假设您将数字[15...115]添加到以下树中：
这些数字将作为一条长链添加，每个节点都有一个右手边的子节点。对于列表的第i个元素，您必须遍历~i个节点，产生O（n^2）。
一般来说，如果您想将插入和检索保持在O（nlogn），您需要使用自平衡树。
-
几天来，我一直在使用二进制搜索树实现，我已经到了知道我的根正在通过使用我的“插入（）”来填充的地步（当我使用Eclipse进行调试时，我可以看到这一点）。为什么我的其他节点不会被添加到树中？ 这是我的BST课程： 这是我的Main（），最终我想在控制台中打印我的BST值，但首先我知道它们需要添加到树中： 公共类Main{
-
主要内容：什么是二叉排序树？,使用二叉排序树查找关键字,二叉排序树中插入关键字,二叉排序树中删除关键字,总结前几节介绍的都是有关静态 查找表的相关知识，从本节开始介绍另外一种查找表—— 动态查找表。 动态查找表中做查找操作时，若查找成功可以对其进行删除；如果查找失败，即表中无该关键字，可以将该关键字插入到表中。 动态查找表的表示方式有多种，本节介绍一种使用树结构表示动态查找表的实现方法—— 二叉排序树（又称为 “二叉查找树”）。 什么是二叉排序树？ 二叉排序树要么是空 二叉树，要么具有如下特点：
-
我正在努力实现二叉搜索树。完成实现所需的功能之一是重新平衡功能。 根据规范，该功能的工作方式如下: rebalance（） 方法应创建一个平衡树，从而将偏度降低为零。平衡树是指在整个树中，左子树和右子树的大小相差不超过1（即，每个子树也是平衡的）。 为了平衡树，rebalance（） 方法应反复将根值移动到较小的子树，并将最小/最大值从较大的子树移动到根，直到树平衡。然后，它应该以递归方式平衡两个
-
我们已经看到了两种不同的方法来获取集合中的键值对。回想一下，这些集合实现了 map 抽象数据类型。我们讨论的 map ADT 的两个实现是在列表和哈希表上的二分搜索。在本节中，我们将研究二叉查找树作为从键映射到值的另一种方法。 在这种情况下，我们对树中项的确切位置不感兴趣，但我们有兴趣使用二叉树结构来提供高效的搜索。
-
二叉搜索树（BST）和二叉树（BT）中的插入有什么区别？我知道，在BST中，您将新节点的值与根进行比较，如果较小，则添加到其左侧，如果较大，则将其添加到根的右侧。BT的程序是否相同？如果没有，插入和移除的步骤是什么？
-
我最近完成了一个项目的二进制搜索树，我正在工作。很顺利，我学到了很多。然而，现在我需要实现一个常规的二叉树...出于某种原因，这让我难倒了。 我正在寻找一种方法来做我的InsertNode功能... 通常在BST中，您只需检查数据 有谁能帮我实现一个函数，只需将一个新节点从左到右不按特定顺序添加到二叉树中？ 以下是我的BST插页：