Número total de posibles árboles binarios de búsqueda y árboles binarios con n claves

Número total de árboles binarios de búsqueda posibles con n claves diferentes (countBST(n)) = número catalán Cn = (2n)! / ((n + 1)! * n!)

Para n = 0, 1, 2, 3,… los valores de los números catalanes son 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,…. También lo son los números de árboles de búsqueda binarios.

Número total de árboles binarios posibles con n claves diferentes (countBT(n)) = countBST(n) * n! 

A continuación se muestra el código para encontrar el recuento de BST y árboles binarios con n números. El código para encontrar el n’ésimo número catalán está tomado de aquí .

// See https://www.geeksforgeeks.org/program-nth-catalan-number/
// for reference of below code.
 
#include <bits/stdc++.h>
using namespace std;
 
// A function to find factorial of a given number
unsigned long int factorial(unsigned int n)
{
    unsigned long int res = 1;
 
    // Calculate value of [1*(2)*---*(n-k+1)] / [k*(k-1)*---*1]
    for (int i = 1; i <= n; ++i)
    {
        res *= i;
    }
 
    return res;
}
 
unsigned long int binomialCoeff(unsigned int n, unsigned int k)
{
    unsigned long int res = 1;
 
    // Since C(n, k) = C(n, n-k)
    if (k > n - k)
        k = n - k;
 
    // Calculate value of [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]
    for (int i = 0; i < k; ++i)
    {
        res *= (n - i);
        res /= (i + 1);
    }
 
    return res;
}
 
 
// A Binomial coefficient based function to find nth catalan
// number in O(n) time
unsigned long int catalan(unsigned int n)
{
    // Calculate value of 2nCn
    unsigned long int c = binomialCoeff(2*n, n);
 
    // return 2nCn/(n+1)
    return c/(n+1);
}
 
// A function to count number of BST with n nodes
// using catalan
unsigned long int countBST(unsigned int n)
{
    // find nth catalan number
    unsigned long int count = catalan(n);
 
    // return nth catalan number
    return count;
}
 
// A function to count number of binary trees with n nodes
unsigned long int countBT(unsigned int n)
{
    // find count of BST with n numbers
    unsigned long int count = catalan(n);
 
    // return count * n!
    return count * factorial(n);
}
 
// Driver Program to test above functions
int main()
{
 
    int count1,count2, n = 5;
 
    // find count of BST and binary trees with n nodes
        count1 = countBST(n);
        count2 = countBT(n);
     
    // print count of BST and binary trees with n nodes
    cout<<"Count of BST with "<<n<<" nodes is "<<count1<<endl;
        cout<<"Count of binary trees with "<<n<<" nodes is "<<count2;
 
    return 0;
}

// See https://www.geeksforgeeks.org/program-nth-catalan-number/
// for reference of below code.
import java.io.*;
 
class GFG
{
     
// A function to find
// factorial of a given number
static int factorial(int n)
{
    int res = 1;
 
    // Calculate value of
    // [1*(2)*---*(n-k+1)] /
    // [k*(k-1)*---*1]
    for (int i = 1; i <= n; ++i)
    {
        res *= i;
    }
 
    return res;
}
 
static int binomialCoeff(int n,
                         int k)
{
    int res = 1;
 
    // Since C(n, k) = C(n, n-k)
    if (k > n - k)
        k = n - k;
 
    // Calculate value of
    // [n*(n-1)*---*(n-k+1)] /
    // [k*(k-1)*---*1]
    for (int i = 0; i < k; ++i)
    {
        res *= (n - i);
        res /= (i + 1);
    }
 
    return res;
}
 
 
// A Binomial coefficient
// based function to find
// nth catalan number in
// O(n) time
static int catalan( int n)
{
     
    // Calculate value of 2nCn
    int c = binomialCoeff(2 * n, n);
 
    // return 2nCn/(n+1)
    return c / (n + 1);
}
 
// A function to count number of
// BST with n nodes using catalan
static int countBST( int n)
{
    // find nth catalan number
    int count = catalan(n);
 
    // return nth catalan number
    return count;
}
 
// A function to count number
// of binary trees with n nodes
static int countBT(int n)
{
    // find count of BST
    // with n numbers
    int count = catalan(n);
 
    // return count * n!
    return count * factorial(n);
}
 
// Driver Code
public static void main (String[] args)
{
    int count1, count2, n = 5;
 
    // find count of BST and
    // binary trees with n nodes
    count1 = countBST(n);
    count2 = countBT(n);
 
    // print count of BST and
    // binary trees with n nodes
    System.out.println("Count of BST with "+
                            n +" nodes is "+
                                    count1);
    System.out.println("Count of binary " +
                             "trees with "+
                         n + " nodes is " +
                                   count2);
}
}
 
// This code is contributed by ajit

# See https:#www.geeksforgeeks.org/program-nth-catalan-number/
# for reference of below code.
 
# A function to find factorial of a given number
def factorial(n) :
    res = 1
     
    # Calculate value of [1*(2)*---*
    #(n-k+1)] / [k*(k-1)*---*1]
    for i in range(1, n + 1):
        res *= i
    return res
 
def binomialCoeff(n, k):
 
    res = 1
 
    # Since C(n, k) = C(n, n-k)
    if (k > n - k):
        k = n - k
 
    # Calculate value of [n*(n-1)*---*(n-k+1)] /
    # [k*(k-1)*---*1]
    for i in range(k):
     
        res *= (n - i)
        res //= (i + 1)
     
    return res
 
# A Binomial coefficient based function to
# find nth catalan number in O(n) time
def catalan(n):
 
    # Calculate value of 2nCn
    c = binomialCoeff(2 * n, n)
 
    # return 2nCn/(n+1)
    return c // (n + 1)
 
# A function to count number of BST
# with n nodes using catalan
def countBST(n):
 
    # find nth catalan number
    count = catalan(n)
 
    # return nth catalan number
    return count
 
# A function to count number of binary
# trees with n nodes
def countBT(n):
 
    # find count of BST with n numbers
    count = catalan(n)
 
    # return count * n!
    return count * factorial(n)
 
# Driver Code
if __name__ == '__main__':
 
    n = 5
 
    # find count of BST and binary
    # trees with n nodes
    count1 = countBST(n)
    count2 = countBT(n)
 
    # print count of BST and binary trees with n nodes
    print("Count of BST with", n, "nodes is", count1)
    print("Count of binary trees with", n,
                       "nodes is", count2)
 
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)

// See https://www.geeksforgeeks.org/program-nth-catalan-number/
// for reference of below code.
using System;
 
class GFG
{
     
// A function to find
// factorial of a given number
static int factorial(int n)
{
    int res = 1;
 
    // Calculate value of
    // [1*(2)*---*(n-k+1)] /
    // [k*(k-1)*---*1]
    for (int i = 1; i <= n; ++i)
    {
        res *= i;
    }
 
    return res;
}
 
static int binomialCoeff(int n,
                         int k)
{
    int res = 1;
 
    // Since C(n, k) = C(n, n-k)
    if (k > n - k)
        k = n - k;
 
    // Calculate value of
    // [n*(n-1)*---*(n-k+1)] /
    // [k*(k-1)*---*1]
    for (int i = 0; i < k; ++i)
    {
        res *= (n - i);
        res /= (i + 1);
    }
 
    return res;
}
 
// A Binomial coefficient
// based function to find
// nth catalan number in
// O(n) time
static int catalan(int n)
{
     
    // Calculate value
    // of 2nCn
    int c = binomialCoeff(2 * n, n);
 
    // return 2nCn/(n+1)
    return c / (n + 1);
}
 
// A function to count
// number of BST with
// n nodes using catalan
static int countBST(int n)
{
    // find nth catalan number
    int count = catalan(n);
 
    // return nth catalan number
    return count;
}
 
// A function to count number
// of binary trees with n nodes
static int countBT(int n)
{
    // find count of BST
    // with n numbers
    int count = catalan(n);
 
    // return count * n!
    return count * factorial(n);
}
 
// Driver Code
static public void Main ()
{
    int count1, count2, n = 5;
     
    // find count of BST 
    // and binary trees
    // with n nodes
    count1 = countBST(n);
    count2 = countBT(n);
     
    // print count of BST and
    // binary trees with n nodes
    Console.WriteLine("Count of BST with "+
                           n +" nodes is "+
                                   count1);
    Console.WriteLine("Count of binary " +
                            "trees with "+
                        n + " nodes is " +
                                   count2);
    }
}
 
// This code is contributed
// by akt_mit

<?php
// See https://www.geeksforgeeks.org/program-nth-catalan-number/
// for reference of below code.
// A function to find factorial
// of a given number
function factorial($n)
{
    $res = 1;
 
    // Calculate value of
    // [1*(2)*---*(n-k+1)] /
    // [k*(k-1)*---*1]
    for ($i = 1; $i <= $n; ++$i)
    {
        $res *= $i;
    }
 
    return $res;
}
 
function binomialCoeff($n, $k)
{
    $res = 1;
 
    // Since C(n, k) = C(n, n-k)
    if ($k > $n - $k)
        $k = $n - $k;
 
    // Calculate value of
    // [n*(n-1)*---*(n-k+1)] /
    // [k*(k-1)*---*1]
    for ($i = 0; $i < $k; ++$i)
    {
        $res *= ($n - $i);
        $res = (int)$res / ($i + 1);
    }
 
    return $res;
}
 
// A Binomial coefficient
// based function to find
// nth catalan number in
// O(n) time
function catalan($n)
{
    // Calculate value of 2nCn
    $c = binomialCoeff(2 * $n, $n);
 
    // return 2nCn/(n+1)
    return (int)$c / ($n + 1);
}
 
// A function to count
// number of BST with
// n nodes using catalan
function countBST($n)
{
    // find nth catalan number
    $count = catalan($n);
 
    // return nth
    // catalan number
    return $count;
}
 
// A function to count
// number of binary
// trees with n nodes
function countBT($n)
{
    // find count of
    // BST with n numbers
    $count = catalan($n);
 
    // return count * n!
    return $count *
           factorial($n);
}
 
// Driver Code
$count1;
$count2;
$n = 5;
 
// find count of BST and
// binary trees with n nodes
$count1 = countBST($n);
$count2 = countBT($n);
 
// print count of BST and
// binary trees with n nodes
echo "Count of BST with " , $n ,
     " nodes is ", $count1,"\n";
      
echo "Count of binary trees with " ,
           $n ," nodes is ",$count2;
 
// This code is contributed by ajit
?>

<script>
 
// See https://www.geeksforgeeks.org/program-nth-catalan-number/
// for reference of below code.
 
    // A function to find
    // factorial of a given number
    function factorial(n)
    {
        let res = 1;
 
        // Calculate value of
        // [1*(2)*---*(n-k+1)] /
        // [k*(k-1)*---*1]
        for (let i = 1; i <= n; ++i)
        {
            res *= i;
        }
 
        return res;
    }
 
    function binomialCoeff(n, k)
    {
        let res = 1;
 
        // Since C(n, k) = C(n, n-k)
        if (k > n - k)
            k = n - k;
 
        // Calculate value of
        // [n*(n-1)*---*(n-k+1)] /
        // [k*(k-1)*---*1]
        for (let i = 0; i < k; ++i)
        {
            res *= (n - i);
            res /= (i + 1);
        }
 
        return res;
    }
 
    // A Binomial coefficient
    // based function to find
    // nth catalan number in
    // O(n) time
    function catalan(n)
    {
 
        // Calculate value
        // of 2nCn
        let c = binomialCoeff(2 * n, n);
 
        // return 2nCn/(n+1)
        return c / (n + 1);
    }
 
    // A function to count
    // number of BST with
    // n nodes using catalan
    function countBST(n)
    {
        // find nth catalan number
        let count = catalan(n);
 
        // return nth catalan number
        return count;
    }
 
    // A function to count number
    // of binary trees with n nodes
    function countBT(n)
    {
        // find count of BST
        // with n numbers
        let count = catalan(n);
 
        // return count * n!
        return count * factorial(n);
    }
       
    let count1, count2, n = 5;
       
    // find count of BST 
    // and binary trees
    // with n nodes
    count1 = countBST(n);
    count2 = countBT(n);
       
    // print count of BST and
    // binary trees with n nodes
    document.write("Count of BST with "+
                           n +" nodes is "+
                                   count1 + "</br>");
    document.write("Count of binary " +
                            "trees with "+
                        n + " nodes is " +
                                   count2);
                                    
</script>

Producción: 

Count of BST with 5 nodes is 42
Count of binary trees with 5 nodes is 5040

Prueba de Enumeración

Considere todos los árboles de búsqueda binarios posibles con cada elemento en la raíz. Si hay n Nodes, entonces para cada opción de Node raíz, hay n – 1 Nodes no raíz y estos Nodes no raíz deben dividirse en aquellos que son menores que una raíz elegida y aquellos que son mayores que la raíz elegida .

Digamos que se elige el Node i para que sea la raíz. Luego hay i – 1 Nodes más pequeños que i y n – i Nodes más grandes que i. Para cada uno de estos dos conjuntos de Nodes, existe un cierto número de subárboles posibles.

Sea t(n) el número total de BST con n Nodes. El número total de BST con i en la raíz es t(i – 1) t(n – i). Los dos términos se multiplican juntos porque los arreglos en los subárboles izquierdo y derecho son independientes. Es decir, para cada arreglo en el árbol de la izquierda y para cada arreglo en el árbol de la derecha, obtienes un BST con i en la raíz.

Sumar sobre i da el número total de árboles de búsqueda binarios con n Nodes.

El caso base es t(0) = 1 y t(1) = 1, es decir, hay un BST vacío y hay un BST con un Node.

Además, la relación cuentaBT(n) = cuentaBST(n) * n! sostiene En cuanto a cada BST posible, puede haber n! árboles binarios donde n es el número de Nodes en BST. 

Este artículo es una contribución de Shubham Agarwal. Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org . Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.