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

Question

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

Consider the following height balanced BST where Balance factor = Height of left subtree - Height of right subtree & the accepted balance factors are 0, 1, -1, 2, and -2. What will be the time taken to search an element in such a kind of height-balanced BST? Explain.

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

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

Answer 1

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

定义最坏情况

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

In case of simple Binary Search Tree with no Balancing Factor Condition on Nodes, this maximum height can be n or n+1 (depending on convention whether height of single node tree will be 1 or 0) where n is number of nodes.

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

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

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

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

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

Here we will exploit the fact that Binary Tree is a Recursive Data Structure (A Binary Tree can be defined in terms of Binary Tree)

2. 我们将使用符号 N_H 表示 中的最小节点数高度为 H

   的二叉搜索树

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

4. 到Root的Left（或Right），添加一个高度H-1的子树（利用递归属性）。为了使整棵树的节点数最少，Left（或Right）subtree的节点数也应该最少。因此 N_H 是函数 N_H-1

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

6. 因此，构建高度 H 的 二叉搜索树 使得 个节点数 在树是最小值，我们可以采用二叉搜索树高度H-1使得节点数 是 最少，并且可以添加1个根节点。
   因此，我们可以将 Recurrence Relation 形成为
   N_H = N_H-1 + 1
   基本条件为
   N₀=1

To create BST of height 0, we need to add one node. Throughout the answer we will use this convention

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 ≥ N_H

关于简化，可以得出结论

H ≤ 1.44log₂(n)

在 GIVEN 树上应用这个概念

1. 让我们尝试构造 给定树 高度 H 使得 节点数 在这棵树是 最小值。

2. 我们将使用符号N_H表示给定的最小节点数树 高度H

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

4. 到Root的Left（或Right），添加一个高度H-1的子树（利用递归属性）。为了使整棵树的节点数最少，Left（或Right）subtree的节点数也应该最少。因此 N_H 是函数 N_H-1

5. 我们需要向右（或左）添加任何内容吗？
   是的！ 因为节点平衡系数有限制
   我们需要在 Right（或 Left）上添加子树。 它的高度应该是多少？

   H?

   不是，那么整棵树的高度就会变成H+1

   H-1?

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

   H-2?

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

   H-3?

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

   H-4?

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

   我们想要最少的节点数，所以在 H-1、H-2 和 H-3 中，我们将选择 H-3。为了使整棵树的节点数最少，右（或左）子树的节点数也应该最少。因此 N_H 是 also 的函数 N_H-3

6. 因此，构造 给定树 的高度 H 使得 节点数 在树是 minimum，我们可以将 LEFT 子树作为 给定树 的高度 H-1 这样 节点数 是 最小值 并且可以有 RIGHT子树作为 给定树 的高度 H-3 使得其中的 节点数 也是 最小值 ，可以添加一个Root Node。我们的树看起来像
   

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

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

7. 现在，这个 Recurrence Relation 很难解决。但是感谢this answer，我们可以得出结论
   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))

因此，数学证明！