Interface Baum visualisieren

[CptK]

Hallo,
ich habe eine Arraylist:

private ArrayList<int[]> info = new ArrayList<int[]>();

Diese beinhaltet die Daten eines Baumes, den ich gerne Visualisieren würde. Das habe ich bisher:

private int x, width;

public void paintComponent(Graphics g) {
    super.paintComponent(g);
    int y = 10;
    width = getWidth();
    for(int i = 0; i < info.size(); i++) {
    if(i == 0) x = (getWidth() - g.getFontMetrics().stringWidth(Arrays.toString(info.get(i)))) / 2;
    else calcX(g.getFontMetrics().stringWidth(Arrays.toString(info.get(i))), i);
    g.drawString(Arrays.toString(info.get(i)), x, y);
    y +=20;
    }
}

public void calcX(int w, int index) {
    width /= 2;
    if(info.get(index).length == 1 && info.get(index-1).length == 1) x = (width * 2);
    else x = (width - w) / 2;
}

Allerdings ist das sehr unübersichtlich und wie ich das sehe auch nicht zielführend. Im folgenden Bild habe ich einen Beispielbaum, wobei die grünen Zahlen (die nicht gezeichnet werden sollen) den Index des jeweiligen int-Arrays in der ArrayList darstellen. Die Striche wären schön aber nicht zwingend notwendig. Wie würde ich ein System schreiben, das die Positionen der jeweiligen Strings berechnet, sodass alles schön eingerückt ist?

 

[mihe7]

Wie würde ich ein System schreiben, das die Positionen der jeweiligen Strings berechnet, sodass alles schön eingerückt ist?

Das ist nicht ganz trivial. Wir können ja mal versuchen, uns ranzutasten

Den meisten Platz brauchen offensichtlich die Blattknoten, die in einem festen Abstand zueinander angeordnet werden. Den Abstand bezeichnen wir mal mit hGap.

Außerdem haben wir ein Array mit n Elementen, d. h. wir brauchen Platz für n Blattknoten zzgl. (n-1)*hGap für die Abstände zwischen den Knoten.

Wie groß ist der Platz für einen Blattknoten? Da machen wir es uns einfach und sagen, dass jeder Blattknoten so groß ist, dass der breiteste String, den wir haben, hineinpasst. Nennen wir das mal leaveWidth.

Die Komponente braucht also eine Breite von n*(leaveWidth+hGap) - hGap.

Welche Höhe hat der Baum? Er verfügt über h = floor(log2(n)) + 1 Ebenen. Alle Knoten haben die gleiche Höhe nodeHeight. Außerdem gehen wir von einem festen Abstand vGap zwischen den Ebenen aus, d. h. die Komponente braucht eine Höhe von h*(nodeHeight + vGap) - vGap.

Sei ab jetzt w die Breite des Baums und h die Höhe der Komponente (in Punkten).

Ab jetzt wird es etwas einfacher: jeder Knoten wird zentriert in einem Bereich eingezeichnet, der durch eine linke Koordinate und eine Breite (l und b) in der Horizontalen begrenzt wird.

Wir beginnen bei der Wurzel. Der Bereich beginnt links bei 0 und hat eine Breite von w, d. h. (l,b) == (0,w). Der zu zeichnende String habe eine Breite von sw. Die x-Koordinate berechnet sich dann mit l + (b-sw)/2. Die y-Koordinate entspricht der Grundlinie, also fm.getAscending().

Die Kindknoten werden dann in den Bereichen (l,b/2) und (l+b/2, b/2) eingezeichnet, wobei die y-Koordinate nach jeder Ebene um vGap erhöht wird. Natürlich kann dann auch jeweils eine Linie eingezeichnet werden.

 

[CptK]

Das ist nicht ganz trivial. Wir können ja mal versuchen, uns ranzutasten

Den meisten Platz brauchen offensichtlich die Blattknoten, die in einem festen Abstand zueinander angeordnet werden. Den Abstand bezeichnen wir mal mit hGap.

Außerdem haben wir ein Array mit n Elementen, d. h. wir brauchen Platz für n Blattknoten zzgl. (n-1)*hGap für die Abstände zwischen den Knoten.

Wie groß ist der Platz für einen Blattknoten? Da machen wir es uns einfach und sagen, dass jeder Blattknoten so groß ist, dass der breiteste String, den wir haben, hineinpasst. Nennen wir das mal leaveWidth.

Die Komponente braucht also eine Breite von n*(leaveWidth+hGap) - hGap.

Welche Höhe hat der Baum? Er verfügt über h = floor(log2(n)) + 1 Ebenen. Alle Knoten haben die gleiche Höhe nodeHeight. Außerdem gehen wir von einem festen Abstand vGap zwischen den Ebenen aus, d. h. die Komponente braucht eine Höhe von h*(nodeHeight + vGap) - vGap.

Sei ab jetzt w die Breite des Baums und h die Höhe der Komponente (in Punkten).

Ab jetzt wird es etwas einfacher: jeder Knoten wird zentriert in einem Bereich eingezeichnet, der durch eine linke Koordinate und eine Breite (l und b) in der Horizontalen begrenzt wird.

Wir beginnen bei der Wurzel. Der Bereich beginnt links bei 0 und hat eine Breite von w, d. h. (l,b) == (0,w). Der zu zeichnende String habe eine Breite von sw. Die x-Koordinate berechnet sich dann mit l + (b-sw)/2. Die y-Koordinate entspricht der Grundlinie, also fm.getAscending().

Die Kindknoten werden dann in den Bereichen (l,b/2) und (l+b/2, b/2) eingezeichnet, wobei die y-Koordinate nach jeder Ebene um vGap erhöht wird. Natürlich kann dann auch jeweils eine Linie eingezeichnet werden.

Also, ich versuche mir das jetzt erstmal als Baum-Datenstruktur aufzubauen. Allerdings scheitert es bei mir da schon bei der Insert-Methode. Es soll ja zuerst die Wurzel erzeugt werden. Dann soll solange links eingefügt werden, bis die Länge des Arrays eins beträgt. So weit so gut. Dann muss er aber zurück gehen und rechts weiter machen. Da kriege ich die Rekursion irgendwie nicht hin. Was ich bisher habe:

public void insert(int[] value) {
        if(root == null) root = new Node(value, null);
        else insert(root, value);
    }
    
    private void insert(Node parent, int[] value) {
        if(parent.getLeft() == null) parent.setLeft(new Node(value, parent));
        else {
            if(parent.getLeft().getValue().length == 1) {
                if(parent.getRight() == null) {
                    parent.setRight(new Node(value, parent));
                }
            } else {
                insert(parent.getLeft(), value);
            }
        }
    }

Wichtig hierbei ist ja nicht, dass nach Größe sortiert wird, sondern dass die Struktur wie im Bild oben entsteht.

Zur Ausgabe habe ich eine Preorder-Funktion, wäre schön wenn mir da noch jemand sagen könnte, ob die richtig ist.

public void preorder(Node node) {
        System.out.println("out"+node.getValueString());
        if(node.getLeft() != null) {
            preorder(node.getLeft());
        }
        if(node.getRight() != null) {
            preorder(node.getRight());
        }
    }

Am wichstigsten ist mir natürlich die insert-Methode.

 

[mihe7]

Das ist einfach ein binärer Suchbaum. Als Schlüssel verwendest Du die Mitte des Indexbereichs:

        public int[] sort(int l, int r) {

Schlüssel: (l+r)/2

 

[Blender3D]

Diese beinhaltet die Daten eines Baumes, den ich gerne Visualisieren würde. Das habe ich bisher:

Vielleicht hilft Dir der Linke weiter
https://www.java-forum.org/thema/baum-erzeugen.173638/page-3#post-1155830

 

[CptK]

Das ist einfach ein binärer Suchbaum. Als Schlüssel verwendest Du die Mitte des Indexbereichs:

        public int[] sort(int l, int r) {

Schlüssel: (l+r)/2

ich verstehe nicht ganz, wie mir das helfen soll.

 

[mihe7]

Sagen wir mal, Du hast ein Array mit 16 Elementen. Dann wird sort(0,16) (16 exclusive) für die Wurzel aufgerufen. Der Schlüssel wäre (0+16)/2 == 8.

In sort wird sort rekursiv aufgerufen: sort(0,8) und sort(8,16), entsprechend dem linken und dem rechten Kind der Wurzel. Die Schlüssel sind (0+8)/2 == 4 und (8+16)/2 == 12.

Bei sort(0,8) wird nun wieder rekursiv aufgerufen: sort(0,4) und sort(4, 8). Die Schlüssel sind (0+4)/2 == 2 und (4+8)/2 == 6.
Bei sort(8,16) wird auch rekursiv aufgerufen: sort(8,12) und sort(12,16). Die Schlüssel sind (8+12)/2 == 10 und (12+16)/2 == 14.

Fügst Du also die Arrays entsprechend der Schlüssel in den Baum ein, erhältst Du (Darstellung ohne die Arrays):

          8
         / \ 
        /   \
       4    12
      / \   / \
     2  6  10 14

Und so weiter, also einen Baum, der genau den Aufrufen entspricht.

 

[CptK]

Sagen wir mal, Du hast ein Array mit 16 Elementen. Dann wird sort(0,16) (16 exclusive) für die Wurzel aufgerufen. Der Schlüssel wäre (0+16)/2 == 8.

In sort wird sort rekursiv aufgerufen: sort(0,8) und sort(8,16), entsprechend dem linken und dem rechten Kind der Wurzel. Die Schlüssel sind (0+8)/2 == 4 und (8+16)/2 == 12.

Bei sort(0,8) wird nun wieder rekursiv aufgerufen: sort(0,4) und sort(4, 8). Die Schlüssel sind (0+4)/2 == 2 und (4+8)/2 == 6.
Bei sort(8,16) wird auch rekursiv aufgerufen: sort(8,12) und sort(12,16). Die Schlüssel sind (8+12)/2 == 10 und (12+16)/2 == 14.

Fügst Du also die Arrays entsprechend der Schlüssel in den Baum ein, erhältst Du (Darstellung ohne die Arrays):

          8
         / \
        /   \
       4    12
      / \   / \
     2  6  10 14

Und so weiter, also einen Baum, der genau den Aufrufen entspricht.

Das klingt schon irgendwie logisch, ich weiß nur trotzdem nicht so recht, wie ich das in Code umsetzten soll.

 

[mihe7]

OK, so aus dem Kopf heraus:

class Node {
    public static final Node EMPTY = new Node() {
        @Override
        protected boolean isEmptyNode() { return true; }
        @Override
        public Node getLeft() { return this; }
        @Override
        public Node getRight() { return this; }
    };

    private int[] value;
    private int key;
    private Node left;
    private Node right;

    private Node() {}

    public Node(int key, int[] value) {
        this.key = key;
        this.value = value;
        left = EMPTY;
        right = EMPTY;
    }

    protected boolean isEmptyNode() { return false; }

    public Node insert(Node node) {
        if (this.isEmptyNode()) {
            return node;
        } else {
            if (node.key < key) {
                left = left.insert(node);
            } else if (node.key > key) {
                right = right.insert(node);
            }
            return this;
        }
    }

    public int[] getValue() { return value; }
    public int getKey() { return key; }
    public Node getLeft() { return left; }
    public Node getRight() { return right; }
}

Damit kannst Du irgendwo einen Baum verwalten, den Du zu Beginn mit Node.EMPTY initialisierst. In sort kopierst Du den aktuell betrachteten Ausschnitt des Arrays, der von l bis r geht, in ein neues Array. Zusammen mit dem Schlüssel (l+r)/2 ergibt dies dann einen Node, den Du in Deinen Baum einfügen kannst: tree = tree.insert(newNode);.

 

[CptK]

Okay, dazu habe ich aber noch ein paar Fragen:
1. Ist das denn auch rekursiv, weil irgendwie habe ich das Gefühl, dass einfach immer der alter Baum überschrieben wird und am Ende nicht alle 19 Arrays gespeichert sind.
2. Gäbe es in diesem System auch die Möglichkeit für jeden Node den Parent-Node zu speichern?
3. Wie würde ich das Ganze ausgeben?

 

[mihe7]

Ist das denn auch rekursiv, weil irgendwie habe ich das Gefühl, dass einfach immer der alter Baum überschrieben wird und am Ende nicht alle 19 Arrays gespeichert sind.

Die insert-Methode arbeitet rekursiv. Wenn Du auf tree = tree.insert(...) anspielst: das liegt nur daran, weil der Baum leer sein kann und beim Einfügen dann eine neue Wurzel erhält.

Gäbe es in diesem System auch die Möglichkeit für jeden Node den Parent-Node zu speichern?

Natürlich. Brauchst Du aber zum Zeichnen nicht.

Wie würde ich das Ganze ausgeben?

Du kannst dem Spaß eine Visitor-Methode hinzufügen:

    public void preorder(Consumer<Node> c) {
        if (isEmptyNode()) { return; }
        c.accept(this);
        preorder(left);
        preorder(right);
    }

 

[CptK]

Die insert-Methode arbeitet rekursiv. Wenn Du auf tree = tree.insert(...) anspielst: das liegt nur daran, weil der Baum leer sein kann und beim Einfügen dann eine neue Wurzel erhält.


Natürlich. Brauchst Du aber zum Zeichnen nicht.


Du kannst dem Spaß eine Visitor-Methode hinzufügen:

    public void preorder(Consumer<Node> c) {
        if (isEmptyNode()) { return; }
        c.accept(this);
        preorder(left);
        preorder(right);
    }

Also ich checke es nicht... Ich habe jetzt in meiner Klasse eine Variable tree. Im Constructor mache ich

this.tree = Node.EMPTY;

meine run-Methode sieht so aus:

public void run() {
    tree = tree.insert(new Node((data.length-1) / 2, data));
    sort(0, data.length-1);
    tree.preorder(tree);
    panel.setDefault();
}

und die sort-Methode so:

public int[] sort(int l, int r) {
            int[] tempArr = new int[r-l+1];
            int c = 0;
            for(int m = l; m <= r; m++) {
                tempArr[c] = data[m];
                c++;
            }
            tree.insert(new Node((l+r)/2, tempArr));
            treepanel.addData(tempArr,tree);
            //System.out.println(Arrays.toString(tempArr));
            if (l < r) {
                int q = (l + r) / 2;
                sort(l, q);
                sort(q+1, r);
                merge(l, q, r);
         
            }
            return data;
        }

Deine Ausgabe-Methode geht auch nicht, weil die übergebenen Parameter kein Consumer sind und die sich irgendwie auch nicht casten lassen. Ich habe versucht das so umzuschreiben:

public void preorder(Node c) {
        if (isEmptyNode()) { return; }
        System.out.println(Arrays.toString(value));
        preorder(left);
        preorder(right);
    }

Allerdings bekomme ich da in der Ausgabe immer nur das Selbe, nämlich das Array, das als erstes eingegeben wurde, bis ein java.lang.StackOverflowError kommt. Liegt das jetzt daran, dass das Zeug falsch eingefügt oder nur falsch ausgegeben wird?

 

[CptK]

UPDATE:
Ich habe jetzt meinen ursprünglichen Baum so modifiziert, dass es funktioniert:
Tree.java:

package data;

public class Tree {

    private Node root;
    
    public Tree() {
        root = null;
    }
    
    public void insert(int[] value, int key) {
        if(root == null) root = new Node(value, key);
        else insert(root, value, key);
    }
    
    private void insert(Node parent, int[] value, int key) {
        if(parent.key > key) {
            if(parent.getLeft() == null) parent.setLeft(new Node(value, key));
            else insert(parent.getLeft(), value, key);
        } else {
            if(parent.getRight() == null) parent.setRight(new Node(value, key));
            else insert(parent.getRight(), value, key);
        }
    }
    
    public void preorder(Node node) {
        System.out.println("out"+node.getValueString());
        if(node.getLeft() != null) {
            preorder(node.getLeft());
        }
        if(node.getRight() != null) {
            preorder(node.getRight());
        }
    }
    

    public Node getRoot() {
        return root;
    }
    
}

Node.java:

package data;

import java.util.Arrays;

public class Node {
    private int[] value;
    private Node left, right;
    public int key;
    
    public Node(int[] value, int key) {
        this.value = value;
        this.key = key;
    }
    
    public int[] getValue() {
        return value;
    }
    
    public String getValueString() {
        return Arrays.toString(value);
    }
    
    public Node getLeft() {
        return left;
    }
    
    public Node getRight() {
        return right;
    }
    
    public void setLeft(Node left) {
        this.left = left;
    }
    
    public void setRight(Node right) {
        this.right = right;
    }
}

Da hätte ich nur nochmal ne kleine Design-Frage: ist es besser eine Variable als public zu definieren oder lieber als private mit Getter & Setter?

 

[mihe7]

Deine Ausgabe-Methode geht auch nicht, weil die übergebenen Parameter kein Consumer sind und die sich irgendwie auch nicht casten lassen.

Naja, ich schreibe den Code hier nur in den Editor, um die Grundidee zu zeigen. D. h. es kann durchaus sein, dass da Fehler enthalten sind. Konkret habe ich mich beim rekursiven Aufruf von preorder verschrieben:

    public void preorder(Consumer<Node> c) {
        if (isEmptyNode()) { return; }
        c.accept(this);
        left.preorder(c);
        right.preorder(c);
    }

Das ist übrigens keine Ausgabe-Methode sondern ein Visitor, mit dem die Knoten in preorder-Reihenfolge besucht werden. Die Methode funktioniert, wenn man eine Implementierung von java.util.function.Consumer mitgibt, z. B.

tree.preorder(new Consumer<Node>() {
    public void accept(Node n) {
        // mach was mit n
    }
});

Der Unterschied ist, dass es nun nicht mehr von der Klasse Node sondern vom Aufrufer abhängig ist, was mit dem besuchten Node passiert. Die Schreibweise lässt sich mit Methodenreferenzen und Lambdas schön verkürzen:

tree.preorder(n -> System.out.println(n.getKey() + ": " + Arrays.toString(n.getValuae()));

Da hätte ich nur nochmal ne kleine Design-Frage: ist es besser eine Variable als public zu definieren oder lieber als private mit Getter & Setter?

Oh, die Frage führt zu einem ganz zentralen Punkt. In der Objektorientierung geht es um Abstraktion, will man doch abstrakte Datentypen umsetzen. Andererseits stellt nicht jede Klasse einen solchen Datentyp dar bzw. braucht man manchmal einfach zusammengesetzte Datentypen, die einfach nur als Datencontainer dienen. Dort dienen Getter und Setter lediglich der Zugriffskontrolle, da das Implementierungsdetail sowieso nach außen getragen wird. Wenn keine Zugriffskontrolle notwendig ist, kann man sich die Methoden auch sparen.

Der Code hier kann diesbezüglich als schlechtes Beispiel dienen. Wenn Du meine Node-Klasse nimmst, werden dort Schlüssel und Werte konkreter Typen gespeichert und diese werden ebenso konkret einfach nach außen gegeben (getKey(), getVaue()). Es findet keinerlei Prüfung statt. Zugute halten kann man der Implementierung diesbezüglich nur, dass es keine Setter gibt.

Bzgl. left und right sieht die Sache dagegen anders aus. Wir haben zwar zwei Methoden, die getLeft() und getRight() heißen, deren Aufgabe besteht aber nicht darin left und right zurückzugeben. Die Aufgabe der Methoden besteht darin, den Wurzelknoten des linken bzw. rechten Teilbaums zu liefern. Dass sie in der Klasse Node die Attribute left bzw. right zurückgeben, ist ein Implementierungsdetail, wie man an Node.EMPTY schön sieht. Dort wird einfach this geliefert.

 

[CptK]

Ich hätte jetzt noch eine weitere Frage: Wie finde ich die Tiefe eines Elements heraus?
Ich habe es so versucht:

public int getElementDepht(int key) {
        int d = 0;
            if(root.key != key) {
                if(key > root.key) {
                    if(root.getRight() != null) d = getElementDepht(key, root.getRight()) + 1;
                } else {
                    if(root.getLeft() != null)d = getElementDepht(key, root.getLeft()) + 1;
                }
            }
        return d;
    }

    private int getElementDepht(int key, Node parent) {
        int d = 0;
        if(parent != null && parent.key != key) {
            if(key > root.key) {
                if(root.getRight() != null) d = getElementDepht(key, parent.getRight()) + 1;
            } else {
                if(root.getLeft() != null) d = getElementDepht(key, parent.getLeft()) + 1;
            }
        }
        return d;
    }

Allerdings stimmen die Ausgaben nicht immer. Ich habe auch das Gefühl, dass in meinem System Schlüssel in mehreren tiefen mehrfach vorkommen. Also muss ich wahrscheinlich mit dem value, also einem int[] suchen, wobei ich da noch weniger weiß wie das gehen soll.

 

[mihe7]

Also muss ich wahrscheinlich mit dem value, also einem int[] suchen, wobei ich da noch weniger weiß wie das gehen soll.

Das solltest Du nicht tun, dazu brauchst Du einen Durchlauf.

public int getElementDepht(int key) {
    return getElementDepth(key, root);
}

Ich habe auch das Gefühl, dass in meinem System Schlüssel in mehreren tiefen mehrfach vorkommen.

Du fängst den Fall parent.key == key nicht ab (wobei das der Parameter besser root statt parent heißen sollte).

 

[CptK]

Damit ist das Problem, dass ein Schlüssel mehrfach vorkommt, z.B. der Schlüssel 6 einmal in Tiefe 2 und 4, doch noch nicht gelöst?
Bzw wenn ich parent.key == key mache, was soll ich dann machen? Weil ich weiß ja nicht, ob der Schlüssel nochmal vorkommt, also müsste ich dann prüfen, ob er nochmal kommt und ohne die Werte zu vergleichen weiß ich doch nicht, welche Tiefe jetzt die richtige ist.

 

[mihe7]

z.B. der Schlüssel 6 einmal in Tiefe 2 und 4

Lass bei der Berechnung des Schlüssels die Division einfach weg. Dann ist der Schlüssel l+r.

 

[CptK]

Lass bei der Berechnung des Schlüssels die Division einfach weg. Dann ist der Schlüssel l+r.

Das ändert leider auch nichts daran, dass manche Schlüssel mehrfach vorkommen

l: 
l: 0 r: 9 key: 9
l: 0 r: 4 key: 4
l: 0 r: 2 key: 2
l: 0 r: 1 key: 1
l: 0 r: 0 key: 0
l: 1 r: 1 key: 2
l: 2 r: 2 key: 4
l: 3 r: 4 key: 7
l: 3 r: 3 key: 6
l: 4 r: 4 key: 8
l: 5 r: 9 key: 14
l: 5 r: 7 key: 12
l: 5 r: 6 key: 11
l: 5 r: 5 key: 10
l: 6 r: 6 key: 12
l: 7 r: 7 key: 14
l: 8 r: 9 key: 17
l: 8 r: 8 key: 16
l: 9 r: 9 key: 18

 

[CptK]

Das ändert leider auch nichts daran, dass manche Schlüssel mehrfach vorkommen

Habe da jetzt ne andere Idee:

private ArrayList<int[]> info;

 public void run() {
     info = new ArrayList<int[]>();
     sort(0, data.length-1);
 }

public int[] sort(int l, int r) {
    int[] tempArr = new int[r-l+1];
    int c = 0;
    for(int m = l; m <= r; m++) {
        tempArr[c] = data[m];
        c++;
    }
    if (l < r) {
        int q = (l + r) / 2;
        sort(l, q);
        info.add(tempArr);
        double key = info.indexOf(tempArr);
        sort(q+1, r);
        merge(l, q, r);
    } else {
        info.add(tempArr);
        double key = info.indexOf(tempArr);
        treepanel.addData(tempArr, key);
    }
    return data;
}

Ich habe eine ArrayList, der ich die Obkejte hinzufüge und der index in der ArrayList ist der Schlüssel. Problem ist hierbeim aber, dass zwar alles den richtigen schlüssel hat ich für die insert methode diese aber vor der if(l < r) aufrufen müsste, ich da aber den schlüssel noch nicht habe, also so:

public int[] sort(int l, int r) {
            int[] tempArr = new int[r-l+1];
            int c = 0;
            for(int m = l; m <= r; m++) {
                tempArr[c] = data[m];
                c++;
            }
            
            /////////////////////////////////////////////////
            double key = info.indexOf(tempArr);
            treepanel.addData(tempArr, key);
            /////////////////////////////////////////////////
            Problem: objekt wird erst später hinzugrfügt, also kann ich den index hier noch nicht bekommen
            
            if (l < r) {
                int q = (l + r) / 2;
                sort(l, q);
                    info.add(tempArr);
                sort(q+1, r);
                merge(l, q, r);
            } else {
                info.add(tempArr);
            }
            return data;
        }

 

[mihe7]

Das ändert leider auch nichts daran, dass manche Schlüssel mehrfach vorkommen

OMG, bin ich blöd, das kann so und so nicht funktionieren, weil die Intervallgrenzen ganzzahlig sind. Dann nimmst Du halt das Intervall als Schlüssel. Du fügst in den linken Teilbaum ein, wenn die rechte Grenze des Schlüssels kleiner als die rechte Grenze des Wurzel-Schlüssels ist, ansonsten in den rechten Teilbaum.

 

[mihe7]

Hier mal ein zusammengeschusteter Ansatz.

Spoiler: MergeSort.java

public class MergeSort {
    public interface SortingListener {
        void sorting(int[] arr, int l, int r);
    }

    private SortingListener listener;

    public void setSortingListener(SortingListener listener) {
        this.listener = listener;
    }

    public void sort(int[] data) {
        sort(data, 0, data.length);
    }
    
    private void sort(int[] arr, int l, int r) {
        sorting(arr, l, r);

        int size = r-l;
        if (size < 2) {
            return;
        }

        int m = (l+r)/2;
        sort(arr, l, m);
        sort(arr, m, r);
        merge(arr, l, m, r);
    }

    private void merge(int[] arr, int l, int m, int r) {
        int size = r-l;
        int[] copy = new int[size];
        System.arraycopy(arr, l, copy, 0, size);

        int nl = 0;
        int nr = size-1;

        for (int i = l; i < r; i++) {
            if (copy[nl] <= copy[nr]) {
                arr[i] = copy[nl];
                nl++;
            } else {
                arr[i] = copy[nr];
                nr--;
            }
        }
    }

    private void sorting(int[] arr, int l, int r) {
        if (listener != null) {
            listener.sorting(arr, l, r);
        }
    }
}

Spoiler: Node.java

public class Node {
    public static class Entry {
        final int left;
        final int right;
        final int[] data;

        public Entry(int left, int right, int[] data) {
            this.left = left;
            this.right = right;
            this.data = data;
        }

        public boolean overlaps(Entry e) {
            return left < e.right && right > e.left;
        }

        public boolean isLeftOf(Entry e) {
            return right < e.right;
        }
    }

    static Node EMPTY = new Node() {
        @Override
        public boolean isEmpty() { return true; }
        @Override
        public Node leftTree() { return this; }
        @Override
        public Node rightTree() { return this; }
    };

    private Entry value;
    private Node left, right;

    private Node() {}

    public Node(Entry value) {
        this.value = value;
        right = left = EMPTY;
    }

    public boolean isEmpty() { return false; }
    public Entry getValue() { return value; }
    public Node leftTree() { return left; }
    public Node rightTree() { return right; }
    
    public Node insert(Entry newValue) {
        if (isEmpty()) {
            return new Node(newValue);
        } else if (value.overlaps(newValue)) {
            if (shouldBeInLeftTree(newValue)) {
                left = left.insert(newValue);
            } else {
                right = right.insert(newValue);
            }
        }
        return this;
    }

    private boolean shouldBeInLeftTree(Entry entry) {
        return left.isEmpty() && entry.isLeftOf(value) ||
                !left.isEmpty() && left.value.overlaps(entry);
    }
}

Spoiler: TreePanel.java

import java.awt.FontMetrics;
import java.awt.Graphics;
import java.util.Arrays;
import javax.swing.JPanel;

public class TreePanel extends JPanel {
    private Node tree = Node.EMPTY;

    private int hGap = 10;
    private int vGap = 30;
    

    public void setTree(Node root) {
        tree = root;
        repaint();
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        if (tree.isEmpty()) {
            return;
        }

        int[] data = tree.getValue().data;
        int entryWidth = maxEntryWidth(data, g.getFontMetrics());
        int width = data.length*(entryWidth + hGap) - hGap;
        paintNode(tree, width, 0, 0, g);
    }

    private int maxEntryWidth(int[] data, FontMetrics fm) {
        int[] entry = new int[1];
        int max = 0;
        for (int value : data) {
            entry[0] = value;
            int w = fm.stringWidth(Arrays.toString(entry));
            if (w > max) { max = w; }
        }
        return max;
    }

    private void paintNode(Node node, int width, int x, int y, Graphics g) {
        if (node.isEmpty()) {
            return;
        }
        FontMetrics fm = g.getFontMetrics();
        int cy = y + fm.getAscent();
        String text = Arrays.toString(node.getValue().data);
        int cx = x + (width - fm.stringWidth(text))/2;
        g.drawString(text, cx, cy);
        if (!node.leftTree().isEmpty()) {
            g.drawLine(x+width/2, y+fm.getHeight(), x + width/4, y+fm.getHeight()+vGap);
            paintNode(node.leftTree(), width/2, x, y+fm.getHeight()+vGap, g);
        }
        if (!node.rightTree().isEmpty()) {
            g.drawLine(x+width/2, y+fm.getHeight(), x + 3*width/4, y+fm.getHeight()+vGap);
            paintNode(node.rightTree(), width/2, x+width/2, y+fm.getHeight()+vGap, g);
        }
    }
}

Spoiler: Main.java

import java.awt.BorderLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.Arrays;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.SwingUtilities;

public class Main {

    private int[] data = {8,7,6,5,4,3,2,1};
    private Node tree = Node.EMPTY;
    private TreePanel panel = new TreePanel();
    private MergeSort mergeSort = new MergeSort();
    private Thread background = null;

    private ActionListener sortAction = new ActionListener() {
        public void actionPerformed(ActionEvent e) {
            if (background != null && background.isAlive()) {
                return;
            }
            tree = Node.EMPTY;
            panel.setTree(tree);
            int[] tmp = new int[data.length];
            System.arraycopy(data,0, tmp, 0, data.length);
            background = new Thread(() -> mergeSort.sort(tmp));
            background.setPriority(Thread.MIN_PRIORITY);
            background.start();
        }
    };

    public static void main(String[] args) {
        SwingUtilities.invokeLater(() -> new Main().run());
    }

    public void run() {
        mergeSort.setSortingListener(this::insert);
        JButton button = new JButton("Sortieren");
        button.addActionListener(sortAction);
        
        JFrame frame = new JFrame("Merge Sort");
        frame.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
        frame.add(panel);
        frame.add(button, BorderLayout.SOUTH);
        frame.setSize(600,400);
        frame.setVisible(true);
    }

    private void insert(int[] arr, int left, int right) {
        int[] data = new int[right-left];
        System.arraycopy(arr, left, data, 0, data.length);
        SwingUtilities.invokeLater(() -> {
            tree = tree.insert(new Node.Entry(left, right, data));
            panel.setTree(tree);
        });
        sleep(250);
    }

    private void sleep(long ms) {
        try {
            Thread.sleep(ms);
        } catch (InterruptedException ex) {
            ex.printStackTrace();
        }
    }
}

 

[CptK]

Hallo,
ich hatte das Projekt erst einmal auf Eis gelegt, deshalb die späte Antwort. Das was du geschickt hast ist schon mal genial.



Allerdings war das erst die Hälfte. Bisher wird der Teil des Sortierens (im Bild das Schwarze) gezeichnet. Nun fehlt noch der zweite Teil, das Merging (im Bild das Blaue). Gibt es einfache Möglichkeit das im Code noch hinzuzufügen?

 

[Xyz1]

Man ist das eine Sauklaue Nein, Spaß. Geht es um MergeSort?

 

[CptK]

Man ist das eine Sauklaue Nein, Spaß. Geht es um MergeSort?

Pff
Ja, es geht darum den Algorithmus, also das was ich da "gekritzelt" habe, visuell aus einem int-Array darzustellen, wofür mihe7 oben schon den ersten Teil (im Bild das Schwarze) als Code offeriert hat.

 

[Xyz1]

War nicht so gemeint... Manche schreiben auch so dass komplett nichts zu erkennen ist.
Ich schaue es mir später an sobald ich wieder am PC bin...*.

 

[Xyz1]

@mihe7 mach Du weiter büdde.

 

[mihe7]

It's your turn Mir fällt gerade nichts ein, wie man das einfach hinbekommen würde.

 

[Xyz1]

Mich macht auch das etwas stutzig: "Das Verfahren arbeitet bei Arrays in der Regel nicht in-place," https://de.wikipedia.org/wiki/Mergesort#Funktionsweise .

Soweit ich das auf die Schnelle erkennen kann, geht ihr nicht in-place vor.

 

[mihe7]

Mich macht auch das etwas stutzig: "Das Verfahren arbeitet bei Arrays in der Regel nicht in-place," https://de.wikipedia.org/wiki/Mergesort#Funktionsweise .

Und was macht Dich da stutzig? Der Mergeschritt besteht ja gerade darin, zwei sortierte Listen in O(n) zu einer sortierten Liste vereinen zu können. In-Place macht de Umsetzung doch wesentlich komplizierter.

 

[Xyz1]

ja dann ist es doch einfach.

 

[mihe7]

ja dann ist es doch einfach.

?

 

[Xyz1]

@mihe7 Jetzt mach Du bitte weiter, habe dazu keinen Nerv.

Zudem, so wie es aussieht, habt ihr den conquer Schritt doch schon.

 

[mihe7]

It's your turn Mir fällt gerade nichts ein, wie man das einfach hinbekommen würde.

 

[CptK]

Wäre es möglich, das Ganze mit dem Array der in meiner Abbildung ganz unten steht durchlaufen zu lassen und anstatt von oben nach unten einfach von unten nach oben zu zeichnen?

 

[CptK]

Keiner der mir helfen kann?

 

[Xyz1]

Ok, ich helfe Dir...

Wie ist der Ist-Stand (Quelltext...) und der Soll-Stand bisher?

 

[CptK]

Der ist_Stand ist im prinzip der code den mihe7 weiter oben gesendet hat weil ich alle Veränderung, nachdem sie nicht funktioniert haben, frustriert wieder gelöscht habe. Der Soll-Stand ist, dass der gesamte Baum, den ich in dem Bild geschickt habe gezeichnet wird und nicht nur der Halbe wie in mihes code.