平衡二叉树与平衡二叉搜索树

Question

对于这些操作中的每一个，平衡二叉搜索树是否会比平衡二叉树在更快的时间内完成任务？

1. 查找树中最小的项。

我认为平衡 BST 会比平衡二叉树有更快的大时间，因为您可以继续向左遍历并找到最小的项目。我认为它会是 O(log n)。

2. 创建树中小于某个值 v 的所有元素的列表。

对于 2，有人可以向我解释一下哪个会有更快的大时间吗？

Answer 1

您还必须考虑时间复杂度性能的最佳、平均和最坏情况，记住 的值n代表什么：

1. 平衡二叉搜索树表示

           25             // Level 1
        20    36          // Level 2
      10 22  30 40        // Level 3
  .. .. .. .. .. .. .. 
.. .. .. .. .. .. .. ..   // Level n

2. 二叉搜索树表示

           10           // Level 1
          9  11         // Level 2
         7 . . 20       // Level 3
        8 . . . 15 24   
       6 . . . . . . .  // Level n

查找树中最小的项。

这是一个搜索操作。

1)这里的时间复杂度是O(log n)，即使在最坏的情况下也是如此，因为树是平衡的。最小值为 10。

2)在最坏的情况下，这里的时间复杂度是O(n)。最小值为 6。您可以从表示中看出根的左树（分支）的行为类似于链表。这是因为树是不平衡的。[ 1 ]

创建树中小于某个值 v 的所有元素的列表。

这将是一个插入操作。

1)这将是O(log n)，因为当树被遍历时它是平衡的，所以你不会得到 2) 的场景。

2）这将是O(n)，因为在最坏的情况下，您的插入将类似于链接列表的插入。

结论： 平衡二叉搜索树在所有节点的搜索、插入和删除情况下都保证O(log n)，而典型的 BST 则不然。

引文

最佳、最差和平均情况 [1]