Requisito previo: número total de posibles árboles binarios de búsqueda con n claves
dada una array arr[] de N enteros. La tarea es contar el número de árboles de búsqueda binaria que se pueden realizar utilizando cada Node del elemento en arr[] como Node raíz.
Ejemplos:
Entrada: arr[] = { 20, 10, 30 }
Salida: 1 2 2
Entrada: arr[] = { 1, 2, 3, 4, 5 }
Salida: 14 5 4 5 14
Enfoque:
El número total de árboles de búsqueda binarios (BST) posibles viene dado por el número catalán :
Cn = (2n)!/(( n+1)!*n!) where n = number of distinct keys.
- Cuente el número de elementos (digamos c1 ) menos que el Node actual.
- Cuente el número de elementos (digamos c2 ) mayor que el Node actual.
- Luego, el número total de árboles de búsqueda binarios (BST) se puede formar usando el elemento actual como un Node raíz es igual al producto del número total de BST formados usando elementos c1 y el número total de BST formados usando elementos c2 .
Total Number of BST = Cc1*Cc2
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above code
#include <iostream>
using namespace std;
// A function to find factorial of a
// given number
int fact(int num)
{
int fact = 1;
while(num > 1)
{
fact *= num;
num -= 1;
}
return fact;
}
// Find nth catalan number
int catalan(int n)
{
return fact(2 * n)/(fact(n) * fact(n + 1)) ;
}
// Driver Code
int main()
{
// size of arr[]
int n = 5;
// Elements in arr[]
int arr[] = {1, 2, 3, 4, 5};
int i,k;
for(k = 0; k < n; k++)
{
int s = 0;
// Count the number of element
// less than current element
// in arr[k]
for(i = 0; i < n; i++)
{
if (arr[i] < arr[k])
s += 1 ;
}
// Here s = number of node in left
// BST and (n-s-1) = number of node
// in right BST
// Find number of BST using elements
// in left BST
int catalan_leftBST = catalan(s) ;
// Find number of BST using elements
// in right BST
int catalan_rightBST = catalan(n - s - 1) ;
// Find total number of BST
int totalBST = catalan_rightBST * catalan_leftBST ;
// Print total BST count
cout<< totalBST << " " ;
}
}
// This code is contributed by AnkitRai01
Java
// java implementation of the above code
public class GFG
{
// A function to find factorial of a
// given number
static int fact(int num)
{
int fact = 1;
while(num > 1)
{
fact *= num;
num -= 1;
}
return fact;
}
// Find nth catalan number
static int catalan(int n)
{
return fact(2 * n)/(fact(n) * fact(n + 1)) ;
}
// Driver Code
public static void main (String[] args)
{
// size of arr[]
int n = 5;
// Elements in arr[]
int arr[] = {1, 2, 3, 4, 5};
int i,k;
for(k = 0; k < n; k++)
{
int s = 0;
// Count the number of element
// less than current element
// in arr[k]
for(i = 0; i < n; i++)
{
if (arr[i] < arr[k])
s += 1 ;
}
// Here s = number of node in left
// BST and (n-s-1) = number of node
// in right BST
// Find number of BST using elements
// in left BST
int catalan_leftBST = catalan(s) ;
// Find number of BST using elements
// in right BST
int catalan_rightBST = catalan(n - s - 1) ;
// Find total number of BST
int totalBST = catalan_rightBST * catalan_leftBST ;
// Print total BST count
System.out.print(totalBST + " ") ;
}
}
}
// This code is contributed by AnkitRai01
Python3
# A function to find factorial of a # given number def fact(num): fact = 1; while(num>1): fact = fact * num; num = num-1; return fact; # Find nth catalan number def catalan(n): return fact(2 * n)//(fact(n)*fact(n + 1)) # Driver Code if __name__ == '__main__': # size of arr[] n = 5 # Elements in arr[] arr = [1, 2, 3, 4, 5] for k in range(n): s = 0 # Count the number of element # less than current element # in arr[k] for i in range(n): if arr[i] < arr[k]: s+= 1 # Here s = number of node in left # BST and (n-s-1) = number of node # in right BST # Find number of BST using elements # in left BST catalan_leftBST = catalan(s) # Find number of BST using elements # in right BST catalan_rightBST = catalan(n-s-1) # Find total number of BST totalBST = catalan_rightBST * catalan_leftBST # Print total BST count print(totalBST, end =" ")
C#
// C# implementation of the above code
using System;
class GFG
{
// A function to find factorial of a
// given number
static int fact(int num)
{
int fact = 1;
while(num > 1)
{
fact *= num;
num -= 1;
}
return fact;
}
// Find nth catalan number
static int catalan(int n)
{
return fact(2 * n)/(fact(n) * fact(n + 1)) ;
}
// Driver Code
public static void Main(String[] args)
{
// size of []arr
int n = 5;
// Elements in []arr
int []arr = {1, 2, 3, 4, 5};
int i,k;
for(k = 0; k < n; k++)
{
int s = 0;
// Count the number of element
// less than current element
// in arr[k]
for(i = 0; i < n; i++)
{
if (arr[i] < arr[k])
s += 1 ;
}
// Here s = number of node in left
// BST and (n-s-1) = number of node
// in right BST
// Find number of BST using elements
// in left BST
int catalan_leftBST = catalan(s) ;
// Find number of BST using elements
// in right BST
int catalan_rightBST = catalan(n - s - 1) ;
// Find total number of BST
int totalBST = catalan_rightBST * catalan_leftBST ;
// Print total BST count
Console.Write(totalBST + " ") ;
}
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the above code
// A function to find factorial of a
// given number
function fact(num)
{
var fact = 1;
while(num > 1)
{
fact *= num;
num -= 1;
}
return fact;
}
// Find nth catalan number
function catalan(n)
{
return fact(2 * n)/(fact(n) * fact(n + 1)) ;
}
// Driver Code
// size of arr[]
var n = 5;
// Elements in arr[]
var arr = [1, 2, 3, 4, 5] ;
var i,k;
for(k = 0; k < n; k++)
{
var s = 0;
// Count the number of element
// less than current element
// in arr[k]
for(i = 0; i < n; i++)
{
if (arr[i] < arr[k])
s += 1 ;
}
// Here s = number of node in left
// BST and (n-s-1) = number of node
// in right BST
// Find number of BST using elements
// in left BST
var catalan_leftBST = catalan(s) ;
// Find number of BST using elements
// in right BST
var catalan_rightBST = catalan(n - s - 1) ;
// Find total number of BST
var totalBST = catalan_rightBST * catalan_leftBST ;
// Print total BST count
document.write( totalBST + " ");
}
</script>
Producción:
14 5 4 5 14
Complejidad del tiempo: O(N 2 )