Có thể xây dựng bao nhiêu cây tìm kiếm nhị phân từ n thành phần riêng biệt? Và làm thế nào chúng ta có thể tìm thấy một công thức toán học được chứng minh cho nó?Số cây tìm kiếm nhị phân trên n thành phần riêng biệt
Ví dụ: Nếu chúng ta có 3 yếu tố riêng biệt, nói 1, 2, 3, có 5 cây tìm kiếm nhị phân.
Với n yếu tố, số lượng cây tìm kiếm nhị phân có thể được làm từ những yếu tố được đưa ra bởi các thứ n Catalan number (ký hiệu là C n). Đây là bằng
trực giác, những con số Catalan đại diện cho số cách mà bạn có thể tạo ra một cấu trúc bằng các phần tử n được làm theo cách sau:
Mẫu này hoàn toàn phù hợp với cách bạn có thể tạo BST từ bộ phần tử n. Chọn một phần tử để sử dụng làm gốc của cây. Tất cả các phần tử nhỏ hơn phải chuyển sang bên trái và tất cả các phần tử lớn hơn phải chuyển sang bên phải. Từ đó, bạn có thể xây dựng các BST nhỏ hơn từ các phần tử bên trái và bên phải, sau đó kết hợp chúng lại với nút gốc để tạo thành một BST tổng thể. Số cách bạn có thể thực hiện việc này với các phần tử n được đưa ra bởi C n và do đó số lượng BST có thể được cho bởi số Catalan thứ n.
Hy vọng điều này sẽ hữu ích!
Ví dụ cho các nút 10, 10, 10 số cây tìm kiếm nhị phân là 1. Nhưng số Catalan là 5. Nhưng nếu tất cả các phần tử khác thì không sao đâu. –
@ SukhanovNiсkolay Số BST vẫn là 5 cho 10,10,10. Hình dạng cây sẽ khác nhau. – rents
Cho T (n) là số bsts của phần tử n.
Với n yếu tố được sắp xếp riêng biệt, được đánh số từ 1 đến n, chúng tôi chọn tôi làm gốc.
Lá này (1..i-1) trong cây con trái cho các kết hợp T (i-1) và (i + 1..n) trong cây con phù hợp cho các kết hợp T (n-i).
Do đó:
T(n) = sum_i=1^n(T(i-1) * T(n-i))
và dĩ nhiên là T (1) = 1
Nó có thể là tốt để đề cập đến rằng sự tái diễn này giải quyết đến số thứ Catalan. – templatetypedef
@templatetypedef: Bạn có biết cách lấy công thức số của catalan bắt đầu từ số tiền tôi đã hiển thị không? –
@ user1131467 Tổng này phải chính xác số lượng tam giác của đa giác trên các nút n + 2, đó là cách tôi được giới thiệu với số Catalan. Bạn sửa một cạnh và để trục đi qua các đỉnh n khác, khiến bạn có hai đa giác kích cỡ i-1 và n-i. –
Tôi chắc chắn câu hỏi này không chỉ là để đếm sử dụng một công thức toán học .. Tôi đã diễn ra một thời gian và đã viết chương trình và giải thích hoặc ý tưởng đằng sau tính toán cho cùng một.
Tôi đã thử giải quyết nó bằng cả chương trình đệ quy và động. Hi vọng điêu nay co ich.
Công thức đã có mặt trong các câu trả lời trước:
Vì vậy, nếu bạn muốn tìm hiểu các giải pháp và tìm hiểu apporach bạn luôn có thể kiểm tra bài viết của tôi Count Binary Search Trees created from N unique elements
lẽ [liên quan] (http: // stackoverflow.com/questions/3042412/with-n-no-of-nodes-how-many-different-binary-and-binary-search-trees-possib). –