gewichtsbalancierte Bäume

[Laren]

Hi,

Ich schreibe bald eine Klausur und es könnte ein Thema dran kommen, was wir eigentlich nur angeschnitten hatten, aber in keiner Vorlesung ein Beispiel gebracht hat.
Es geht um gewichtsbalancierte Bäume.

c) Stellen sie grafisch einen weight-balanced und einen Minmax-tree mit Namen als „keys“ dar für die nachfolgende Menge von Knoten mit den Namen und zugehörigen Häufigkeiten: (Müller,40), (Maier,15), (Bachmann ,16), (Schneider,20), (Bolander ,1), (Ernst ,6), (Fliegner ,1), (Liebelt ,1)

Ich kann auch leider nichts finden, wie ich einen solchen Baum erstellen kann. Wäre cool wenn mir jemand helfen könnte

Grüße

 

[Laren]

Ich hab jetzt noch den Algorithmus, weis aber immer noch nicht weiter;(

Wähle die Wurzel so, dass das Maximum der Gewichte der beiden Unterbäume minimal ist, d.h. minimiere max(G(lt(x)),G(rt(x))). Verfahre rekursiv auf den Unterbäumen.

Beide Regeln wählen Wurzeln, die in der Nähe der „Mitte“ der Gewichtsverteilung liegen. Daher der Grundgedanke, dies formal als Auswahlkriterium für die Wurzel zu wählen mit rekursiver Anwendung auf die Unterbäume.

 

[SamHotte]

Google ist Dein Freund:
weight-balanced tree - Google-Suche

 

[Laren]

da hab ich schon geschaut, aber finde nicht wie ich den Baum Step for Step aufbaue.

 

[SlaterB]

Weight-balanced tree - Wikipedia, the free encyclopedia
dort wird recht einfach vorgegangen, das höchste Gewicht ist der root, dann muss nach Sortierung der Rest nach links und rechts verteilt werden,
wieder jeweils das höchste Gewicht suchen usw.

 

[Laren]

ok,danke, aber wie sieht es mit dem MinMax tree aus?

 

[Laren]

nur mal kurz sagen, wie ich die wurzel wähle und wie die Kinder beim MinMax, mehr brauch ich gar nicht:noe:

Grüße

 

[Marcinek]

Minimax-Algorithmus ? Wikipedia