Рубрики

Общее количество возможных деревьев двоичного поиска и двоичных деревьев с n ключами

Общее количество возможных деревьев бинарного поиска с n разными ключами (countBST (n)) = каталонское число Cn = (2n)! / ((n + 1)! * n!)

Для n = 0, 1, 2, 3,… значения каталонских чисел равны 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,…. Так же, как и номера деревьев двоичного поиска.

Общее количество возможных двоичных деревьев с n различными ключами (countBT (n)) = countBST (n) * n!

Ниже приведен код для определения количества BST и двоичных деревьев с n числами. Код для поиска n-го каталонского номера взят отсюда .

C ++

// см. Https://www.geeksforgeeks.org/program-nth-catalan-number/amp/
// для ссылки на приведенный ниже код.

  
#include <bits/stdc++.h>

using namespace std;

  
// Функция для поиска факториала данного числа

unsigned long int factorial(unsigned int n)

{

    unsigned long int res = 1;

  

    // Рассчитать значение [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;

  

    // Поскольку C (n, k) = C (n, nk)

    if (k > n - k)

        k = n - k;

  

    // Рассчитать значение [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;

}

  

  
// Функция на основе биномиального коэффициента для поиска n-го каталонского
// число за O (n) время

unsigned long int catalan(unsigned int n)

{

    // Рассчитать значение 2nCn

    unsigned long int c = binomialCoeff(2*n, n);

  

    // вернуть 2nCn / (n + 1)

    return c/(n+1);

}

  
// Функция для подсчета количества BST с n узлами
// используя каталанский

unsigned long int countBST(unsigned int n)

{

    // найти номер каталонца

    unsigned long int count = catalan(n);

  

    // возвращаем каталонское число

    return count;

}

  
// Функция для подсчета количества двоичных деревьев с n узлами

unsigned long int countBT(unsigned int n)

{

    // найти количество BST с n числами

    unsigned long int count = catalan(n);

  

    // возвращаем количество * n!

    return count * factorial(n);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

  

    int count1,count2, n = 5;

  

    // найти количество BST и двоичных деревьев с n узлами

        count1 = countBST(n);

        count2 = countBT(n); 

      

    // выводим счетчик BST и двоичных деревьев с n узлами

    cout<<"Count of BST with "<<n<<" nodes is "<<count1<<endl;

        cout<<"Count of binary trees with "<<n<<" nodes is "<<count2;

  

    return 0;

}

Джава

// см. Https://www.geeksforgeeks.org/program-nth-catalan-number/amp/
// для ссылки на приведенный ниже код.

import java.io.*;

  

class GFG 

{

      
// Функция для поиска
// факториал заданного числа

static int factorial(int n)

{

    int res = 1;

  

    // Рассчитать значение

    // [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;

  

    // Поскольку C (n, k) = C (n, nk)

    if (k > n - k)

        k = n - k;

  

    // Рассчитать значение

    // [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;

}

  

  
// Биномиальный коэффициент
// основанная функция для поиска
// каталонский номер
// Вовремя

static int catalan( int n)

{

      

    // Рассчитать значение 2nCn

    int c = binomialCoeff(2 * n, n);

  

    // вернуть 2nCn / (n + 1)

    return c / (n + 1);

}

  
// Функция для подсчета количества
// BST с n узлами, использующими каталанский

static int countBST( int n)

{

    // найти номер каталонца

    int count = catalan(n);

  

    // возвращаем каталонское число

    return count;

}

  
// Функция для подсчета числа
// двоичных деревьев с n узлами

static int countBT(int n)

{

    // найти количество BST

    // с n числами

    int count = catalan(n);

  

    // возвращаем количество * n!

    return count * factorial(n);

}

  
// Код драйвера

public static void main (String[] args)

{

    int count1, count2, n = 5;

  

    // найти количество BST и

    // двоичные деревья с n узлами

    count1 = countBST(n);

    count2 = countBT(n); 

  

    // выводим счетчик BST и

    // двоичные деревья с n узлами

    System.out.println("Count of BST with "

                            n +" nodes is "

                                    count1);

    System.out.println("Count of binary "

                             "trees with "

                         n + " nodes is "

                                   count2);

}
}

  
// Этот код предоставлен ajit

python3

# См. Https: # www.geeksforgeeks.org / program-nth-catalan-number /
# для ссылки ниже кода.

  
# Функция для поиска факториала заданного числа

def factorial(n) :

    res = 1

      

    # Рассчитать значение [1 * (2) * --- *

    # (n-k + 1)] / [k * (k-1) * --- * 1]

    for i in range(1, n + 1): 

        res *=

    return res 

  

def binomialCoeff(n, k): 

  

    res = 1

  

    # Так как C (n, k) = C (n, nk)

    if (k > n - k): 

        k = n -

  

    # Рассчитать значение [n * (n-1) * --- * (n-k + 1)] /

    # [k * (k-1) * --- * 1]

    for i in range(k): 

      

        res *= (n - i) 

        res //= (i + 1

      

    return res 

  
# Функция на основе биномиального коэффициента для
# найти n-е каталонское число за O (n) время

def catalan(n):

  

    # Рассчитать значение 2nCn

    c = binomialCoeff(2 * n, n) 

  

    # return 2nCn / (n + 1)

    return c // (n + 1

  
# Функция для подсчета количества BST
# с n узлами, использующими каталанский

def countBST(n):

  

    # найти номер каталонца

    count = catalan(n) 

  

    # вернуть n каталонский номер

    return count 

  
# Функция для подсчета количества двоичных файлов
# деревьев с n узлами

def countBT(n):

  

    # найти количество BST с n номерами

    count = catalan(n) 

  

    # возвращаемое количество * n!

    return count * factorial(n) 

  
Код водителя

if __name__ == '__main__':

  

    n = 5

  

    # найти количество BST и двоичный

    # деревьев с n узлами

    count1 = countBST(n) 

    count2 = countBT(n) 

  

    # вывести количество BST и двоичных деревьев с n узлами

    print("Count of BST with", n, "nodes is", count1) 

    print("Count of binary trees with", n, 

                       "nodes is", count2)

  
# Этот код предоставлен
# Шубхам Сингх (SHUBHAMSINGH10)

C #

// см. Https://www.geeksforgeeks.org/program-nth-catalan-number/amp/
// для ссылки на приведенный ниже код.

using System;

  

class GFG

{

      
// Функция для поиска
// факториал заданного числа

static int factorial(int n)

{

    int res = 1;

  

    // Рассчитать значение

    // [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;

  

    // Поскольку C (n, k) = C (n, nk)

    if (k > n - k)

        k = n - k;

  

    // Рассчитать значение

    // [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;

}

  
// Биномиальный коэффициент
// основанная функция для поиска
// каталонский номер
// Вовремя

static int catalan(int n)

{

      

    // Рассчитать значение

    // из 2nCn

    int c = binomialCoeff(2 * n, n);

  

    // вернуть 2nCn / (n + 1)

    return c / (n + 1);

}

  
// Функция для подсчета
// номер BST с
// n узлов, использующих каталанский

static int countBST(int n)

{

    // найти номер каталонца

    int count = catalan(n);

  

    // возвращаем каталонское число

    return count;

}

  
// Функция для подсчета числа
// двоичных деревьев с n узлами

static int countBT(int n)

{

    // найти количество BST

    // с n числами

    int count = catalan(n);

  

    // возвращаем количество * n!

    return count * factorial(n);

}

  
// Код драйвера

static public void Main ()

{

    int count1, count2, n = 5;

      

    // найти количество BST

    // и бинарные деревья

    // с n узлами

    count1 = countBST(n);

    count2 = countBT(n); 

      

    // выводим счетчик BST и

    // двоичные деревья с n узлами

    Console.WriteLine("Count of BST with "

                           n +" nodes is "

                                   count1);

    Console.WriteLine("Count of binary "

                            "trees with "

                        n + " nodes is "

                                   count2);

    }

}

  
// Этот код добавлен
// от akt_mit

PHP

<?php
// см. Https://www.geeksforgeeks.org/program-nth-catalan-number/amp/
// для ссылки на приведенный ниже код.
// Функция для поиска факториала
// данного числа

function factorial($n)

{

    $res = 1;

  

    // Рассчитать значение

    // [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;

  

    // Поскольку C (n, k) = C (n, nk)

    if ($k > $n - $k)

        $k = $n - $k;

  

    // Рассчитать значение

    // [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;

}

  
// Биномиальный коэффициент
// основанная функция для поиска
// каталонский номер
// Вовремя

function catalan($n)

{

    // Рассчитать значение 2nCn

    $c = binomialCoeff(2 * $n, $n);

  

    // вернуть 2nCn / (n + 1)

    return (int)$c / ($n + 1);

}

  
// Функция для подсчета
// номер BST с
// n узлов, использующих каталанский

function countBST($n)

{

    // найти номер каталонца

    $count = catalan($n);

  

    // вернуть nth

    // каталонский номер

    return $count;

}

  
// Функция для подсчета
// номер двоичного файла
// деревья с n узлами

function countBT($n)

{

    // найти количество

    // BST с n числами

    $count = catalan($n);

  

    // возвращаем количество * n!

    return $count

           factorial($n);

}

  
// Код драйвера

$count1;

$count2;

$n = 5;

  
// найти количество BST и
// двоичные деревья с n узлами

$count1 = countBST($n);

$count2 = countBT($n); 

  
// выводим счетчик BST и
// двоичные деревья с n узлами

echo "Count of BST with " , $n ,

     " nodes is ", $count1,"\n";

       

echo "Count of binary trees with "

           $n ," nodes is ",$count2;

  
// Этот код предоставлен ajit
?>

Выход:

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

Доказательство перечисления

Рассмотрим все возможные бинарные деревья поиска с каждым элементом в корне. Если имеется n узлов, то для каждого выбора корневого узла существует n — 1 некорневых узлов, и эти некорневые узлы должны быть разделены на те, которые меньше выбранного корня, и те, которые больше выбранного корня ,

Допустим, узел i выбран в качестве корня. Тогда есть i — 1 узлов меньше, чем i и n — i узлов больше, чем i. Для каждого из этих двух наборов узлов существует определенное количество возможных поддеревьев.

Пусть t (n) будет общим количеством BST с n узлами. Общее количество BST с i в корне равно t (i — 1) t (n — i). Два слагаемых умножаются вместе, потому что расположения в левом и правом поддеревьях независимы. То есть для каждого расположения в левом дереве и для каждого расположения в правом дереве вы получаете один BST с i в корне.

Суммирование по i дает общее количество бинарных деревьев поиска с n узлами.

Базовый случай: t (0) = 1 и t (1) = 1, то есть есть один пустой BST и один BST с одним узлом.



Кроме того, отношение countBT (n) = countBST (n) * n! держит. Что касается каждого возможного BST, то здесь может быть n! двоичные деревья, где n — количество узлов в BST.

Эта статья предоставлена Shubham Agarwal. Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org . Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Общее количество возможных деревьев двоичного поиска и двоичных деревьев с n ключами

0.00 (0%) 0 votes