PDA

View Full Version : Avl- Baum

feurio
19-05-2002, 23:11
hallo leute
habe mir ein fiktives beispiel überlegt und ausgerechnet.


gegeben ist eine folge
gesucht ist die balancierte AVL baum

falls jemand lust hat, kann er/sie mir dann die lösung sagen, damit ich vergleichen kann?

2,1,6,4,9,11,15,17,22,28,27,32,16,13,18


danke im voraus + viel spass dabei

wünscht euch
azadi
yrucrem
20-05-2002, 01:42
Ist ein bisschen schwer hier einen umfangreicheren Baum darzustellen. Hier ist jedenfalls die Preordertraversierung meiner Loesung: 17, 6, 2, 1, 4, 11, 9, 15, 13, 16, 27, 22, 18, 28, 32 (und wieder was zum ueben :-)).

Und hier ist der Baum ein wenig anschaulicher: AVL-Baum.png (http://stud3.tuwien.ac.at/~e0125335/pub/AVL-Baum.png).

/edit: Sorry, das Bild habe ich mal geloescht.
PliniusSecundus
20-05-2002, 12:46
Wirklich ein super Beispiel zum Üben! Zumindest auf der rechten Seite kommen so ziemlich alle Fälle wie man was rotieren und wo anders anhängen muss vor.
Danke Azadi.

PS: Ergebnis von yrucrem kann ich bestätigen.
eXe
20-05-2002, 15:09
alles LR und einmal RLR, müßte stimmen weil ich das gleiche rausbekomm :)
MrBurnst
20-05-2002, 15:45
:o
jaja, hab auch den baum rausbekommen, wird schon passen...
phlow
20-05-2002, 16:14
Nur mal zur kontrolle:

Die korrekten Inorder und Postorder Durchmusterungen für das Bsp wären dann:
Inorder: 1,2,4,6,9,11,13,15,16,17,18,22,27,28,32
Postorder: 1,4,2,13,16,15,9,11,6,18,22,32,28,27,17 ???

Bitte kann das mal wer überprüfen, bei Postorder bin ich mir sehr unsicher. thx

[edit: inorder ausgebssert, kleiner denkfehler *G*
postorder: tjo, da hab ich 2 zeilen meines notizzettels komplett vermischt beim abschreiben, habs jetzt mal korrigiert so wie ichs hatte, obs stimmt weis ich net]
#!/usr/bin/perl
20-05-2002, 16:27
also ich hab bei InOrder rausbekommen:

1 2 4 6 9 11 13 15 16 17 18 22 27 28 32

PostOrder sieht bei mir so aus:

1 4 2 9 13 16 15 11 6 18 22 32 28 27 17
phlow
20-05-2002, 16:42
thx: inorder hatte ich nen denkfehler drin, habs ausgebessert.

bei poostorder bin ich mir noch immer net sicher ;). deins schaut aber logischer aus als meins, also denk mal das das stimmt.
eXe
20-05-2002, 17:00
ich habs genauso wie perl

bei inorder muß immer eine aufsteigende zahlenfolge rauskommen :)