balancer 二叉树与 balancer 二进制搜索树

2 回答

• 2

  You also have to take into account best, average and worst case scenarios in time complexity performance, keeping in mind what the value of n represents:

  ---

  1. Balanced Binary Search Tree representation

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

  ---

  2. Binary Search Tree representation

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

  查找树中的最小项目 .

  这是一个搜索操作 .

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

  2) 最坏情况下的时间复杂度为 O(n) . 最小值为6.您可以从表示中查看根的左侧树（分支）的行为类似于链接列表 . 这是因为树是不 balancer 的 . [1]

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

  这将是一个插入操作 .

  1) 这将是 O(log n) ，因为当遍历树时它是 balancer 的，所以你不要使用't get 2)'场景 .

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

  In conclusion: balancer 二进制搜索树在所有搜索，插入和删除节点的情况下都保证 O(log n) ，而典型的BST则不然 .

  ---

  Citations

  Best, worst and average case [1]

  回复于 2024-04-26T06:47:38+08:00
• 1

  创建树中所有小于某个值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 一样好 . 所以这里的时间复杂性也是 O(N) .

  回复于 2024-04-26T06:47:38+08:00