二叉搜索树的运行时间复杂性
我已经知道，如果您尝试查找具有特定键的项目，最坏情况下的运行时间是O（n），n是节点数。如果您尝试按键的顺序打印所有数据项，则最坏情况下的运行时间是O（n）。如果您试图搜索特定的数据项（您不知道该键），那么最坏情况下的运行时间是O（n）。然而，如果键和数据都是整数，输入项在插入之前被随机置乱，会怎么样。最糟糕的运行时间还会保持不变吗？
共有2个答案
您可能无法更改正常BST的最坏情况运行时间，但是，如果您将输入随机化（在少于O（log n）的时间内，如果您的目标是O（log n）总体），那么发生最坏情况的可能性非常小。请参见此处的数学分析。
如果您对保证O（log n）时间感兴趣，您可以使用平衡BST，如Red Black Trees等。但是，打印时间仍然是O（n），因为您仍然需要访问每个节点才能打印它。
在最坏的情况下，是的。随机构建的具有n个节点的BST有一个2-1！由于n的大小很合理，但仍有可能退化，因此极为罕见。在这种情况下，查找可能需要花费Θ（n）时间，因为搜索可能需要一直向下搜索到最深的叶子。
但是，根据预期，树的高度将为Θ（log n），因此查找将花费预期的O（log n）时间。
顺便说一下，打印树的时间与树的形状无关。它总是θ（n）。
希望这有帮助！
-
假设BST的高度是h。如果我们要删除一个有两个子节点的节点，那么该过程的时间复杂度是多少。 我知道在普通的二叉树中，删除的时间复杂度是O（h）；O（n）最坏情况和O（logn）最好情况。但是由于我们用它的右子树的最小节点替换删除节点的键，因此需要更多时间来找到最小键。 那么，有人知道如何解释这种情况下的时间复杂性吗？
-
如果二叉树是平衡的，那么二叉搜索的最佳运行时间是O（log（n））。最坏的情况是，如果二叉树非常不平衡，它基本上表示一个链表。在这种情况下，二进制搜索的运行时间将为O（n）。 但是，如果树只是稍微不平衡，就像这棵树的情况一样： 如果我没记错的话，最好的情况仍然是O（log n）。但是最坏的情况是什么？
-
二叉树上广度优先搜索的空间复杂度是多少？因为它一次只存储一个级别，我不认为它会是O（n）。
-
对于插入二叉查找树的时间效率， 我知道插入的最佳/平均情况是O（log n），其中最坏的情况是O（n）。 我想知道的是，除了实现AVL（平衡BST）之外，是否还有任何方法可以确保在插入时始终具有最佳/平均情况？ 谢谢
-
我很难按我教授想要的格式打印出一个二叉搜索树。 他的格式是这样的： 我的代码：
-
树的特征和定义 树(Tree)是元素的集合。我们先以比较直观的方式介绍树。下面的数据结构是一个树： 树有多个节点(node)，用以储存元素。某些节点之间存在一定的关系，用连线表示，连线称为边(edge)。边的上端节点称为父节点，下端称为子节点。树像是一个不断分叉的树根。 每个节点可以有多个子节点(children)，而该节点是相应子节点的父节点(parent)。比如说，3,5是6的子节点，6是3,