查找可能的二元查找樹的數量

Question

假設我們有密鑰1,2,3,4,5,6,7。我必須找到可能的二叉搜索樹的總數，使得二叉搜索樹的高度爲6。

答案是。但我無法找到一種模式，以便從數學上推導出答案。僅僅通過蠻力繪製所有可能的樹木是不可能的。

可能的樹的一個簡單例子是傾斜的不平衡樹，其中按照升序和降序插入密鑰。兩棵樹的高度都是6.但是如何達到總和64？

Answer 1

這可以通過施工來證明。

比方說，
F（n）的用於n+1號碼
要求用高度n二叉查找樹的=編號：F(n) = 2^n

證明：

F(0) = 1 (by construction) 
F(1) = 2 (by construction) 

現在，計算F（N ），那麼最小的數字或最大的數字可以是樹的根。剩餘的正數將不得不被安排在左子樹（如果數量最多的是root），或右（如果最小的數字是根）

所以，

F(n) = 2*F(n-1) 
F(n) = 2^n