Variation der Suche nach der Anzahl der Binärbäume für eine bestimmte n Anzahl von Schlüsseln

Question

Gegeben eine Liste A von n verschiedenen Schlüsseln, wie viele binäre Suchbäume können so gebildet werden, dass in jeder Unterbaum, der Unterschied zwischen den Nummern der Knoten in seine linken und rechten Unterbäume sind bei am meisten?

Die Rekursion für die Anzahl der binären Suchbäume ohne die Bedingung

f(1) = f(0) = 1; 
Let total_trees = 0; 
for(int i = 1; i<= n; ++i) 
    total_trees += f(i-1) * f(n-i) 

jemand mit der Variation helfen?

Mein Versuch (was falsch ist):

f(1) = f(0) = 1; 
Let total_trees = 0; 
for(int i = 1; i<= n; ++i) 
    total_trees += f(i) * f(i-1) 

Answer 1

Lassen Sie sich alle Schlüssel sind in linearer Anordnung. Wenn die Anzahl der Schlüssel gerade ist, haben Sie 2 Varianten von Root - 2 zentrale Elemente. Für ungerade Anzahl von Schlüsseln gibt es nur eine Variante mit einem zentralen Element als root, um die Bedingung zu erfüllen. So Rekursion wie folgt aussieht:

f (1) = f (0) = 1

f (2 * k) = f (k-1) * f (k + 1) + f (k + 1) * f (k-1) = 2 * f (k-1) * f (k + 1)

f (2 * k + 1) = f (k) * f (k)