给定右臂伸展的二叉搜索树数量

Question

给定右臂伸展的二叉搜索树数量

algorithmdata-structuresdynamic-programmingcombinatorics

3

针对一个包含不同（唯一）整数的数组，我想知道在所有排列中，右侧最长长度为k的二叉搜索树的数量。（如果k = 3，则root->right->right是叶节点）

（在我目前的要求下，我无法承受时间复杂度大于N^3的算法）

从不同的排列生成的两个相同的二叉搜索树被认为是不同的。

到目前为止，我的方法是：

假设有一个函数：

F(arr) = {a1, a2, a3...}

a1代表k=1的数组元素个数，a2代表k=2的数组元素个数，以此类推。

F(arr[1:n]) = 对于i从1到n的每个元素，计算（1 + df * F(子数组，其每个元素均大于arr[i] ) )

其中，df为动态因子，等于(n-1)C(小于arr[i]的元素个数)

我正在尝试创建一个dp来解决这个问题：

对数组进行排序
从最大的数字开始向较小的数字进行迭代
dp[i][i] = 1
对于j从i-1到1的所有元素，dp[j][i]是dp[j][i-1]的某个函数，但我无法确定这个函数

例如：对于数组{4, 3, 2, 1}，我期望的dp结果如下：

          arr[i]  4   3   2   1
                +---+---+---+---+
         k = 1  | 1 | 1 | 2 | 6 |
                +---+---+---+---+
         k = 2  | - | 1 | 3 |11 |
                +---+---+---+---+
         k = 3  | - | - | 1 | 6 |
                +---+---+---+---+
         k = 4  | - | - | - | 1 |
                +---+---+---+---+
verification(n!) 1    2   6   24

任何提示、建议、指针或引导我满足好奇心的好源都欢迎。谢谢。编辑：看来我可能需要一个三维dp数组。我正在处理相同的问题。编辑：修正了dp的第三列。

- Mohit Jain

感谢所有帮助过我的人。在更加努力思考并多花些时间纸上推敲后，我已经得到了答案。dp[j][i] = dp[j-1][i] * (i-1) + dp[j][i-1] - Mohit Jain

2个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hivert · Answer 1

好消息是，如果您不想要排列而只想要它们的数字，那么有一个公式可以实现。这些被称为（无符号）第一类斯特林数。原因是在二叉搜索树的右侧出现的数字是从左到右的最小值，即出现在i之前的数字大于i的数字。以下是一个示例，其中记录已经被下划线标记：

 6 8 3 5 4 2 7 1 9
 _   _     _   _

这会返回树形结构

          6
    3           8
 2     5      7   9
1     4

这些数字可以根据不同的特征（循环数等）进行排列组合计数。已知最大值或最小值是其中一些特征。您可以在整数序列在线百科全书Entry A008275上找到更多信息。

现在来回答如何计算它们的问题。设S(n,k)为具有k个从左到右的最小值的n个数字的排列数。您可以使用以下递归公式：

S(n,0)=0，对于所有n
S(n+1,k)=n*S(n,k)+S(n,k-1)，对于所有n>0和k>0

- Ivan Mushketyk · Answer 2

如果我正确理解了你的问题。

你不需要对数组进行排序。由于数组中的所有数字都是唯一的，因此可以假设每个可能的子树都是唯一的。
因此，您只需要计算可以构建具有N-k个唯一元素的唯一树的数量，其中N是您的数组的长度，k是最右侧分支的长度。换句话说，如果您将右子树固定为一个固定结构（根（节点1（节点2 ...节点K））），则它将是左子树排列的数量。

以下是计算大小为N的二叉树数量的方法：

public int numTrees(int n) {

    int[] ut = new int[Math.max(n + 1, 3)];

    ut[1] = 1;
    ut[2] = 2;

    for (int i = 3; i <= n; i++) {
        int u = 0;
        for (int j = 0; j < i; j++) {
            u += Math.max(1, ut[j]) * Math.max(1, ut[i - j - 1]);
        }
        ut[i] = u;
    }

    return ut[n];
}

它具有O(n^2)的时间复杂度和O(n)的空间复杂度。