Dado un número entero N , la tarea es contar el número de posibles árboles binarios de búsqueda con N claves.
Ejemplos:
Input: N = 2 Output: 2 For N = 2, there are 2 unique BSTs 1 2 \ / 2 1 Input: N = 9 Output: 4862
Enfoque: El número de árboles de búsqueda binarios que se formarán con N claves se puede calcular simplemente evaluando el número correspondiente en la serie de números catalanes .
Los primeros números catalanes para n = 0, 1, 2, 3,… son 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,…
Los números catalanes satisfacen la siguiente fórmula recursiva:
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <iostream> using namespace std; // Function to return the count // of unique BSTs with n keys int uniqueBSTs(int n) { int n1, n2, sum = 0; // Base cases if (n == 1 || n == 0) return 1; // Find the nth Catalan number for (int i = 1; i <= n; i++) { // Recursive calls n1 = uniqueBSTs(i - 1); n2 = uniqueBSTs(n - i); sum += n1 * n2; } // Return the nth Catalan number return sum; } // Driver code int main() { int n = 2; // Function call cout << uniqueBSTs(n); return 0; }
Java
// Java implementation of the approach import java.io.*; class GFG { // Function to return the count // of unique BSTs with n keys static int uniqueBSTs(int n) { int n1, n2, sum = 0; // Base cases if (n == 1 || n == 0) return 1; // Find the nth Catalan number for (int i = 1; i <= n; i++) { // Recursive calls n1 = uniqueBSTs(i - 1); n2 = uniqueBSTs(n - i); sum += n1 * n2; } // Return the nth Catalan number return sum; } // Driver code public static void main(String[] args) { int n = 2; // Function call System.out.println(uniqueBSTs(n)); } } // This code is contributed by jit_t.
Python3
# Python3 implementation of the approach # Function to return the count # of unique BSTs with n keys def uniqueBSTs(n): n1, n2, sum = 0, 0, 0 # Base cases if (n == 1 or n == 0): return 1 # Find the nth Catalan number for i in range(1, n + 1): # Recursive calls n1 = uniqueBSTs(i - 1) n2 = uniqueBSTs(n - i) sum += n1 * n2 # Return the nth Catalan number return sum # Driver code n = 2 # Function call print(uniqueBSTs(n)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach using System; class GFG { // Function to return the count // of unique BSTs with n keys static int uniqueBSTs(int n) { int n1, n2, sum = 0; // Base cases if (n == 1 || n == 0) return 1; // Find the nth Catalan number for (int i = 1; i <= n; i++) { // Recursive calls n1 = uniqueBSTs(i - 1); n2 = uniqueBSTs(n - i); sum += n1 * n2; } // Return the nth Catalan number return sum; } // Driver code static public void Main() { int n = 2; // Function call Console.WriteLine(uniqueBSTs(n)); } } // This code is contributed by ajit.
Javascript
<script> // Javascript implementation of the approach // Function to return the count // of unique BSTs with n keys function uniqueBSTs(n) { let n1, n2, sum = 0; // Base cases if (n == 1 || n == 0) return 1; // Find the nth Catalan number for (let i = 1; i <= n; i++) { // Recursive calls n1 = uniqueBSTs(i - 1); n2 = uniqueBSTs(n - i); sum += n1 * n2; } // Return the nth Catalan number return sum; } let n = 2; // Function call document.write(uniqueBSTs(n)); </script>
2
El problema se puede resolver mediante programación dinámica.
Aquí hay un fragmento de cómo procederá el árbol de recurrencia:
G(4) / | | \ G(0)G(3) G(1)G(2) G(2)G(1) G(3)G(0) / | \ G(0)G(2) G(1)G(1) G(2)G(0) / \ G(0)G(1) G(1)G(0) // base case
Nota: Sin memorización, la complejidad del tiempo está limitada por O(N x N!).
Dada una secuencia 1…n, para construir un árbol de búsqueda binaria (BST) a partir de la secuencia, podríamos enumerar cada número i en la secuencia y usar el número como raíz, naturalmente, la subsecuencia 1…(i-1) en su lado izquierdo estaría en la rama izquierda de la raíz, y de manera similar la subsecuencia derecha (i+1)…n estaría en la rama derecha de la raíz. Entonces podemos construir el subárbol a partir de la subsecuencia recursivamente. A través del enfoque anterior, podemos asegurarnos de que el BST que construimos sea único, ya que tienen raíces únicas.
El problema es calcular el número de BST únicos. Para hacerlo, necesitamos definir dos funciones:
1.G(n): the number of unique BST for a sequence of length n. 2.F(i, n), 1 <= i <= n: The number of unique BST, where the number i is the root of BST, and the sequence ranges from 1 to n. As one can see, G(n) is the actual function we need to calculate in order to solve the problem. And G(n) can be derived from F(i, n), which at the end, would recursively refer to G(n). First of all, given the above definitions, we can see that the total number of unique BST G(n), is the sum of BST F(i) using each number i as a root. i.e., G(n) = F(1, n) + F(2, n) + ... + F(n, n). Given a sequence 1…n, we pick a number i out of the sequence as the root, then the number of unique BST with the specified root F(i), is the cartesian product of the number of BST for its left and right subtrees.For example, F(2, 4): the number of unique BST tree with number 2 as its root. To construct an unique BST out of the entire sequence [1, 2, 3, 4] with 2 as the root, which is to say, we need to construct an unique BST out of its left subsequence [1] and another BST out of the right subsequence [3,4], and then combine them together (i.e. cartesian product). F(i, n) = G(i-1) * G(n-i) 1 <= i <= n Combining the above two formulas, we obtain the recursive formula for G(n). i.e. G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0)
En términos de cálculo, debemos comenzar con el número más bajo, ya que el valor de G(n)
depende de los valores de G(0) … G(n-1).
A continuación se muestra la implementación anterior del algoritmo anterior:
C++
// C++ dynamic programming implementation of the approach #include <iostream> using namespace std; // Function to return the count // of unique BSTs with n keys int uniqueBSTs(int n) { // construct a dp array to store the // subsequent results int dparray[n + 1] = { 0 }; // there is only one combination to construct a // BST out of a sequence of dparray[0] = dparray[1] = 1; // length 1 (only a root) or 0 (empty tree). for (int i = 2; i <= n; ++i) { // choosing every value as root for (int k = 1; k <= i; ++k) { dparray[i] += dparray[k - 1] * dparray[i - k]; } } return dparray[n]; } // Driver code int main() { int n = 2; // Function call cout << uniqueBSTs(n); return 0; }
Java
// Java dynamic programming implementation of the approach import java.io.*; import java.util.*; class GFG { // Function to return the count // of unique BSTs with n keys static int uniqueBSTs(int n) { // construct a dp array to store the // subsequent results int[] dparray = new int[n + 1]; Arrays.fill(dparray, 0); // there is only one combination to construct a // BST out of a sequence of dparray[0] = dparray[1] = 1; // length 1 (only a root) or 0 (empty tree). for (int i = 2; i <= n; ++i) { // choosing every value as root for (int k = 1; k <= i; ++k) { dparray[i] += dparray[k - 1] * dparray[i - k]; } } return dparray[n]; } // Driver code public static void main (String[] args) { int n = 2; // Function call System.out.println(uniqueBSTs(n)); } } // This code is contributed by avanitrachhadiya2155
Python3
# Python3 dynamic programming # implementation of the approach # Function to return the count # of unique BSTs with n keys def uniqueBSTs(n): # Construct a dp array to store the # subsequent results dparray = [0 for i in range(n + 1)] # There is only one combination to # construct a BST out of a sequence of dparray[0] = 1 dparray[1] = 1 # length 1 (only a root) or 0 (empty tree). for i in range(2, n + 1, 1): # Choosing every value as root for k in range(1, i + 1, 1): dparray[i] += (dparray[k - 1] * dparray[i - k]) return dparray[n] # Driver code if __name__ == '__main__': n = 2 # Function call print(uniqueBSTs(n)) # This code is contributed by bgangwar59
C#
// C# dynamic programming implementation // of the approach using System; class GFG{ // Function to return the count // of unique BSTs with n keys static int uniqueBSTs(int n) { // construct a dp array to store the // subsequent results int[] dparray = new int[n + 1]; // there is only one combination to // construct a BST out of a sequence of dparray[0] = dparray[1] = 1; // length 1 (only a root) or 0 (empty tree). for(int i = 2; i <= n; ++i) { // Choosing every value as root for(int k = 1; k <= i; ++k) { dparray[i] += dparray[k - 1] * dparray[i - k]; } } return dparray[n]; } // Driver code public static void Main(String[] args) { int n = 2; // Function call Console.WriteLine(uniqueBSTs(n)); } } // This code is contributed by Amit Katiyar
Javascript
<script> // Javascript dynamic programming // implementation of the approach // Function to return the count // of unique BSTs with n keys function uniqueBSTs(n) { // construct a dp array to store the // subsequent results let dparray = new Array(n + 1); dparray.fill(0); // there is only one combination to construct a // BST out of a sequence of dparray[0] = dparray[1] = 1; // length 1 (only a root) or 0 (empty tree). for (let i = 2; i <= n; ++i) { // choosing every value as root for (let k = 1; k <= i; ++k) { dparray[i] += dparray[k - 1] * dparray[i - k]; } } return dparray[n]; } let n = 2; // Function call document.write(uniqueBSTs(n)); </script>
2
Complejidad de tiempo: O(N 2 ) Complejidad de espacio : O(N)
En esta publicación, discutiremos una solución espacial O(n) y O(1) basada en Programación Dinámica.
Sabemos que la fórmula del número catalán para una variable n es la que se simplifica a
Del mismo modo número catalán para (n-1) Nodes =
La fórmula para n Nodes se puede reescribir como
= Número catalán para (n-1) Nodes*
Entonces, para cada iteración de ‘i’ que va de 1 a n, almacenaremos el número catalán para los Nodes ‘i-1’ y calcularemos para el i-ésimo Node.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h> using namespace std; // Function to find number of unique BST int numberOfBST(int n) { // For n=1 answer is 1 long v = 1; for (int i = 2; i <= n; i++) { // using previous answer in v to calculate current // catalan number. v = ((v * (i * 2) * (i * 2 - 1)) / ((i + 1) * (i))); } return v; } int main() { int n = 4; cout << "Number of Unique BST for " << n << " nodes is " << numberOfBST(n) << endl; return 0; }
Java
class GFG{ // Function to find number of unique BST static long numberOfBST(int n) { // For n=1 answer is 1 long v = 1; for(int i = 2; i <= n; i++) { // Using previous answer in v to calculate // current catalan number. v = ((v * (i * 2) * (i * 2 - 1)) / ((i + 1) * (i))); } return v; } // Driver code public static void main(String[] args) { int n = 4; System.out.print("Number of Unique BST for " + n + " nodes is " + numberOfBST(n) + "\n"); } } // This code is contributed by shikhasingrajput
Python3
# Function to find number of unique BST def numberOfBST(n): # For n=1 answer is 1 v = 1 for i in range(2, n + 1): # using previous answer in v to calculate current catalan number. v = ((v * (i * 2) * (i * 2 - 1)) / ((i + 1) * (i))) return int(v) n = 4 print("Number of Unique BST for", n, "nodes is", numberOfBST(n)) # This code is contributed by divyesh072019.
C#
using System; class GFG { // Function to find number of unique BST static int numberOfBST(int n) { // For n=1 answer is 1 int v = 1; for (int i = 2; i <= n; i++) { // using previous answer in v to calculate current // catalan number. v = ((v * (i * 2) * (i * 2 - 1)) / ((i + 1) * (i))); } return v; } static void Main() { int n = 4; Console.Write("Number of Unique BST for " + n + " nodes is " + numberOfBST(n)); } } // This code is contributed by rameshtravel07.
Javascript
<script> // Function to find number of unique BST function numberOfBST(n) { // For n=1 answer is 1 let v = 1; for (let i = 2; i <= n; i++) { // using previous answer in v to calculate current // catalan number. v = ((v * (i * 2) * (i * 2 - 1)) / ((i + 1) * (i))); } return v; } let n = 4; document.write("Number of Unique BST for " + n + " nodes is " + numberOfBST(n)); // This code is contributed by mukesh07. </script>
Number of Unique BST for 4 nodes is 14
Complejidad Temporal: O(n)
Espacio Auxiliar: O(1).
Publicación traducida automáticamente
Artículo escrito por KunalGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA