将节点插入二叉搜索树的最坏情况时间复杂度是多少？

Question

将节点插入二叉搜索树的最坏情况时间复杂度是多少？

Answer 1

如果你有一个不做任何平衡的“纯”二叉搜索树，那么插入元素的最坏情况运行时间是 Θ(n)。如果您有一个退化的二叉搜索树（其中每个节点只有一个子节点）并且您最终插入的元素最终成为最深节点的子节点，则会发生这种情况。例如，如果您尝试通过插入数字 1、2、3、...、n 来构建 BST，这种方式在每一步插入剩余数字中的最小或最大数字，您将触发这种情况.

如果您使用自平衡二叉搜索树，例如 AVL 树或红/黑树，最坏情况的运行时间是 Θ(log n)，因为这些树保证树的高度永远不会超过 Θ(log n) 并且插入的运行时间在最坏的情况下与树的高度成正比。