data-structures - 这个平衡 BST 的复杂性是什么？

Question

我在一次采访中被问到这个问题，我很想知道正确的解释是什么？

考虑以下高度平衡 BST，其中Balance factor = Height of left subtree - Height of right subtree& 可接受的平衡因子为 0、1、-1、2 和 -2。在这种高度平衡的 BST 中搜索元素需要多长时间？解释。

我说的是，即使它的高度因子2不是1标准 Balance BST 定义中的，但操作仍然应该是logN复杂度顺序，（其中 N 是树中元素的数量）因为当 N 很大时如果高度因子为 2 或 1，则差别不大。

如果有人能告诉我这里的正确答案将是有帮助的:)

标签： data-structuresbinary-treebinary-search-treeavl-treered-black-tree

Answer 1

我们可以用数学方法解决这个问题：

定义最坏情况

现在，在任何Binary Tree情况下，时间复杂度searching是 的高度在O(h)哪里。 现在，对于最坏的情况，我们想要找到最大高度。hBinary Tree

在简单的情况下，Binary Search Tree节点上没有平衡因子条件，这个最大高度可以是n或n+1 （取决于约定是单个节点树的高度是 1 还是 0） ，其中n是节点数。

因此，我们可以这么说given number of nodes, worst case is maximum height。

有趣的是，我们也可以这样说given height of a tree, the worst case is minimum nodes。即使对于这样的最小节点数，我们也可能必须遍历 height 的树h，我们也必须这样做以获得最大节点数。

因此，直觉应该清楚的是Given Height of Tree, the worst case is minimum number of nodes.

将此概念应用于二叉搜索树

1. 让我们尝试构建高度的二叉搜索树H，使树中的节点数最少。

在这里，我们将利用二叉树是递归数据结构的事实（二叉树可以用二叉树来定义）

2. 我们将使用符号N _H来表示高度为H的二叉搜索树中的最小节点数

3. 我们将创建一个根节点
   

4. 在Root 的左侧（或右侧），添加一个高度子树H-1（利用递归属性）。因此整个树中的节点数最少，左（或右）子树中的节点数也应该是最少的。因此N _H是 N _H-1的函数

5. 我们需要在右（或左）添加任何东西吗？
   不会。因为 BST 没有平衡因子的限制。因此，我们的树看起来像

6. 因此，要构造树H中节点数最少的高度二叉搜索树，我们可以采用节点数最少的 高度二叉搜索树，并且可以添加1个根节点。 因此，我们可以形成N H ₌ N _H-1 + 1 ，基本条件为N ₀ =1H-1
Recurrence Relation
   
   
   

要创建高度为 0 的 BST，我们需要添加一个节点。在整个答案中，我们将使用此约定

7. 现在，这Recurrence Relation很容易通过替换来解决，因此
   N _H = H+1
   N _H > H

8. 现在，设n为高度为 H 的 BST 中的节点数，则
   n
   ≥ N _H
   n ≥ H
   H ≤ n
   因此， H=O(n)
   或 O(H) = O(n)

因此，搜索的最坏情况时间复杂度将是O(n)

将此概念应用于 AVL 树

我们可以在 AVL 树上应用类似的概念。在阅读解决方案的后面部分后，可以找到递归关系：

N _H = N _H-1 + N _H-2 + 1

基本条件：

N ₀ = 1
N ₁ = 2

并且，求解递归的不等式条件将是

N _H ≥ ((1+√5)/2) ^H

然后，设n为节点数。因此，

n≥NH _{_}

简化后，可以得出结论

H≤1.44log ₂ (n)

将此概念应用于 GIVEN Tree

1. 让我们尝试构造给定高度树，H使得树中的节点数最少。

2. 我们将使用符号N _H来表示高度为H的给定树中的最小节点数

3. 我们将创建一个根节点
   

4. 在Root 的左侧（或右侧），添加一个高度子树H-1（利用递归属性）。因此整个树中的节点数最少，左（或右）子树中的节点数也应该是最少的。因此N _H是 N _H-1的函数

5. 我们需要在右（或左）添加任何东西吗？
   是的！因为节点上存在平衡因子的限制。
   我们需要在右侧（或左侧）添加子树。它的高度应该是多少？

   H？

   不，那么整棵树的高度将变为 H+1

   H-1？

   允许！因为根的平衡因子将为 0

   H-2？

   允许！因为根的平衡因子将为 1

   H-3？

   允许！因为根的平衡因子将是 2

   H-4？

   不允许！因为根的平衡因子将变为 3

   我们想要最小数量的节点，所以在和中H-1，我们将选择。因此整个树中的节点数最少，右（或左）子树中的节点数也应该是最少的。因此N _H也是N _H-3的函数 H-2H-3H-3

6. 因此，要构造给定高度树以H使树中的节点数最少，我们可以将左子树作为 给定高度树，H-1使得节点数最小，并且可以将右子树作为给定高度树，H-3使得其中的节点也是最少的，可以添加一个根节点。我们的树看起来像
   

   因此，我们可以将递归关系形成为

   N _H = N _H-1 + N _H-3 + 1
   基本条件为
   N ₀ =1
   N ₁ =2
   N ₂ =3

7. 现在，这Recurrence Relation很难解决。但礼貌地回答这个答案，我们可以得出结论
   N _H > (√2) ^H

8. 现在，让是给定树n中的节点数然后，

   n ≥ N _H
   n ≥ (√2) ^H
   log _√2 (n) ≥ H
   H ≤ log _√2 (n)
   H ≤ 2log ₂ (n)

因此，H=O(log(n))
或O(H) = O(log(n))

因此，在这个给定树中搜索的最坏情况时间复杂度将是O(log(n))

因此，数学证明！