[자료구조] Program to find the total number of possible Binary Search Trees with n keys. feat. catalan number

원문링크 :

https://www.javatpoint.com/program-to-find-the-total-number-of-possible-binary-search-trees-with-n-keys

Program to Find the Total Number of Possible Binary Search Trees with N Keys - javatpoint

주어진 노드의 갯수로 몇개의 Binary Search Tree를 만들 수 있는지 묻는 문제이다.

The question is that how many Binary Search Trees I can construct with given nodes.

 

To find a regularities for construction of BST with specific nodes, let's observe some examples

 

Let's say a function that returns the number of BST that can make when we input the nubmer of nodes as F(n)

 

F(The number of nodes) = The number of BST that can construct

No doubt that F(1) = 1 and F(2) = 2. ( we are  also gonna say F(0) = 1)

F(3) = F(0)F(2) + F(1)F(1) + F(2)F(0) = 1*2  +  1*1  +  2*1 = 5

F(4) = F(0)F(3) + F(1)F(2) + F(2)F(1) + F(3)F(0) = 1*5  +  1*2  +  2*1  +  5*1 = 14

 

so we can express like below

and also we can write a code like below with this idea

#include <stdio.h>
#include "datastructure.h"
 
int numberofBST(int numberofNodes) {
    int *F;
    F = (int*)malloc(sizeof(int)*numberofNodes);
    F[0] = 1;
    F[1] = 1;
    for (int i = 2; i <= numberofNodes; i++) {
        int sum = 0;
        for (int j = 0; j < i; j++) {
            sum += F[j] * F[i - j - 1];
        }
        F[i] = sum;
    }
    return F[numberofNodes];
}
 
int main() {
    printf("The number of BST that can construct with %d nodes is %d\n", 5, numberofBST(5));
 
 
    return 0;
}

 

They have another function for this question in original link

The code is like below

int factorial(int num) {  
    int fact = 1;  
    if(num == 0)  
        return 1;  
    else {  
        while(num > 1) {  
            fact = fact * num;  
            num--;  
        }  
        return fact;  
    }  
}  
   
//numOfBST() will calculate the total number of possible BST by calculating Catalan Number for given key  
int numOfBST(int key) {  
    int catalanNumber = factorial(2 * key)/(factorial(key + 1) * factorial(key));  
    return catalanNumber;  
}  
      
int main(){  
      
    //Display total number of possible binary search tree with key 5  
    printf("Total number of possible Binary Search Trees with given key: %d", numOfBST(5));  
      
    return 0;  
}

It is interesting that using factorial to solve this problem

The main idea is same but the expression of it is little bit different

They simplify the equation by using combination like this

To understand this equation we should know about the Catalan Number

https://en.wikipedia.org/wiki/Catalan_number

Catalan number - Wikipedia

https://soccer-programming.tistory.com/18

카탈란수(catalan number)