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

Question

对于每个操作，平衡二叉搜索树会比平衡二叉树更快地完成任务吗？

1. 找到树中最小的项目。

我认为平衡二叉搜索树比平衡二叉树有更快的大哦时间，因为你可以继续向左遍历并找到最小的项目。我认为这将是 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
         8 . . 20       // Level 3
        7 . . 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]

Answer 2

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

好吧，在 Big O 表示法中，

balanced binary search tree

和

balanced binary tree

都会执行相同的操作，时间将为 O(N)，这是线性时间复杂度。

对于

Balanced Binary Search tree

，我们会进行中序遍历，并不断将所有键添加到列表中，直到遇到带有键

v

的节点（

BST

的中序遍历导致键的升序排列） 。现在最坏的情况发生在

v

是

BST

中存在的最大键时，因此，时间复杂度为 O(N)。

对于

balanced binary tree

，它相当于遍历整棵树并将所有小于

v

的键添加到列表中。所以这里的时间复杂度也是O(N)。