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

Question

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

（一个）。到正常的 BST（二叉搜索树）

(b)。到张开树

在每种情况下 (a), b) 的复杂性是多少？

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

Answer 1

根据 Wikipedia Splay 树的文章，平均插入时间是 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 的右子项。当你去插入时5，它必须再次查看前四项。每次插入都必须查看所有先前的项目。插入 n 项时的比较总数将为(n*(n-1))/2，即 O(n^2)。

如果您使用的是自平衡二叉搜索树，则插入是 O(log n)，所有项目的插入将需要 O(n log n)。