具有 n 个键的总可能二叉搜索树数量

二叉搜索树是一种二叉树数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

• 其左子树中所有节点的值都小于该节点的值。
• 其右子树中所有节点的值都大于该节点的值。

因此，这一特性使得二叉树是有序的，从而可以快速地进行元素的搜索、插入和删除。

问题陈述

创建一个程序，确定对于给定数量 'n' 个不同键，可以实现的二叉搜索树 (BST) 的总数。目标是设计一个解决方案，计算并输出可能的唯一 BST 的总数，同时考虑到二叉搜索树的排序约束，即每个节点的左子树包含小于该节点的值，右子树包含大于该节点的值。该程序应设计为能够处理不同的 'n' 值，并准确计算可能的 BST 的总数。

解决方案

卡特兰数表示用给定数量的键可以形成的结构上唯一的 BST 的数量。

卡特兰数

卡特兰数是一个自然数序列，出现在各种计数问题中，通常涉及递归结构。

对于一个有 n 个键的 BST，存在不同结构上唯一的 BST。

公式

代码实现

递归方法

说明

• catalanN 方法利用递归来确定第 n 个卡特兰数。
• 它有一个 n = 0 的基本情况，此时卡特兰数为 1。
• 递归公式被用来确定不同 n 值的卡特兰数。
• countBSTs 方法基本上是调用 catalanN 技术来获得具有 n 个键的 BST 的绝对数量。
• main 方法用于测试。
• 它将 n 的值设置为任何整数值。
• 然后它调用 countBSTs 策略来获取 BST 的总数并打印结果。
• 该程序打印具有预定义键数的 BST 的绝对数量。
• 在 catalanN 方法中使用的公式是计算卡特兰数的标准方程。

时间复杂度

当时间复杂度与递归调用次数成正比时，时间复杂度为 O(n²)。

空间复杂度

空间由递归栈的最大深度决定。对于当前情况，递归深度可以达到 n，这意味着空间复杂度为 O(n)。

动态规划方法

输出

说明

• 动态规划数组 dp 存储了键数为 0 到 n 之间每个计数的 BST 的总数。
• 由于对于一个键和零个键都只有一个 BST，基本情况将 dp[0] 和 dp[1] 定义为 1。
• 嵌套循环用于为 2 到 n 个键的算法运行 BST 的数量。
• 获得 BST 总数的公式是 dp[i] += dp[j] * dp[i - j - 1]，这个公式也考虑了所有左右子树的选项。
• 最后，结果存放在 dp[n] 中，这是具有 n 个键的 BST 的绝对数量。

时间复杂度

外层循环从 2 开始并重复 n 次。内层循环从 0 到 i，对于外层循环的每次迭代，重复不超过 i 次。在内层循环内部，有一个恒定的操作流程。这两个循环导致了 O(n²) 的总时间复杂度。

空间复杂度

一个大小为 n+1 的名为 dp 的数组被用来存储中间结果。最终，空间复杂度为 O(n)，因为这是数据的大小。对于二叉搜索树问题，动态规划技术是首选，因为它具有良好的时间复杂度并避免了冗余计算。

结论

最终，可以通过递归和动态规划两种方法成功计算出具有“n”个键的二叉搜索树（BST）的总数。递归策略使用卡特兰数公式，其时间复杂度为 O(n²)。然而，动态规划技术通过存储中间结果来改进循环，从而获得更好的时间效率。