alte Testangaben 11.12.2003 1.A

[Frusel]

gegeben ist eine buchstabenfolge...man soll sie bei punkt a.) in einen avl baum eintragen und bei punkt b.) in einen binären suchbaum

kann es sein dass die beide gleich aussschauen? ^^

mfg frusel

[oopster]

gegeben ist eine buchstabenfolge...man soll sie bei punkt a.) in einen avl baum eintragen und bei punkt b.) in einen binären suchbaum

kann es sein dass die beide gleich aussschauen? ^^

mfg frusel
nein, da du beim avl beim ja aus der balance gekommenen knoten wieder rebalanciersts! der binär baum ist viel tiefer als der avl baum.

[eva_d]

äh nein, das ist hier nicht der fall :)
beim eintragen in einen AVL-baum musst ja sofort rebalancieren, sobald der baum aus der balance gerät. bei binärbaum nicht.

[Frusel]

hmmm steht aber nichts in der angabe dass man in balancieren soll ^^
aber ich nehm mal an wenn er nicht balanciert is wäre es kein avl baum oder?

dann müsste der nicht balancierte avl baum dieser angabe gleich dem binären suchbaum sein oder?

mein binärer suchbaum wäre mit der angabe: K,G,W,E,A,M,C,U

K
/ \
G W
/ /
E M
/ \
A U
\
C
passt das?

[Georg Kraml]

hmmm steht aber nichts in der angabe dass man in balancieren soll ^^

Doch. Es steht da, dass man einen AVL-Baum basteln soll, das impliziert Balancierung.


aber ich nehm mal an wenn er nicht balanciert is wäre es kein avl baum oder?

Stimmt.


dann müsste der nicht balancierte avl baum dieser angabe gleich dem binären suchbaum sein oder?

Es gibt eben keinen "nicht balancierten" AVL-Baum.

.

[eva_d]

ja frusel, der binäre suchbaum schaut so aus, stimmt.

aber ein avl-baum ist eben ein BALANCIERTER baum. du musst nach jedem einfügen eines knotens überprüfen, ob er aus der balance geraten ist -> in diesem fall heißt es dann: rebalancieren!

[Frusel]

passt thx eva :-)
so nun sollte alles klappen morgen
wünsch euch allen viel glück ^^

[floevents]

ich hab folgende lösung

[oopster]

ich hab folgende lösung
ab ich auch so, nur warum hast du für die Anzahl der Vergleiche beim AVL auch 4 ? (warum nicht 3?, da der Baum ja niedriger ist? Täusch ich mich da,
also er vergleicht:

K mit T
U mit T und dann
M mit T

bitte schreien wenns falsch ist

lg

[clemensp]

s würd mich auch intressiern

also gleich könnens meiner meinung nach sicher nicht sein

aber:
muss man beim avl baum max 3 oder 4 vergleiche machn

4 verglecihe bräuchte man ja dann wenn man nciht weiß ob das gescuhte zeichen existiert...
aber eigntlich braucht man den 4. verglecih wenn man nach c sucht auch dann wenn man zb die tiefe vom baum nicht weiß oda ?

wenn ich aber weiß dass die tiefe 3 is und dass mein gesuchter schlüssel existiert brauch ich den letzten vergleich eigntlich nichtmehr...

hm

beim binären baum muss trotzdem ein vergleich mehr sein weil die tiefe größer is

[Septic.exe]

Muß ich da nicht nur zusätzlich in best, avg und worst unterscheiden? Weil wenn der gesuchte Schlüssel in der Wurzel steht, brauch ich ja nur 1 Vergleich ... egal ob AVL oder bS ... oder?

[oopster]

Muß ich da nicht nur zusätzlich in best, avg und worst unterscheiden? Weil wenn der gesuchte Schlüssel in der Wurzel steht, brauch ich ja nur 1 Vergleich ... egal ob AVL oder bS ... oder?
naja im dem fall nit, da der gesuchte schlüssel ein T ist, und der noch nicht im AVL baum drinnen ist

[clemensp]

asooo da steht ja e was für ein element gesucht is *patsch*

*g*

ja dann sans 3 mal fürn avl baum und 4 fürn binärn

würd i sagn :)

[Septic.exe]

Aso ... ich dachte, das wär ein beliebiges Element ... :), jo ... dann müsstens 3 Vergleiche fürn AVL sein und 4 fürn bS.

[Crow]

War Schwachsinn. sorry.