algorithm - 将 n 个数字插入二叉搜索树的复杂性

Question

我有一个问题，它说“计算将 n 个数字插入二叉搜索树的过程的紧时间复杂度”。它不表示这是否是一棵平衡树。那么，这样的问题可以给出什么答案呢？如果这是一棵平衡树，那么高度是 logn，插入 n 个数字需要 O(nlogn) 时间。但这是不平衡的，在最坏的情况下甚至可能需要 O(n²) 时间。找到将 n 个数字插入 bst 的紧时间复杂度是什么意思？我错过了什么吗？谢谢

Answer 1

即使树是平衡的，也可能是 O(n^2)。

假设您要添加一个排序的数字列表，所有数字都大于树中的最大数字。在这种情况下，所有数字都将添加到树中最右边叶子的右边 child ，因此 O(n^2)。

例如，假设您将数字 [15..115] 添加到以下树中:

数字将作为长链添加，每个节点都有一个右手子节点。对于列表的第 i 个元素，您必须遍历 ~i 个节点，这会产生 O(n^2)。

一般来说，如果你想保持插入和检索在 O(nlogn)，你需要使用 Self Balancing trees .