Binärbäume ausgleichen

[DocJunioR]

Also ich hab nen schööönen Binärbaum der jeden Gärtner zum Verzweifeln bringt. was für Strategien (Algorithmen) gibts denn, um diesen gelegentlich auszugleichen?
Der Baum ist übrigens eine Liste von Strings.
Wären es Integer-Werte, würd ich ja einfach den größten und den kleinsten Wert nehmen und dann einen Wert suchen, der ungefähr dem Mittelwert zwischen beiden entspricht.. Bei Worten ist das allerdings ein wenig unpraktisch..

[b7f7]

http://de.wikipedia.org/wiki/Binärbaum
mal den links nachschleichen
bei Strings gibt es ja auch Sortierpredikate !?

[C++ Forumbot]

Dieser Thread wurde von Moderator/in HumeSikkins aus dem Forum C++ in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

[zufaulzumeinloggen]

Google mal nach AVL Tree oder Red-Black Tree. Sollte auch einiges mit praktischen Beispielen zu finden sein.

Grüße Joe_M.

[volkardus]

DocJunioR schrieb:

Also ich hab nen schööönen Binärbaum der jeden Gärtner zum Verzweifeln bringt. was für Strategien (Algorithmen) gibts denn, um diesen gelegentlich auszugleichen?

unzählige. schau auf jeden fall neben bayer-bäumen, rot-schwarz-baumen und tries auch spreizbäume an. die haben zum teil wunderbare eigenschaften.

Der Baum ist übrigens eine Liste von Strings.

sag das doch gleich. wirf sofort deinen baum weg und mach nen TST draus. der ist unglaublich stabil gegen schieflagen, so daß man normalerweise nichtmal ballancieren muss. und der fetzt in der performance sogar hashtables weg.

nen anständigen TST zu implementieren wird wohl mein nächstes c++-projekt.

[unwissender 42]

Wofür steht den bitte die Abkürzung "TST" ?

[Walli]

Ich tippe mal auf "Ternary Search Tree" .