binary-tree - 将 N 项插入一个空的二叉搜索树

Question

为什么将 N 项插入空二叉搜索树 n^2 的最坏情况是 big-O？没有余额检查。

Answer 1

每一项都是O(n)，有n项。即使每个项目的 O(n) 是“不断增加”的 n，您仍然会得到 0 + 1 + 2 + 3 ... (n-1) 即 n(n-1)/2 = O( n^2)。

换句话说，假设我们要添加 10、20、30、40：

第 1 步：空树，插入 10：

10

第二步：比较20和10；更大，因此树变为：

10
  \
   20

第三步：比较30和10；更大，所以用 20 向下移动到节点。将 30 与 20 进行比较；更大，因此树变为：

10
  \
   20
     \
      30

第4步：比较40和10；更大，所以用 20 向下移动到节点。比较 40 和 20；更大，所以向下移动到具有 30 的节点。将 40 与 30 进行比较；更大，因此树变为：

10
  \
   20
     \
      30
        \
         40

请注意我们每次如何获得更多比较 - 所以第一个元素需要 0 个比较，第二个需要 1，第三个需要 2 等等 - 总和为 n(n-1)。

当然，仅当您按排序顺序（从小到大或从大到小）插入时才会出现这种情况。以恰好平衡树的顺序插入会便宜得多。

Answer 2

在最坏的情况下，您的 BST 是一个列表，并且将 N 个项目插入到空的末尾是 O(n^2)。