Hallo, ich habe folgende Aufgabe:
Gegeben sei der folgende Suchbaum, in dem die Elemente A;B;C;D;E
lexikographisch geordnet sind. Beweisen oder widerlegen Sie:
Der Baum kann ein optimaler Suchbaum mit 2,1 erwarteten Vergleichen sein.
Da kommen ich und viele andere nicht weiter, die meisten neigen zur Meinung, dass die Aussage falsch ist. Wir haben dazu sehr viele Gleichungen aufgestellt, die aber kompliziert zu lösen scheinen: (a bis e sind die jew. Zugriffswahrscheinlichkeiten)
a+b+c+d+e=1
a+2b+4c+3d+4e=2,1
Durch die e_ij Tabellen (erwartete Anzahl Vergleiche im Unterbaum von i bis j):
b<=a, e<=d<=c
Aber ich stecke jetzt fest wie ich hier wirklich weiterkomme. Muss ich etwa noch mehr Ungleichungen/Gleichungen aufstellen?
Vielen Dank im Voraus!