algorithm - BST 和 Splay 树中 1...n 键的插入操作的复杂度是多少？

Question

如果 n 个键 1,2,…,n 被按顺序插入，

(一)。到普通的 BST(二叉搜索树)

(乙)。到一棵八字树

每种情况 (a)、b) 的复杂度是多少？

这两种情况都是 O(log n) 吗？还是 (a) 的 O(log n) 和 (b) 的 O(M log n)？

Answer 1

根据维基百科Splay tree article，平均插入时间为 O(log n)，最坏情况为 O(log n)。因此，将所有项目插入 Splay 树的预期时间为 O(n log n)。

二叉搜索树的情况取决于您使用的是哪种 BST。对于原始 BST，按顺序插入项是最坏的情况，因为它会创建退化树——链表。这是每次插入的 O(n)(其中 n 是树中的项目数)。所以插入所有项目需要 O(n^2)。

插入退化树的时间复杂度为 O(n)，因为树本质上是一个链表。按顺序插入数字 [1, 2, 3] 后，您的树如下所示:

1
 \
  2
   \
    3

如果您随后想要插入 4，则代码必须先查看每个现有项 1、2 和 3，然后再将 4 作为 3 的右 child 添加。当您去插入5，它又要看前面的四项。每次插入都必须查看所有先前的项目。插入 n 项时的总比较次数将为 (n*(n-1))/2，即 O(n^2)。

如果您使用的是自平衡二叉搜索树，则插入的时间复杂度为 O(log n)，而插入所有项的时间复杂度为 O(n log n)。