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

Question

为什么将 N 项插入空二叉搜索树 n^2 的最坏情况是大 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:

第一步:空树，插入10:

10

第 2 步:将 20 与 10 进行比较；更大，因此树变成:

10
  \
   20

第 3 步:将 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)。

当然，只有按排序顺序(从小到大或从大到小)插入时才会出现这种情况。以恰好使树平衡的顺序插入会便宜得多。