基于值的二叉搜索树复杂度
Binary Search Tree Complexity based on Values
我用 C 语言创建了一个二叉搜索树，当我测试我的树时，插入和搜索操作需要不同的时间来执行。例如，我有两种情况，插入从 1 到 10000 的随机值和插入从 1 到 10000 的排序值。当我将 1 到 10000 的随机值插入我的 BST 时，它比将 1 到 10000 的排序值插入到我的 BST.
在我的 BST 中执行搜索操作也是如此，当我搜索那些随机值时花费的时间更少，但在我的 BST 中搜索排序值时花费的时间太长。
现在，问题是时间复杂度，谁能解释一下，这是如何处理的？所有四种情况的时间复杂度是多少？
注意：插入和搜索这些排序的值几乎花费相同的时间，仍然搜索需要更长的时间！
如果不平衡树，其结构取决于插入顺序，"fully unbalanced"二叉搜索树相当于一个排序链表。
因此，操作的最坏情况时间复杂度与树的大小成线性关系，而不是平衡树中的对数关系。
例如，如果您从 1 开始插入并递增，您将得到
1
/\
2
/\
3
/\
...
其中右边"spine"是链表
使用 AVL 树。它将使您的树保持平衡，并且您将始终获得 log(n)
的搜索时间
我用 C 语言创建了一个二叉搜索树，当我测试我的树时，插入和搜索操作需要不同的时间来执行。例如，我有两种情况，插入从 1 到 10000 的随机值和插入从 1 到 10000 的排序值。当我将 1 到 10000 的随机值插入我的 BST 时，它比将 1 到 10000 的排序值插入到我的 BST.
在我的 BST 中执行搜索操作也是如此，当我搜索那些随机值时花费的时间更少，但在我的 BST 中搜索排序值时花费的时间太长。
现在，问题是时间复杂度，谁能解释一下，这是如何处理的？所有四种情况的时间复杂度是多少？
注意：插入和搜索这些排序的值几乎花费相同的时间，仍然搜索需要更长的时间！
如果不平衡树，其结构取决于插入顺序，"fully unbalanced"二叉搜索树相当于一个排序链表。
因此，操作的最坏情况时间复杂度与树的大小成线性关系，而不是平衡树中的对数关系。
例如，如果您从 1 开始插入并递增，您将得到
1
/\
2
/\
3
/\
...
其中右边"spine"是链表
使用 AVL 树。它将使您的树保持平衡，并且您将始终获得 log(n)
的搜索时间