BST 和 Splay 树中 1...n 键的插入操作的复杂度是多少？
What is the complexity of insertion operation for 1...n keys in BST and Splay tree?
如果要按顺序插入 n 个键 1,2,...,n，
(一)。到普通的 BST（二叉搜索树）
(b)。到八字树
每种情况 (a)、b) 的复杂性是多少？
这两种情况都是 O(log n) 吗？还是 (a) 的 O(log n) 和 (b) 的 O(M log n)？
根据维基百科 文章，平均插入时间为 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)。
如果要按顺序插入 n 个键 1,2,...,n，
(一)。到普通的 BST（二叉搜索树）
(b)。到八字树
每种情况 (a)、b) 的复杂性是多少？
这两种情况都是 O(log n) 吗？还是 (a) 的 O(log n) 和 (b) 的 O(M 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)。