具有複製密鑰的BST的數量

Question

如果存在具有與由Catalan number給出的BST的數量不同的密鑰的n個頂點。但是如果某些元素重複了我們如何計算BST的數量？

我的天真想法是，如果我們在n中有k個相等的元素，那麼我們就應該把加泰羅尼亞數分爲k！（k個元素的排列）。但是如果我們檢查一下最簡單的例子（BST基於[1,1,1]），我們意識到這是錯誤的想法。

那麼我們應該如何考慮重複鍵，當我們計算BST的數量？

什麼是BST在我的問題：二進制樹，其中左兒童的所有鍵小於根和右兒童的所有鍵磨碎或等於根。

Answer 1

的重複鍵不作出不同的樹的數量有什麼區別。每棵樹都有獨特的形狀，所以你甚至不需要鑰匙來區分它們。你可以完全刪除鑰匙，樹木仍然會有所不同。

與簡單的例子試試：[1,1,1]。您仍然可以使5個不同的BSTS這些鍵：

1  1  1  1  1 
/ / /\  \  \ 
    1  1  1 1  1  1 
/  \    /  \ 
1   1    1   1 

編輯新的要求：

如果左孩子必須嚴格比父母少，然後重複鍵形成一個鏈表就像一個節點，因爲你不能有任何剩餘的孩子。相等值的整個列表都只有一個形狀，一個左孩子和一個右子：

1 
/\ 
    0 1 
     \ 
     1 
     \ 
      2 

所以在這種情況下，你可以只減去重複鍵的數量。

對於具有M個副本的N個密鑰，即N-M個唯一密鑰，有加泰羅尼亞語（N-M）方法來製作樹。