c - 基于值的二叉搜索树复杂性

Question

我用C语言创建了一个二叉搜索树，当我测试我的树时，插入和搜索操作需要不同的时间来执行。例如，我有两种情况，插入从 1 到 10000 的随机值和插入从 1 到 10000 的排序值。当我将 1 到 10000 的随机值插入到 BST 中时，它比将 1 到 10000 的排序值插入到 BST 中花费的时间更少。我的 BST。
对于在 BST 中执行的搜索操作也是如此，当我搜索这些随机值时，它花费的时间更少，但在我的 BST 中搜索排序值时花费的时间太长。现在的问题是时间复杂度，谁能解释一下，这是如何处理的？所有四种情况的时间复杂度是多少？

注意:插入和搜索这些排序值几乎花费相同的时间，但搜索需要更长的时间!

Answer 1

如果不平衡树，它的结构取决于插入顺序，“完全不平衡”的二叉搜索树就相当于一个排序链表。
因此，操作的最坏情况时间复杂度与树的大小呈线性关系，而不是像在平衡树中那样呈对数关系。

例如，如果您从 1 开始插入并递增，您最终会得到

 1
/\
  2
  /\
    3
    /\
     ...

其中右侧的“spine”是一个链接列表。