我有一个问题，它说“计算将 n 个数字插入二叉搜索树的过程的时间复杂度”。它并不表示这是否是平衡树。那么，这样的问题能给出什么答案呢？如果这是一棵平衡树，则高度为 logn，插入 n 个数字需要 O(nlogn) 时间。但这是不平衡的，在最坏的情况下甚至可能需要 O(n 2 ) 时间。找到将 n 个数字插入 bst 的时间复杂度是什么意思？我错过了什么吗？谢谢
问问题
24024 次
2 回答
8
即使树是平衡的，它也可能是 O(n^2)。
假设您要添加一个排序的数字列表，所有数字都大于树中的最大数字。在这种情况下，所有数字都将添加到树中最右边叶子的右孩子，因此 O(n^2)。
例如，假设您将数字 [15..115] 添加到以下树中：
这些数字将被添加为一条长链，每个节点都有一个右手子节点。对于列表的第 i 个元素，您必须遍历 ~i 个节点，这会产生 O(n^2)。
一般来说，如果您想将插入和检索保持在 O(nlogn)，则需要使用自平衡树。
于 2013-03-10T12:53:17.890 回答
1
维基说的是正确的。由于给定的树是一棵 BST，所以不需要搜索整个树，只需将要插入的元素与树/子树的根进行比较，就可以获得第一个元素的适当节点。这需要 O(log2n)。一旦我们有了这样一个节点，我们就可以在其中插入密钥，然后需要将正确的 aub-tree 中的所有元素向右推，这样 BST 的搜索属性就不会受到侵犯。如果要插入的位置是最后一个，我们需要担心第二个过程。如果注意此过程可能需要 O(n)，最坏的情况！因此，在 BST 中插入元素的总体最坏情况复杂度为 O(n)。谢谢！
于 2017-01-04T08:55:49.413 回答