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

Question

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

寻找树中最小的项目。

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

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

对于 2，有人可以向我解释一下哪一个会有更快的 big oh time 吗？

Answer 1

Creating a list of all elements in the tree that are smaller than some value v.

嗯，在 Big O 表示法中，balanced binary search tree 和 balanced binary tree 将执行相同的操作，时间将为 O(N) ，这是线性时间复杂度。

对于Balanced Binary Search tree，我们会做一个inorder traversal并继续将所有键添加到列表中，直到我们遇到具有键v的节点（顺序遍历BST 导致键的升序）。现在最坏的情况发生在 v 是 BST 中存在的最大键时，因此，时间复杂度为 O(N).

对于一个balanced binary tree来说，不如遍历整棵树，把所有小于v的key都加到列表中。所以这里的时间复杂度也是O(N).

Answer 2

您还必须考虑时间复杂度性能的最佳、平均和最差情况，请记住 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

Finding the smallest item in the tree.

这是一个搜索操作。

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

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

Creating a list of all elements in the tree that are smaller than some value v.

这将是一个插入操作。

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

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

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

引用次数

Best, worst and average case [1]

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

Balanced Binary Tree Vs Balanced Binary Search Tree

algorithm

tree

big-o

binary-tree

binary-search-tree