Liczba BST z powielonymi kluczami - algorytm, matematyka, drzewo, drzewo binarne-wyszukiwania, dynamiczne programowanie

Jeśli istnieje n wierzchołka z różnymi kluczami niż liczba BST podana przez Numer kataloński. Ale jeśli niektóre elementy są zduplikowane, możemy policzyć liczbę BST?

Mój naiwny pomysł, że jeśli mamy k równych elementówwśród n, powinniśmy podzielić kataloński numer na k! (permutacje k elementów). Ale jeśli sprawdzimy to na najprostszym przykładzie (kompilacja BST [1, 1, 1]), zdajemy sobie sprawę, że to zły pomysł.

Jak więc wziąć pod uwagę zduplikowane klucze, gdy liczymy liczbę BST?

Co to jest BST w moim pytaniu: drzewo binarne, w którym wszystkie klawisze w lewym dziecku są mniejsze niż w korzeniu, a w prawym dziecku wszystkie klucze są większe lub równe niż w katalogu głównym.

Odpowiedzi:

Zduplikowane klawisze nie mają znaczenialiczba różnych drzew. Każde drzewo ma wyraźny kształt, więc nie potrzebujesz nawet kluczy, aby je rozróżnić. Możesz usunąć klucze całkowicie, a drzewa nadal będą różne.

Wypróbuj za pomocą prostego przykładu: [1,1,1]. Za pomocą tych kluczy nadal możesz utworzyć 5 różnych BST:

    1      1      1      1      1
/      /      /             
1      1      1   1      1      1
/                       /        
1          1             1          1

EDIT dla nowych wymagań:

Jeśli lewe dzieci muszą być ściśle mniejsze niżich rodzice, a następnie duplikaty kluczy tworzą listę połączoną, która działa jak pojedynczy węzeł, ponieważ nie można w niej pozostawić żadnych dzieci. Cała lista równych wartości będzie miała tylko jeden kształt, jedno lewe dziecko i jedno prawe dziecko:

    1
/ 
0   1

1

2

W tym przypadku możesz po prostu odjąć liczbę zduplikowanych kluczy.

Dla N kluczy z M duplikatów, tj. N-M unikalnych kluczy, istnieją katalońskie (N-M) sposoby tworzenia drzewa.