链表与二叉搜索树(BST)插入时间复杂度标注差异疑问

问题解答 #

1. 你的认知没有错误 #

BST的实际指针修改操作耗时确实是O(1)，和链表插入的改指针逻辑完全一致：仅需要修改父节点和新节点的两个指针指向，不需要额外遍历或者移动其他节点。

2. 二者标注复杂度不一致的核心原因，是讨论插入操作的默认前提不同 #

• 资料标注链表插入O(1)时，有一个默认前置条件：你已经提前获取到了插入位置的前驱节点指针。这个标注是为了和数组插入做对比：数组哪怕知道插入位置，也需要移动后续O(n)个元素才能腾出空间，而链表不需要移动元素，仅改指针即可完成操作。如果是「按值查找插入位置再插入」的完整场景，链表的插入复杂度同样要算上遍历的O(n)开销。
• 资料标注BST插入O(log n)时，默认指的是从根节点开始执行完整插入流程的开销：BST的核心特性是节点有序，插入新节点必须遵守「左子树值小于根、右子树值大于根」的规则，因此查找合法插入位置是插入操作不可缺少的一环，平均情况下平衡BST的树高为log n，查找位置需要O(log n)，加上O(1)的改指针操作，整体复杂度就是O(log n)。如果脱离这个上下文，仅单独计算改指针的耗时，BST的插入同样是O(1)，但这个场景没有实际业务价值，因此几乎不会单独讨论。

内容的提问来源于stack exchange，提问作者Brendan