[infostudents] Info 2 - Uebungsblatt 11

  • From: Felix Ruzzoli <f.ruzzoli@xxxxxxxxx>
  • To: Infolist <infostudents@xxxxxxxxxxxxx>
  • Date: Mon, 9 Jul 2007 19:10:49 +0200

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi Leute..
Aufgabe 1 im Anhang..
Gibt es eigentlich einen Hinweis in der Aufgabestellung, ob man mittels
des symmetrischen Vorgaengers oder Nachfolgers entfernen soll..?
Das hat mich naemlich etwas verplant und dann hab ich beides gemacht..

Und noch nen bisserl was zur Aufgabe 2:

damit moeglichst wenig Rotationen auftreten, muessen neue Knoten dort
eingefuegt werden, wo sie entweder die Balance kaum verletzen oder die
kaum verletzte Balance wiederherstellen. D.h. Optimal waere es O.b.d.A
beim sequentiellen Einfuegen von 3 neuen Knoten, den mittleren Knoten
zuerst einzufuegen und dann einen dessen Schluessel kleiner ist und als
letztes einen dessen Schluessel groesser ist.
=> fuer n=7 4, 2, 6, 3, 5, 1, 7
Keine rotationen notwendig.

1, 2, 3, 4, 5, 6, 7
4 Rotationen
notwendig (keine doppelrotationen)

Bei Aufgabe 3 stellen sich mir noch nen paar Fragen..
Hat man nur die in der Aufgabestellung erwaehnten Funktionen lookup und
parent zur verfuegung?
Wie soll man denn dann das Rotieren realisieren?
Oder darf man davon ausgehen vollen Zugriff auf die Struktur zu haben?
Aber wie sieht das dann aus..?
Ansonsten wuerde ich vorerst naemlich sowas hier schreiben..:

Es gibt schon:
node lookup(int key)
node parent(node N)

Zu schreiben:
insert(int key, int prio) {
        node worknode = lookup(key);
        // auf gleichheit pruefen, in der aufgabenstellung
        // ist aber nicht von inhalt die rede, oder sind
        // die keys eindeutig?
        //if (worknode.content==content) return;
        if (worknode.key==key) return;
        worknode.setKey(key);
        worknode.setPriority(prio);
        while (worknode.getPriority()<parent(worknode).getPriority()) {
                //rotateUp
                // worknode should be in the position
                // of his parent afterwards..
        }
}

algo:
1. suche schluessel k, falls schon vorhanden -> fertig.
Ansonsten:
2. ersetze blatt in dem suche nach k endet durch neuen Knoten
mit Wert (k,p).
3. stelle heap bedingung wieder her.

Um kommentare wird gebeten..

mfg fx
- -- 
Felix Ruzzoli
eMail: f.ruzzoli@xxxxxxxxx oder ruzzoli@xxxxxxxxxxxxxxxxxxxxxxxxxx
Jabber: memmaker@xxxxxxxxxxxxx
ICQ: 21907473

#-----------------------------------------------------------------#

Nichts is so wie es scheint..
Alles ist erlaubt..
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFGkmwftsta2pU07v0RAhEgAKCqqNg8IJ1RJgBcYoNihgK40WxrVACdEZF+
4y2oP5w07TS6ra6W5WIMkzE=
=NmwZ
-----END PGP SIGNATURE-----

Other related posts:

  • » [infostudents] Info 2 - Uebungsblatt 11