在求解最优二叉搜索树时添加频率和
Adding sum of frequencies whille solving Optimal Binary search tree
我指的是 THIS 问题和解决方案。
首先，我不明白为什么要在递归方程中加入频率和。
有人可以帮助理解这个例子吗。
作者的话。
We add sum of frequencies from i to j (see first term in the above
formula), this is added because every search will go through root and
one comparison will be done for every search.
在代码中，频率总和（我不明白其用途）...对应于 fsum。
int optCost(int freq[], int i, int j)
{
// Base cases
if (j < i) // If there are no elements in this subarray
return 0;
if (j == i) // If there is one element in this subarray
return freq[i];
// Get sum of freq[i], freq[i+1], ... freq[j]
int fsum = sum(freq, i, j);
// Initialize minimum value
int min = INT_MAX;
// One by one consider all elements as root and recursively find cost
// of the BST, compare the cost with min and update min if needed
for (int r = i; r <= j; ++r)
{
int cost = optCost(freq, i, r-1) + optCost(freq, r+1, j);
if (cost < min)
min = cost;
}
// Return minimum value
return min + fsum;
}
其次，此解决方案将只是 return 最优成本。关于如何获得实际 bst 的任何建议？
为什么我们需要频率和
频率和背后的想法是正确计算特定树的成本。它的行为类似于存储树权重的累加器值。
想象一下，在第一级递归中，我们从位于树的第一级的所有键开始（我们还没有选择任何根元素）。记住权重函数 - 它对所有节点权重乘以节点级别求和。现在我们树的权重等于所有键的权重之和，因为我们的任何键都可以位于任何级别（从第一层开始），无论如何我们的结果中每个键至少有一个权重。
1) 假设我们找到了最佳根密钥，比如密钥r。接下来，我们将除 r 之外的所有键都向下移动一层，因为剩下的每个元素最多可以位于第二层（第一层已被占用）。因此，我们将剩下的每个键的权重添加到我们的总和中，因为无论如何，对于所有这些键，我们将至少有两倍的权重。我们根据 r 元素（从 r 向左和向右）将左侧的键分成两个子数组，我们之前 selected。
2) 下一步是 select 第二级的最优键，第一步留下的两个子数组中的每一个。这样做之后，我们再次将所有键向下移动一层并将它们的权重添加到总和中，因为它们将至少位于第三层，因此我们每个键至少有三倍的权重。
3) 等等。
我希望这个解释能让你理解为什么我们需要这个频率总和。
寻找最佳bst
正如作者在文末提到的
2) In the above solutions, we have computed optimal cost only. The
solutions can be easily modified to store the structure of BSTs also.
We can create another auxiliary array of size n to store the structure
of tree. All we need to do is, store the chosen ‘r’ in the innermost
loop.
我们可以做到。您将在下面找到我的实现。
一些注意事项：
1) 我被迫用实用程序 class Matrix 替换 int[n][n] 因为我使用的是 Visual C++，它不支持非编译时常量表达式作为数组大小。
2) 我使用了您提供的文章中的算法的第二种实现（带记忆），因为添加功能以向其存储最佳 bst 更容易。
3) 作者的代码有错误：
第二个循环 for (int i=0; i<=n-L+1; i++) 应该有 n-L 作为上限而不是 n-L+1.
4）我们存储最优bst的方式如下：
对于每一对i, j，我们存储最佳密钥索引。这与最优成本相同，但我们存储最优密钥索引而不是存储最优成本。例如，对于 0, n-1，我们将拥有结果树的根键 r 的索引。接下来，我们根据根元素索引 r 将数组一分为二，并获得它们的最佳键索引。我们可以通过访问矩阵元素 0, r-1 和 r+1, n-1 来确定。等等。效用函数 'PrintResultTree' 使用这种方法并按顺序（左子树、节点、右子树）打印结果树。所以你基本上得到有序列表，因为它是二叉搜索树。
5) 请不要因为我的代码而责备我——我不是真正的 C++ 程序员。 :)
int optimalSearchTree(int keys[], int freq[], int n, Matrix& optimalKeyIndexes)
{
/* Create an auxiliary 2D matrix to store results of subproblems */
Matrix cost(n,n);
optimalKeyIndexes = Matrix(n, n);
/* cost[i][j] = Optimal cost of binary search tree that can be
formed from keys[i] to keys[j].
cost[0][n-1] will store the resultant cost */
// For a single key, cost is equal to frequency of the key
for (int i = 0; i < n; i++)
cost.SetCell(i, i, freq[i]);
// Now we need to consider chains of length 2, 3, ... .
// L is chain length.
for (int L = 2; L <= n; L++)
{
// i is row number in cost[][]
for (int i = 0; i <= n - L; i++)
{
// Get column number j from row number i and chain length L
int j = i + L - 1;
cost.SetCell(i, j, INT_MAX);
// Try making all keys in interval keys[i..j] as root
for (int r = i; r <= j; r++)
{
// c = cost when keys[r] becomes root of this subtree
int c = ((r > i) ? cost.GetCell(i, r - 1) : 0) +
((r < j) ? cost.GetCell(r + 1, j) : 0) +
sum(freq, i, j);
if (c < cost.GetCell(i, j))
{
cost.SetCell(i, j, c);
optimalKeyIndexes.SetCell(i, j, r);
}
}
}
}
return cost.GetCell(0, n - 1);
}
下面是实用程序 class Matrix:
class Matrix
{
private:
int rowCount;
int columnCount;
std::vector<int> cells;
public:
Matrix()
{
}
Matrix(int rows, int columns)
{
rowCount = rows;
columnCount = columns;
cells = std::vector<int>(rows * columns);
}
int GetCell(int rowNum, int columnNum)
{
return cells[columnNum + rowNum * columnCount];
}
void SetCell(int rowNum, int columnNum, int value)
{
cells[columnNum + rowNum * columnCount] = value;
}
};
以及具有按顺序打印结果树的实用函数的主要方法：
//Print result tree in in-order
void PrintResultTree(
Matrix& optimalKeyIndexes,
int startIndex,
int endIndex,
int* keys)
{
if (startIndex == endIndex)
{
printf("%d\n", keys[startIndex]);
return;
}
else if (startIndex > endIndex)
{
return;
}
int currentOptimalKeyIndex = optimalKeyIndexes.GetCell(startIndex, endIndex);
PrintResultTree(optimalKeyIndexes, startIndex, currentOptimalKeyIndex - 1, keys);
printf("%d\n", keys[currentOptimalKeyIndex]);
PrintResultTree(optimalKeyIndexes, currentOptimalKeyIndex + 1, endIndex, keys);
}
int main(int argc, char* argv[])
{
int keys[] = { 10, 12, 20 };
int freq[] = { 34, 8, 50 };
int n = sizeof(keys) / sizeof(keys[0]);
Matrix optimalKeyIndexes;
printf("Cost of Optimal BST is %d \n", optimalSearchTree(keys, freq, n, optimalKeyIndexes));
PrintResultTree(optimalKeyIndexes, 0, n - 1, keys);
return 0;
}
编辑：
您可以在下面找到创建简单树状结构的代码。
这是实用工具TreeNodeclass
struct TreeNode
{
public:
int Key;
TreeNode* Left;
TreeNode* Right;
};
用 BuildResultTree 函数更新了 main 函数
void BuildResultTree(Matrix& optimalKeyIndexes,
int startIndex,
int endIndex,
int* keys,
TreeNode*& tree)
{
if (startIndex > endIndex)
{
return;
}
tree = new TreeNode();
tree->Left = NULL;
tree->Right = NULL;
if (startIndex == endIndex)
{
tree->Key = keys[startIndex];
return;
}
int currentOptimalKeyIndex = optimalKeyIndexes.GetCell(startIndex, endIndex);
tree->Key = keys[currentOptimalKeyIndex];
BuildResultTree(optimalKeyIndexes, startIndex, currentOptimalKeyIndex - 1, keys, tree->Left);
BuildResultTree(optimalKeyIndexes, currentOptimalKeyIndex + 1, endIndex, keys, tree->Right);
}
int main(int argc, char* argv[])
{
int keys[] = { 10, 12, 20 };
int freq[] = { 34, 8, 50 };
int n = sizeof(keys) / sizeof(keys[0]);
Matrix optimalKeyIndexes;
printf("Cost of Optimal BST is %d \n", optimalSearchTree(keys, freq, n, optimalKeyIndexes));
PrintResultTree(optimalKeyIndexes, 0, n - 1, keys);
TreeNode* tree = new TreeNode();
BuildResultTree(optimalKeyIndexes, 0, n - 1, keys, tree);
return 0;
}
我指的是 THIS 问题和解决方案。
首先，我不明白为什么要在递归方程中加入频率和。
作者的话。
We add sum of frequencies from i to j (see first term in the above formula), this is added because every search will go through root and one comparison will be done for every search.
在代码中，频率总和（我不明白其用途）...对应于 fsum。
int optCost(int freq[], int i, int j)
{
// Base cases
if (j < i) // If there are no elements in this subarray
return 0;
if (j == i) // If there is one element in this subarray
return freq[i];
// Get sum of freq[i], freq[i+1], ... freq[j]
int fsum = sum(freq, i, j);
// Initialize minimum value
int min = INT_MAX;
// One by one consider all elements as root and recursively find cost
// of the BST, compare the cost with min and update min if needed
for (int r = i; r <= j; ++r)
{
int cost = optCost(freq, i, r-1) + optCost(freq, r+1, j);
if (cost < min)
min = cost;
}
// Return minimum value
return min + fsum;
}
其次，此解决方案将只是 return 最优成本。关于如何获得实际 bst 的任何建议？
为什么我们需要频率和
频率和背后的想法是正确计算特定树的成本。它的行为类似于存储树权重的累加器值。
想象一下，在第一级递归中，我们从位于树的第一级的所有键开始（我们还没有选择任何根元素）。记住权重函数 - 它对所有节点权重乘以节点级别求和。现在我们树的权重等于所有键的权重之和，因为我们的任何键都可以位于任何级别（从第一层开始），无论如何我们的结果中每个键至少有一个权重。
1) 假设我们找到了最佳根密钥，比如密钥r。接下来，我们将除 r 之外的所有键都向下移动一层，因为剩下的每个元素最多可以位于第二层（第一层已被占用）。因此，我们将剩下的每个键的权重添加到我们的总和中，因为无论如何，对于所有这些键，我们将至少有两倍的权重。我们根据 r 元素（从 r 向左和向右）将左侧的键分成两个子数组，我们之前 selected。
2) 下一步是 select 第二级的最优键，第一步留下的两个子数组中的每一个。这样做之后，我们再次将所有键向下移动一层并将它们的权重添加到总和中，因为它们将至少位于第三层，因此我们每个键至少有三倍的权重。
3) 等等。
我希望这个解释能让你理解为什么我们需要这个频率总和。
寻找最佳bst
正如作者在文末提到的
2) In the above solutions, we have computed optimal cost only. The solutions can be easily modified to store the structure of BSTs also. We can create another auxiliary array of size n to store the structure of tree. All we need to do is, store the chosen ‘r’ in the innermost loop.
我们可以做到。您将在下面找到我的实现。
一些注意事项：
1) 我被迫用实用程序 class Matrix 替换 int[n][n] 因为我使用的是 Visual C++，它不支持非编译时常量表达式作为数组大小。
2) 我使用了您提供的文章中的算法的第二种实现（带记忆），因为添加功能以向其存储最佳 bst 更容易。
3) 作者的代码有错误：
第二个循环 for (int i=0; i<=n-L+1; i++) 应该有 n-L 作为上限而不是 n-L+1.
4）我们存储最优bst的方式如下：
对于每一对i, j，我们存储最佳密钥索引。这与最优成本相同，但我们存储最优密钥索引而不是存储最优成本。例如，对于 0, n-1，我们将拥有结果树的根键 r 的索引。接下来，我们根据根元素索引 r 将数组一分为二，并获得它们的最佳键索引。我们可以通过访问矩阵元素 0, r-1 和 r+1, n-1 来确定。等等。效用函数 'PrintResultTree' 使用这种方法并按顺序（左子树、节点、右子树）打印结果树。所以你基本上得到有序列表，因为它是二叉搜索树。
5) 请不要因为我的代码而责备我——我不是真正的 C++ 程序员。 :)
int optimalSearchTree(int keys[], int freq[], int n, Matrix& optimalKeyIndexes)
{
/* Create an auxiliary 2D matrix to store results of subproblems */
Matrix cost(n,n);
optimalKeyIndexes = Matrix(n, n);
/* cost[i][j] = Optimal cost of binary search tree that can be
formed from keys[i] to keys[j].
cost[0][n-1] will store the resultant cost */
// For a single key, cost is equal to frequency of the key
for (int i = 0; i < n; i++)
cost.SetCell(i, i, freq[i]);
// Now we need to consider chains of length 2, 3, ... .
// L is chain length.
for (int L = 2; L <= n; L++)
{
// i is row number in cost[][]
for (int i = 0; i <= n - L; i++)
{
// Get column number j from row number i and chain length L
int j = i + L - 1;
cost.SetCell(i, j, INT_MAX);
// Try making all keys in interval keys[i..j] as root
for (int r = i; r <= j; r++)
{
// c = cost when keys[r] becomes root of this subtree
int c = ((r > i) ? cost.GetCell(i, r - 1) : 0) +
((r < j) ? cost.GetCell(r + 1, j) : 0) +
sum(freq, i, j);
if (c < cost.GetCell(i, j))
{
cost.SetCell(i, j, c);
optimalKeyIndexes.SetCell(i, j, r);
}
}
}
}
return cost.GetCell(0, n - 1);
}
下面是实用程序 class Matrix:
class Matrix
{
private:
int rowCount;
int columnCount;
std::vector<int> cells;
public:
Matrix()
{
}
Matrix(int rows, int columns)
{
rowCount = rows;
columnCount = columns;
cells = std::vector<int>(rows * columns);
}
int GetCell(int rowNum, int columnNum)
{
return cells[columnNum + rowNum * columnCount];
}
void SetCell(int rowNum, int columnNum, int value)
{
cells[columnNum + rowNum * columnCount] = value;
}
};
以及具有按顺序打印结果树的实用函数的主要方法：
//Print result tree in in-order
void PrintResultTree(
Matrix& optimalKeyIndexes,
int startIndex,
int endIndex,
int* keys)
{
if (startIndex == endIndex)
{
printf("%d\n", keys[startIndex]);
return;
}
else if (startIndex > endIndex)
{
return;
}
int currentOptimalKeyIndex = optimalKeyIndexes.GetCell(startIndex, endIndex);
PrintResultTree(optimalKeyIndexes, startIndex, currentOptimalKeyIndex - 1, keys);
printf("%d\n", keys[currentOptimalKeyIndex]);
PrintResultTree(optimalKeyIndexes, currentOptimalKeyIndex + 1, endIndex, keys);
}
int main(int argc, char* argv[])
{
int keys[] = { 10, 12, 20 };
int freq[] = { 34, 8, 50 };
int n = sizeof(keys) / sizeof(keys[0]);
Matrix optimalKeyIndexes;
printf("Cost of Optimal BST is %d \n", optimalSearchTree(keys, freq, n, optimalKeyIndexes));
PrintResultTree(optimalKeyIndexes, 0, n - 1, keys);
return 0;
}
编辑：
您可以在下面找到创建简单树状结构的代码。
这是实用工具TreeNodeclass
struct TreeNode
{
public:
int Key;
TreeNode* Left;
TreeNode* Right;
};
用 BuildResultTree 函数更新了 main 函数
void BuildResultTree(Matrix& optimalKeyIndexes,
int startIndex,
int endIndex,
int* keys,
TreeNode*& tree)
{
if (startIndex > endIndex)
{
return;
}
tree = new TreeNode();
tree->Left = NULL;
tree->Right = NULL;
if (startIndex == endIndex)
{
tree->Key = keys[startIndex];
return;
}
int currentOptimalKeyIndex = optimalKeyIndexes.GetCell(startIndex, endIndex);
tree->Key = keys[currentOptimalKeyIndex];
BuildResultTree(optimalKeyIndexes, startIndex, currentOptimalKeyIndex - 1, keys, tree->Left);
BuildResultTree(optimalKeyIndexes, currentOptimalKeyIndex + 1, endIndex, keys, tree->Right);
}
int main(int argc, char* argv[])
{
int keys[] = { 10, 12, 20 };
int freq[] = { 34, 8, 50 };
int n = sizeof(keys) / sizeof(keys[0]);
Matrix optimalKeyIndexes;
printf("Cost of Optimal BST is %d \n", optimalSearchTree(keys, freq, n, optimalKeyIndexes));
PrintResultTree(optimalKeyIndexes, 0, n - 1, keys);
TreeNode* tree = new TreeNode();
BuildResultTree(optimalKeyIndexes, 0, n - 1, keys, tree);
return 0;
}