Guten Tag,
habe wieder einmal eine Aufgabe wo ich zwar denke ich hätte einen "Lösungsansatz" doch bekomme ich es nicht Programmiert. Hier mal die Aufgabe:
Der Code dazu:
Die Idee von mir wäre man nimmt Intervalle. Wenn der Baum oben mit 8 Anfängt hätten wir Links [8 ... ] und Rechts [ ... 7]. Doch es sind ja nicht nur Integer zugelassen sondern sämtliche X die Vergleichbar sind. Wie ich dort dann ein Intervall bilden könnte keine Ahnung. Weiß'noch nicht mal ob die Idee dafür geeignet wäre.
Alle anderen Ideen die ich hatte Speichern den Baum in eine andere Struktur oder laufen 10.000x durch den Baum also nicht O(n).
Es sind bis jetzt auch erst Ideen zu einer Implementierung kam ich bis jetzt noch nicht und wüsste auch nicht wie das mit den Intervallen gehen würde
Danke im voraus
LG
habe wieder einmal eine Aufgabe wo ich zwar denke ich hätte einen "Lösungsansatz" doch bekomme ich es nicht Programmiert. Hier mal die Aufgabe:
Eine Multimenge sei mit Hilfe von binären Suchbäumen wie unten aufgeführt implementiert. Für jeden Knoten (Node) im Baum ist sein Wert ungleich null und größer oder gleich allen Werten im linken Teilbaum und kleiner als alle Werte im rechten Teilbaum. Gesucht ist die Methode isSet(). Diese Methode überprüft bei einer Komplexität von maximal O(n), ob eine Menge vorliegt (d.h. keine Duplikate vorkommen). Achtung: Die Werte sollen nicht etwa in eine andere Repräsentation kopiert werden; es ist lediglich der Baum geeignet zu analysieren.
Der Code dazu:
Code:
class TreeBag<X extends Comparable<X>> {
private class Node {
X value;
Node left, right;
}
private Node root;
public boolean isSet() {
}
}
Die Idee von mir wäre man nimmt Intervalle. Wenn der Baum oben mit 8 Anfängt hätten wir Links [8 ... ] und Rechts [ ... 7]. Doch es sind ja nicht nur Integer zugelassen sondern sämtliche X die Vergleichbar sind. Wie ich dort dann ein Intervall bilden könnte keine Ahnung. Weiß'noch nicht mal ob die Idee dafür geeignet wäre.
Alle anderen Ideen die ich hatte Speichern den Baum in eine andere Struktur oder laufen 10.000x durch den Baum also nicht O(n).
Es sind bis jetzt auch erst Ideen zu einer Implementierung kam ich bis jetzt noch nicht und wüsste auch nicht wie das mit den Intervallen gehen würde
Danke im voraus
LG