我用C语言创建了一个二叉搜索树,当我测试我的树时,插入和搜索操作需要不同的时间来执行。例如,我有两种情况,插入从 1 到 10000 的随机值和插入从 1 到 10000 的排序值。当我将 1 到 10000 的随机值插入到 BST 中时,它比将 1 到 10000 的排序值插入到 BST 中花费的时间更少。我的 BST。
对于在 BST 中执行的搜索操作也是如此,当我搜索这些随机值时,它花费的时间更少,但在我的 BST 中搜索排序值时花费的时间太长。
现在的问题是时间复杂度,谁能解释一下,这是如何处理的?所有四种情况的时间复杂度是多少?
注意:插入和搜索这些排序值几乎花费相同的时间,但搜索需要更长的时间!
最佳答案
如果不平衡树,它的结构取决于插入顺序,“完全不平衡”的二叉搜索树就相当于一个排序链表。
因此,操作的最坏情况时间复杂度与树的大小呈线性关系,而不是像在平衡树中那样呈对数关系。
例如,如果您从 1 开始插入并递增,您最终会得到
1
/\
2
/\
3
/\
...
其中右侧的“spine”是一个链接列表。
关于c - 基于值的二叉搜索树复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53634659/