Subato 562/SearchTree

Resource Files

SearchTree

Suchbäume

Die Klasse SearchTree implementiert eine Map, die Schlüssel (keys) auf Werte (values) abbildet. Implementieren Sie die zwei folgenden Methoden:

insert(Comparable key, T value): Einfügen eines Schlüssel-Wert-Paares. Implementieren Sie das Einfügen nicht iterativ (wie in der Vorlesung), sondern rekursiv.
countSmaller(Comparable key): Gibt die Anzahl der Elemente im Baum zurück, die kleiner sind als der übergebene Schlüssel. Implementieren Sie die Methode möglichst effizient, d.h. es sollen nicht immer pauschal alle Knoten im Baum besucht werden.

Fold all Unfold all Fullscreen Settings Help

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package de.hsrm.ads;
public class SearchTree< C extends Comparable<C>, T> {
  Node root;
  class Node {
    Node left;
    Node right;
    C key;
    T value;
    Node(C key, T value) {
      this.left = null;
      this.right = null;
      this.value = value;
      this.key = key;
    }
  }
  
  public SearchTree() {
    root = null;
  }
  public void insert(C key, T value) {
    // FIXME
  }
  public int countSmaller(C key) {
    // FIXME
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

java
You are not logged in and therefore you cannot submit a solution.