Übungen zu Collections (KW 17)

(Fortsetzung der Übung zu Suchbäumen)

• Methode add (Einfügen in Suchbaum), contains (Enthaltensein im Suchbaum).

  class Tree<E extends Comparable<E>> { ...
          public void add (E x) { ... }
          public void addAll (Collection<E> c) { ... } // nur 3 Zeilen
          public boolean contains (E x) { ... }
  }
  class Entry<E> { ...
          static <E extends Comparable<E>> Entry<E> add (Entry<E> e, E x) { ... }
  }
  

  und teste:

  class TreeTest {
          public static void addTest () {
                  System.out.println ("addTest");
                  String [] words = { "foo", "bar", "baz" };
                  Tree<String> t = new Tree<String> ();
                  for (String w : words) {
                          System.out.println ("add: " + w);
                          t.add (w);
                          System.out.println (t);
                  }
          }
  }
  

• wie lauten die Spezifikationen von add und contains? Hinweis: reicht der folgende Test aus?

  class TreeTest { ...
          public static void containsTest () {
                  System.out.println ("containsTest");
                  List<Double> l = generate (10);
                  Tree<Double> t = new Tree<Double> ();
                  t.addAll (l);
                  for (Double d : l) {
                          boolean result = t.contains (d);
                          System.out.println (d + " : " + result);
                  }               
          }
  
          static List<Double> generate (int size) {
                  List<Double> result = new LinkedList<Double> ();
                  for (int i=0; i<size; i++) {
                        result.add (Math.random());
                  }
                  return result;
          }
  }
  

• Wie beweist man, daß die Implementierungen tatsächlich die Spezifikationen erfüllen? Welche Eigenschaften der durch equals und compareTo definierten Relationen werden bei add und contains vorausgesetzt? Beantworte anhand des Quelltextes!

• liefere Liste der Schlüssel in Inorder-Reihenfolge, soll so benutzt werden:

          Tree<Integer> t = Tree.full (2);
          List<Integer> l = t.toList();
          System.out.println (l);
  

  Deklaration (sichtbar):

  class Tree<E extends Comparable<E>> {
         ...
          public List<E> toList () {
                  List <E> l = new LinkedList<E> ();
                  Entry.addToList (l, root);
                  return l;
         }
  }
  

  Implementiere die passende Methode:

  class Entry<E> { ...
          static <E> void addToList (List<E> l, Entry<E> e) { ... }
  }
  

• Benutze add zum Sortieren (Ausgabe mit toList).

  class Sort {
      public static <E extends Comparable<E>> List<E> 
                    tree_sort (List <E> input) { ... } // nur 3 Zeilen
  }
  

• vergleiche die Leistung der selbstgebauten Suchbaum-Implementierung:

  List<Double> in = generate (10);
  List<Double> out = Sort.tree_sort(in);
  System.out.println ("out: " + out);
  

  mit der Implementierung aus der Bibliothek:

  Set<Double> s = new TreeSet<Double> ();
  s.addAll (in);
  System.out.println ("s: " + s);
  

  (für längere Eingaben)

Wie sind die offiziellen Suchbäume balanciert?