Chương trình đếm số cây BST với n nút trong Python

Giả sử chúng ta có n nút khác nhau. Tất cả đều phân biệt. Chúng ta phải tìm số cách sắp xếp chúng để thành cây tìm kiếm nhị phân. Như chúng ta biết, với cây tìm kiếm nhị phân, cây con trái luôn chứa giá trị nhỏ hơn và cây con phải chứa giá trị lớn hơn.

Để giải quyết vấn đề này, chúng ta sẽ tìm số Catalan. Số Catalan C(n) đại diện cho số cây tìm kiếm nhị phân với n khóa khác nhau. Công thức như sau:

$$C(n)=\frac{(2n)!}{(n+1)!\times n!}$$

Vì vậy, nếu đầu vào là n = 3, thì đầu ra sẽ là 5 vì:

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau:

Định nghĩa hàm ncr(). Hàm này nhận n, r
res := 1
nếu r > n - r, thì r := n - r
với i từ 0 đến r - 1, thực hiện
- res := res * (n - i)
- res := phần nguyên của res/(i + 1)
trả về res
Từ phương thức chính, thực hiện
c := ncr(2 * n, n)
trả về phần nguyên của c /(n + 1)

Ví dụ

Hãy xem triển khai sau để hiểu rõ hơn:

from math import factorial
def ncr(n, r):
    res = 1
    if r > n - r:
        r = n - r
    for i in range(r):
        res *= (n - i)
        res //= (i + 1)
    return res

def solve(n):
    c = ncr(2 * n, n)
    return c // (n + 1)

n = 3
print(solve(n))

Chương trình đếm số cây BST với n nút trong Python

Ví dụ

Đầu vào

Đầu ra