最优二叉搜索树

我们知道，在二叉搜索树中，左子树中的节点值小于根节点，右子树中的节点值大于根节点。

我们知道树中每个节点的键值，我们也知道每个节点在搜索方面的频率，这意味着搜索一个节点需要多少时间。频率和键值决定了搜索一个节点的总成本。搜索成本在各种应用中是一个非常重要的因素。搜索一个节点的总成本应该更低。在 BST 中搜索一个节点所需的时间比平衡二叉搜索树要长，因为平衡二叉搜索树的层数比 BST 少。有一种方法可以降低二叉搜索树的成本，称为最优二叉搜索树。

让我们通过一个例子来理解。

如果键值为 10, 20, 30, 40, 50, 60, 70

在上面的树中，左子树中的所有节点都小于根节点的值，右子树中的所有节点都大于根节点的值。搜索一个节点所需的最大时间等于树的最小高度，等于 logn。

现在我们将看看给定数量的键可以构成多少个二叉搜索树。

例如：10、20、30 是键，以下是可以用这些键构成的二叉搜索树。

计算树数量的公式

当我们使用上述公式时，发现总共可以创建 5 棵树。

搜索一个元素所需的成本取决于为搜索一个元素而进行的比较次数。现在，我们将计算上述二叉搜索树的平均时间成本。

在上面的树中，可以进行总共 3 次比较。平均比较次数为

在上面的树中，可以进行的平均比较次数为

在上面的树中，可以进行的平均比较次数为

在上面的树中，总共可以进行 3 次比较。因此，可以进行的平均比较次数为

在上面的树中，总共可以进行 3 次比较。因此，可以进行的平均比较次数为

在第三种情况下，比较次数较少，因为树的高度较小，所以它是一棵平衡二叉搜索树。

到目前为止，我们了解了高度平衡二叉搜索树。为了找到最优二叉搜索树，我们将确定搜索键的频率。

假设与键 10、20、30 关联的频率分别为 3、2、5。

上面的树有不同的频率。频率最低的树将被视为最优二叉搜索树。频率为 17 的树是最低的，因此它将被视为最优二叉搜索树。

动态方法

考虑下表，其中包含键和频率。

首先，我们将计算 j-i 等于零的值。

当 i=0, j=0 时，j-i = 0

当 i = 1, j=1 时，j-i = 0

当 i = 2, j=2 时，j-i = 0

当 i = 3, j=3 时，j-i = 0

当 i = 4, j=4 时，j-i = 0

因此，c[0, 0] = 0, c[1 , 1] = 0, c[2,2] = 0, c[3,3] = 0, c[4,4] = 0

现在我们将计算 j-i 等于 1 的值。

当 j=1, i=0 时，j-i = 1

当 j=2, i=1 时，j-i = 1

当 j=3, i=2 时，j-i = 1

当 j=4, i=3 时，j-i = 1

现在为了计算成本，我们只考虑第 j 个值。

c[0,1] 的成本是 4（键是 10，对应键 10 的成本是 4）。

c[1,2] 的成本是 2（键是 20，对应键 20 的成本是 2）。

c[2,3] 的成本是 6（键是 30，对应键 30 的成本是 6）

c[3,4] 的成本是 3（键是 40，对应键 40 的成本是 3）

现在我们将计算 j-i = 2 的值

当 j=2, i=0 时，j-i = 2

当 j=3, i=1 时，j-i = 2

当 j=4, i=2 时，j-i = 2

在这种情况下，我们将考虑两个键。

• 当 i=0 且 j=2 时，键为 10 和 20。可以用这两个键构建的两种可能的树如下所示

在第一个二叉树中，成本将是：4*1 + 2*2 = 8

在第二个二叉树中，成本将是：4*2 + 2*1 = 10

最小成本是 8；因此，c[0,2] = 8

• 当 i=1 且 j=3 时，键为 20 和 30。可以用这两个键构建的两种可能的树如下所示

在第一个二叉树中，成本将是：1*2 + 2*6 = 14

在第二个二叉树中，成本将是：1*6 + 2*2 = 10

最小成本是 10；因此，c[1,3] = 10

• 当 i=2 且 j=4 时，我们将考虑键 3 和 4，即 30 和 40。可以用这两个键构建的两种可能的树如下所示

在第一个二叉树中，成本将是：1*6 + 2*3 = 12

在第二个二叉树中，成本将是：1*3 + 2*6 = 15

最小成本是 12，因此 c[2,4] = 12

现在我们将计算 j-i = 3 的值

当 j=3, i=0 时，j-i = 3

当 j=4, i=1 时，j-i = 3

• 当 i=0, j=3 时，我们将考虑三个键，即 10、20 和 30。

以下是如果将 10 视为根节点可以构建的树。

在上面的树中，10 是根节点，20 是节点 10 的右子节点，30 是节点 20 的右子节点。

成本将是：1*4 + 2*2 + 3*6 = 26

在上面的树中，10 是根节点，30 是节点 10 的右子节点，20 是节点 20 的左子节点。

成本将是：1*4 + 2*6 + 3*2 = 22

如果将 20 视为根节点，可以创建以下树。

在上面的树中，20 是根节点，30 是节点 20 的右子节点，10 是节点 20 的左子节点。

成本将是：1*2 + 4*2 + 6*2 = 22

如果将 30 视为根节点，可以创建以下树。

在上面的树中，30 是根节点，20 是节点 30 的左子节点，10 是节点 20 的左子节点。

成本将是：1*6 + 2*2 + 3*4 = 22

在上面的树中，30 是根节点，10 是节点 30 的左子节点，20 是节点 10 的右子节点。

成本将是：1*6 + 2*4 + 3*2 = 20

因此，最小成本是 20，它是第 3 个根。所以，c[0,3] 等于 20。

• 当 i=1 且 j=4 时，我们将考虑键 20、30、40

c[1,4] = min{ c[1,1] + c[2,4], c[1,2] + c[3,4], c[1,3] + c[4,4] } + 11

= min{0+12, 2+3, 10+0}+ 11

= min{12, 5, 10} + 11

最小值为 5；因此，c[1,4] = 5+11 = 16

• 现在我们将计算 j-i = 4 的值

当 j=4 且 i=0 时，j-i = 4

在这种情况下，我们将考虑四个键，即 10、20、30 和 40。10、20、30 和 40 的频率分别为 4、2、6 和 3。

w[0, 4] = 4 + 2 + 6 + 3 = 15

如果我们将 10 视为根节点，那么

C[0, 4] = min {c[0,0] + c[1,4]}+ w[0,4]

= min {0 + 16} + 15= 31

如果我们将 20 视为根节点，那么

C[0,4] = min{c[0,1] + c[2,4]} + w[0,4]

= min{4 + 12} + 15

= 16 + 15 = 31

如果我们将 30 视为根节点，那么

C[0,4] = min{c[0,2] + c[3,4]} +w[0,4]

= min {8 + 3} + 15

= 26

如果我们将 40 视为根节点，那么

C[0,4] = min{c[0,3] + c[4,4]} + w[0,4]

= min{20 + 0} + 15

= 35

在上述情况中，我们观察到 26 是最小成本；因此，c[0,4] 等于 26。

可以创建最优二叉树为

计算最小成本的通用公式是

C[i,j] = min{c[i, k-1] + c[k,j]} + w(i,j)