NF II, WS 1997/98: Lösungsblatt 9

Aufgabe 1

Keine einheitliche Lösung verfügbar.

Aufgabe 2

Der einfache Fall ist der des leeren Baumes, der nämlich keinen Knoten enthält:

no_of_nodes( nil, 0).

Die Rekursion läuft über die Teilbäume, die an einem Knoten hängen. Beachten Sie, daß hier zum ersten Mal in den Übungen eine nichtlineare Rekursion vorliegt.

no_of_nodes( node( _, Left, Right), No) :- 
  no_of_nodes( Left, LeftNodes),
  no_of_nodes( Right, RightNodes),
  No is LeftNodes + RightNodes + 1.

an beachte außerdem, daß dieses Prädikat nur sehr beschränkt dazu geeignet ist, binäre Bäume zu produzieren.

Aufgabe 3

Auch hier wieder der einfache Fall zuerst: Wenn der Ursprungsbaum leer ist, dann besteht der neue Baum aus genau einem Knoten, nämlich dem, der eingefügt wurde.

insert_name( nil, Name, node( Name, nil, nil)).

Schwieriger wird es, wenn der zu betrachtende Knoten nicht leer ist. Dann müssen drei Fälle betrachtet werden. Falls der einzufügende Name kleiner als der Schlüssel des Knotens ist, muß in den linken Teilbaum eingefügt werden. Ist er größer als der Wert, muß rechts eingefügt werden. Ist er gleich, so passiert überhaupt nichts.

insert_name( node( Key, OldLeft, Right), Name, node( Key, NewLeft, Right)) :-
  Name @< Key,
  insert_name( OldLeft, Name, NewLeft).
insert_name( node( Key, Left, OldRight), Name, node( Key, Left, NewRight)) :-
  Name @> Key,
  insert_name( OldRight, Name, NewRight).
insert_name( node( Key, Left, Right), Key, node( Key, Left, Right)).

Die außerlogischen Prädikate assert und retract können dazu benutzt werden, die eingegebenen Daten dauerhaft in der Datenbasis zu verankern.

mytree(nil).
insert_into_tree( Name) :-
  retract( mytree( Tree)),
  insert_name( Tree, Name, NewTree),
  assert( mytree( NewTree)),
  write( NewTree).

Aufgabe 4

Normalerweise würde man sagen, die Komplexität der Suche in binären Bäumen ist logarithmisch. Warum? Auf der ersten Stufe befindet sich ein Knoten, auf der zweiten Stufe vier, auf der dritten Stufe acht, etc. Auf der n-ten Stufe befinden sich 2^(n-1) Knoten. Ein baum der Höhe h hat folglich 1+2+4+...+2^(n-1) = 2^n-1 Knoten, für deren Absuchen aber nur n Operationen erforderlich sind. Andersrum: Hat ein baum k Knoten, so sind log(k) Operationen zu dessen Absuchen notwendig.

Der lineare Fall tritt auf, wenn einer der Teilbäume an jedem Knoten leer ist (ein sog. entarteter Baum). Man kann ihn z.B. durch folgende Anfragen erzeugen:

insert_into_tree( gustav).
insert_into_tree( marion).
insert_into_tree( monika).
insert_into_tree( ortrud).
insert_into_tree( stefan).
insert_into_tree( tamara).
insert_into_tree( viktor).
insert_into_tree( vogon).

Der erzeugte Baum sieht dann so aus:

node(gustav, 
     nil, 
     node(marion, 
          nil, 
          node(monika, 
               nil, 
               node(ortrud, 
                    nil, 
                    node(stefan, 
                         nil, 
                         node(tamara, 
                              nil, 
                              node(viktor, 
                                   nil, 
                                   node(vogon, 
                                        nil, 
                                        nil))))))))

er entspricht damit eher einer Liste als einem vernünftigen Baum. Das kann man verhindern, indem man fordert, daß die Anzahl der Knoten auf der linken und rechten Seite eines Knotens immer ungefähr gleich sind. Das Ergebnis davon sind sog. ausgeglichene Suchbäume. Mehr dazu z.B. in Wirth; Algorithmen und Datenstrukturen.