二叉搜索树的时间效率
对于插入二叉查找树的时间效率，
我知道插入的最佳/平均情况是O（log n），其中最坏的情况是O（n）。
我想知道的是，除了实现AVL（平衡BST）之外，是否还有任何方法可以确保在插入时始终具有最佳/平均情况？
谢谢
共有1个答案
如果不平衡二进制搜索树，就不能保证日志n的复杂性。在搜索/插入/删除时，您必须在树中导航，以便将自己定位到正确的位置并执行操作。关键的问题是——在正确的位置需要多少步骤？如果BST是平衡的，您可以期望在级别上平均有2个节点。这进一步意味着，如果树具有k级别（k称为树的高度），则树中的预期节点数为1 2 4。。2^（k-1）=2^k-1=n，这给出了从根导航到叶所需的平均步骤数。
话虽如此，平衡BST有多种实现。您提到了AVL，另一种非常流行的是红黑树，例如在C中用于实现std：：map，在Java中用于实现TreeMap。
最坏的情况是O（n），当您不平衡BST并且您的树退化为链表时可能会发生。很明显，为了定位在列表的末尾（这是最坏的情况），您必须遍历整个列表，这需要n步骤。
-
我很难按我教授想要的格式打印出一个二叉搜索树。 他的格式是这样的： 我的代码：
-
树的特征和定义 树(Tree)是元素的集合。我们先以比较直观的方式介绍树。下面的数据结构是一个树： 树有多个节点(node)，用以储存元素。某些节点之间存在一定的关系，用连线表示，连线称为边(edge)。边的上端节点称为父节点，下端称为子节点。树像是一个不断分叉的树根。 每个节点可以有多个子节点(children)，而该节点是相应子节点的父节点(parent)。比如说，3,5是6的子节点，6是3,
-
我已经知道，如果您尝试查找具有特定键的项目，最坏情况下的运行时间是O（n），。如果您试图搜索特定的数据项（您不知道该键），那么最坏情况下的运行时间是O（n）。然而，如果键和数据都是整数，输入项在插入之前被随机置乱，会怎么样。最糟糕的运行时间还会保持不变吗？
-
我正在学习C++语言，我正在尝试编写BST，但是出了问题。我尝试添加元素到空树，根是NULL，但添加元素后，根仍然是NULL，尽管添加成功了（我在调试模式下看到，节点设置为tmp）。我不知道为什么会这样。
-
编写一个函数，如果给定的二叉搜索树包含给定的值，则返回1，否则返回0。 例如,对于以下树： N1（值：1,左：null,右：null) n2（值：2,左:n1,右:n3) N3（值：3,左：null,右：null) 对contains(&n2,3）的调用应返回1，因为根位于n2的树包含编号3。 函数应该返回1，然而，它返回0或者根本不返回。
-
如果二叉树是平衡的，那么二叉搜索的最佳运行时间是O（log（n））。最坏的情况是，如果二叉树非常不平衡，它基本上表示一个链表。在这种情况下，二进制搜索的运行时间将为O（n）。 但是，如果树只是稍微不平衡，就像这棵树的情况一样： 如果我没记错的话，最好的情况仍然是O（log n）。但是最坏的情况是什么？