链表 v.s。二叉搜索树插入时间复杂度
Linked List v.s. Binary Search Tree Insertion Time Complexity
链表
一个链表的插入时间复杂度对于实际操作来说是O(1)，但是遍历到合适的位置需要O(n)的时间。大多数在线资源将链表的平均插入时间列为 O(1):
https://www.bigocheatsheet.com/
https://www.geeksforgeeks.org/time-complexities-of-different-data-structures/
BST
二叉搜索树的插入需要遍历节点，耗时O(log n)。
问题
Am I mistaken to believe that insertion in a BST also takes O(1) time for the actual operation?
类似于链表的节点，在BST中插入节点只是将当前节点的指针指向插入节点，插入节点将指向当前节点的子节点。
If my thinking is correct, why do most online resources list the average insert time for a BST to be O(log n), as opposed to O(1) like for a linked list?
好像对于链表，实际插入时间列为插入时间复杂度，但是对于BST，遍历时间列为插入时间复杂度。
二叉搜索树是有序的，它通常是平衡的（以避免O(n)最坏情况下的搜索时间） ，这意味着当您插入一个值时，必须进行一些改组以平衡树。重新平衡平均需要 O(log n) 次操作，而链表只需要在找到在节点之间插入项目的位置后更新固定数量的指针。
要插入到链表中，只需要维护链表的尾节点即可（假设是在末尾插入）。
要插入到二叉搜索树 (BST) 中，并在插入后 维护 BST，在 O(1) 中您无法做到这一点 - 因为树可能会重新平衡。这个操作不像插入链表简单
查看一些示例 here。
Linked List的插入时间实际上取决于插入的位置和Linked List的类型。
例如考虑以下情况：
- 您使用的是单链表，并且要在末尾/中间插入，您将有 运行 时间 O(n) 遍历链表直到末端节点或中间节点。
- 你正在使用双链表（有两个指针，第一个指针指向头元素，第二个指针指向最后一个元素）并且你要在最后插入，这次你仍然有 O(n) 时间复杂性，因为您需要使用第一个或第二个指针遍历到列表的中间。
- 你使用的是单链表，你打算在链表的第一个位置插入，这次你的复杂度为O(1)，因为你根本不需要遍历任何节点。双链表也是如此，插入位置在链表的末尾。
所以你可以看到在最坏的情况下链表将采用 O(n) 而不是 O(1)。
现在在 BST 的情况下，如果你的 BST 是平衡的而不是倾斜的，你可以想出 O(log n) 时间。如果您的 TREE 是倾斜的（其中每个元素都大于 prev 元素），此时您需要遍历所有节点以找到插入位置。例如考虑你的树是 1->2->4->6 并且你要插入节点 9，所以你需要访问所有节点以找到插入位置。
1
\
2
\
4
\
6 (last position after which new node going to insert)
\
9 (new insertion position for the new node)
因此您可以看到您需要访问所有节点以找到合适的位置，如果您有 n 个节点，您将有 O(n+1) => O(n) 运行 时间复杂度.
但是如果你的 BST 是平衡的而不是倾斜的，情况就会发生巨大的变化，因为每一步你都可以消除不符合条件的节点。
PS：我的意思是not comes under the condition你可以把这个当作作业！
它反映了用法。对于您实际向他们请求的操作，它是 O(1) 和 O(log n)。
使用 BST，您很可能会让它自行管理，而无需了解实施细节。也就是说，您将发出 tree.insert(value) 之类的命令或 tree.contains(value) 之类的查询。这些东西需要 O(log n)。
使用链表，您更有可能自己管理它，至少是定位。你不会发出像 list.insert(value, index) 这样的命令，除非索引非常小或者你不关心性能。您更有可能发出 insertAfter(node, newNode) 或 insertBeginning(list, newNode) 之类的命令，这些命令只需要 O(1) 时间。请注意，我从维基百科的 Linked list operations > Singly linked lists 部分中获取了这两个，该部分甚至 没有 用于在作为索引给定的特定位置插入的操作。因为在现实中，你会用使用链表的算法来管理“位置”（以节点的形式），而管理位置的时间归因于算法代替。顺便说一句，也是O(1)，例子是：
- 您正在从数组构建链表。您将通过保留一个引用最后一个节点的变量来做到这一点。要追加下一个 value/node，将其插入最后一个节点之后（确实是 O(1) 操作），并更新您的变量以引用新的最后一个节点（也是 O(1)）。
- 想象一下，你不是用线性扫描而是用哈希映射找到一个位置，直接存储对链表节点的引用。然后查找引用需要 O(1) 并在查找的节点之后插入也只需要 O(1) 时间。
如果您向我们展示了其中的一些 “大多数在线资源将链表的平均插入时间列为 O(1)”，我们可能看到他们确实显示了像 insertAfterNode 这样的插入操作，而不是 insertAtIndex. 现在编辑你在问题中包含了一些链接： 我的关于链接列表的 O(1) 插入的这些来源的想法： first one does point out that it's O(1) only if you already have something like an "iterator to the location". The second one in turn refers to the same Wikipedia section I showed above, i.e., with insertions after a given node or at the beginning of a list. The third one 是我所知道的最糟糕的编程网站，所以我并不感到惊讶他们只是说 O(1) 而没有任何进一步的信息.
换句话说，因为我喜欢现实世界的类比：如果你问我更换汽车发动机中的零件 X 需要多少钱，我可能会说 200 美元，尽管该零件只需 5 美元。因为我自己不会那样做。我会让机械师来做，我必须为他们的工作付钱。但如果你问我更换自行车上的铃铛要多少钱，我可能会说 5 美元，而铃铛的价格是 5 美元。因为我会自己更换。
链表
一个链表的插入时间复杂度对于实际操作来说是O(1)，但是遍历到合适的位置需要O(n)的时间。大多数在线资源将链表的平均插入时间列为 O(1):
https://www.bigocheatsheet.com/
https://www.geeksforgeeks.org/time-complexities-of-different-data-structures/
BST
二叉搜索树的插入需要遍历节点，耗时O(log n)。
问题
Am I mistaken to believe that insertion in a BST also takes O(1) time for the actual operation?
类似于链表的节点，在BST中插入节点只是将当前节点的指针指向插入节点，插入节点将指向当前节点的子节点。
If my thinking is correct, why do most online resources list the average insert time for a BST to be O(log n), as opposed to O(1) like for a linked list?
好像对于链表，实际插入时间列为插入时间复杂度，但是对于BST，遍历时间列为插入时间复杂度。
二叉搜索树是有序的，它通常是平衡的（以避免O(n)最坏情况下的搜索时间） ，这意味着当您插入一个值时，必须进行一些改组以平衡树。重新平衡平均需要 O(log n) 次操作，而链表只需要在找到在节点之间插入项目的位置后更新固定数量的指针。
要插入到链表中，只需要维护链表的尾节点即可（假设是在末尾插入）。
要插入到二叉搜索树 (BST) 中，并在插入后 维护 BST，在 O(1) 中您无法做到这一点 - 因为树可能会重新平衡。这个操作不像插入链表简单
查看一些示例 here。
Linked List的插入时间实际上取决于插入的位置和Linked List的类型。
例如考虑以下情况：
- 您使用的是单链表，并且要在末尾/中间插入，您将有 运行 时间 O(n) 遍历链表直到末端节点或中间节点。
- 你正在使用双链表（有两个指针，第一个指针指向头元素，第二个指针指向最后一个元素）并且你要在最后插入，这次你仍然有 O(n) 时间复杂性，因为您需要使用第一个或第二个指针遍历到列表的中间。
- 你使用的是单链表，你打算在链表的第一个位置插入，这次你的复杂度为O(1)，因为你根本不需要遍历任何节点。双链表也是如此，插入位置在链表的末尾。
所以你可以看到在最坏的情况下链表将采用 O(n) 而不是 O(1)。
现在在 BST 的情况下，如果你的 BST 是平衡的而不是倾斜的，你可以想出 O(log n) 时间。如果您的 TREE 是倾斜的（其中每个元素都大于 prev 元素），此时您需要遍历所有节点以找到插入位置。例如考虑你的树是 1->2->4->6 并且你要插入节点 9，所以你需要访问所有节点以找到插入位置。
1
\
2
\
4
\
6 (last position after which new node going to insert)
\
9 (new insertion position for the new node)
因此您可以看到您需要访问所有节点以找到合适的位置，如果您有 n 个节点，您将有 O(n+1) => O(n) 运行 时间复杂度.
但是如果你的 BST 是平衡的而不是倾斜的，情况就会发生巨大的变化，因为每一步你都可以消除不符合条件的节点。
PS：我的意思是not comes under the condition你可以把这个当作作业！
它反映了用法。对于您实际向他们请求的操作，它是 O(1) 和 O(log n)。
使用 BST，您很可能会让它自行管理，而无需了解实施细节。也就是说，您将发出 tree.insert(value) 之类的命令或 tree.contains(value) 之类的查询。这些东西需要 O(log n)。
使用链表，您更有可能自己管理它，至少是定位。你不会发出像 list.insert(value, index) 这样的命令，除非索引非常小或者你不关心性能。您更有可能发出 insertAfter(node, newNode) 或 insertBeginning(list, newNode) 之类的命令，这些命令只需要 O(1) 时间。请注意，我从维基百科的 Linked list operations > Singly linked lists 部分中获取了这两个，该部分甚至 没有 用于在作为索引给定的特定位置插入的操作。因为在现实中，你会用使用链表的算法来管理“位置”（以节点的形式），而管理位置的时间归因于算法代替。顺便说一句，也是O(1)，例子是：
- 您正在从数组构建链表。您将通过保留一个引用最后一个节点的变量来做到这一点。要追加下一个 value/node，将其插入最后一个节点之后（确实是 O(1) 操作），并更新您的变量以引用新的最后一个节点（也是 O(1)）。
- 想象一下，你不是用线性扫描而是用哈希映射找到一个位置，直接存储对链表节点的引用。然后查找引用需要 O(1) 并在查找的节点之后插入也只需要 O(1) 时间。
如果您向我们展示了其中的一些 “大多数在线资源将链表的平均插入时间列为 O(1)”，我们可能看到他们确实显示了像 现在编辑你在问题中包含了一些链接： 我的关于链接列表的 O(1) 插入的这些来源的想法： first one does point out that it's O(1) only if you already have something like an "iterator to the location". The second one in turn refers to the same Wikipedia section I showed above, i.e., with insertions after a given node or at the beginning of a list. The third one 是我所知道的最糟糕的编程网站，所以我并不感到惊讶他们只是说 O(1) 而没有任何进一步的信息.insertAfterNode 这样的插入操作，而不是 insertAtIndex.
换句话说，因为我喜欢现实世界的类比：如果你问我更换汽车发动机中的零件 X 需要多少钱，我可能会说 200 美元，尽管该零件只需 5 美元。因为我自己不会那样做。我会让机械师来做，我必须为他们的工作付钱。但如果你问我更换自行车上的铃铛要多少钱，我可能会说 5 美元，而铃铛的价格是 5 美元。因为我会自己更换。