在平衡二叉树中搜索项目
如果我有一个平衡的二叉树，并且我想在其中搜索一个项目，那么大的oh时间复杂度会是O（n）吗？在二叉树中搜索一个项目，不管它是否平衡，会改变O（n）的大时间复杂性吗？我知道如果我们有一个平衡的BST，那么搜索一个项目就等于BST的高度so O（log n），但是普通的二叉树呢？
共有1个答案
平衡BST中的O（log n）搜索时间由两个属性促进：
- 树中的元素通过比较排列
- 树是（近似）平衡的。
如果您丢失了这些属性中的任何一个，那么您将不再获得O（log n）搜索时间。
如果您正在搜索未排序（又名不是BST）的平衡二叉树以查找特定值，那么您必须检查树中的每个节点以保证找到您要查找的值，因此它需要O（n）时间。
对于一个不平衡的树，如果您将失衡的最坏情况可视化，其中每个节点只有一个子节点，而叶子本质上是一个链表，那么这可能会有所帮助。如果您的BST完全（或大部分）不平衡，那么搜索将花费O（n）个时间，就像一个链表一样。
如果未排序的二叉树是不平衡的，那么它仍然有n个节点，并且它们仍然未排序，因此仍然需要O（n）个时间。
-
在上一节中，我们考虑构建一个二叉搜索树。正如我们所学到的，二叉搜索树的性能可以降级到 $$O(n)$$ 的操作，如 get 和 put ，如果树变得不平衡。在本节中，我们将讨论一种特殊类型的二叉搜索树，它自动确保树始终保持平衡。这棵树被称为 AVL树，以其发明人命名：G.M. Adelson-Velskii 和E.M.Landis。 AVL树实现 Map 抽象数据类型就像一个常规的二叉搜索树，唯一
-
在我们继续之前，我们来看看执行这个新的平衡因子要求的结果。我们的主张是，通过确保树总是具有 -1,0或1 的平衡因子，我们可以获得更好的操作性能的关键操作。 让我们开始思考这种平衡条件如何改变最坏情况的树。有两种可能性，一个左重树和一个右重树。 如果我们考虑高度0,1,2和3的树，Figure 2 展示了在新规则下可能的最不平衡的左重树。 Figure 2 看树中节点的总数，我们看到对于高度为0的
-
所以，我一直在研究平衡的二叉查找树。 我谷歌了一下，这是我的发现: 二叉树，其中每个节点的两个子树的深度相差 1 或更小（来自维基百科） 难道就不能把平衡二叉树定义为高度不超过ceil(log(n ^ 1)/log ^ 2)的树吗？ 从这个答案来看，提问者似乎已经问了同样的事情，但是公认的答案通过举斐波纳契树的例子拒绝了这个想法。斐波纳契树不是平衡树，对吗？我认为回答者可能会与AVL树中平衡树的定
-
现在我们已经证明保持 AVL树的平衡将是一个很大的性能改进，让我们看看如何增加过程来插入一个新的键到树。由于所有新的键作为叶节点插入到树中，并且我们知道新叶的平衡因子为零，所以刚刚插入的节点没有新的要求。但一旦添加新叶，我们必须更新其父的平衡因子。这个新叶如何影响父的平衡因子取决于叶节点是左孩子还是右孩子。如果新节点是右子节点，则父节点的平衡因子将减少1。如果新节点是左子节点，则父节点的平衡因子将
-
我刚刚学习了如何创建二进制搜索数据结构，它将用于存储字典中的数千个单词。我遇到的问题是，统计添加和删除数据需要很长时间。通常为199263毫秒或200秒，计算100000个单词。有人告诉我，拥有一棵能够自我平衡的树将提高效率，使操作更快。 我的问题是如何使我的树自动平衡以使其高效。我通过消除重复的单词来使树的高度变短，从而做了一些小小的改进。 如果有人能给我一些建议，告诉我如何使树高效，以及如何在
-
如果二叉树是平衡的，那么二叉搜索的最佳运行时间是O（log（n））。最坏的情况是，如果二叉树非常不平衡，它基本上表示一个链表。在这种情况下，二进制搜索的运行时间将为O（n）。 但是，如果树只是稍微不平衡，就像这棵树的情况一样： 如果我没记错的话，最好的情况仍然是O（log n）。但是最坏的情况是什么？