问平衡二叉树与平衡二叉树

EN

在时间复杂性性能方面，您还必须考虑到最佳、平均和最坏的情况，同时记住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)，而作为一种典型的二进制搜索树，O(Log N)并不保证。

引文

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

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

那么，在大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)。