TreeMap ausbalancieren

TreeMap ausbalancieren

  • Andrej Albrecht
  • 2016-09-03 09:03:00

In der nachfolgenden Abbildung befindet sich das Vorgehen, um eine TreeMap zu balancieren. Im 1. Schritt werden alle Knoten aus der TreeMap gelesen und in einer Liste gespeichert. Diese Liste wird im 2. Schritt halbiert. Das Element (G), das sich genau in der Mitte der Liste befindet, stellt den Wurzel-Knoten dar und wird als solcher gespeichert. Auf alle Elemente (A bis F) aus der Liste, die sich links des Wurzel-Knoten befinden, wird im 3. Schritt das gleiche Vorgehen angewendet. Diesmal wird als mittleres Element (D) aus der Liste gewählt und als linker Knoten von (G) gespeichert. Beim 4. Schritt, wird aus dem rechten Teil der Liste der sich aus dem 2. Schritt ergeben hat (H bis M), als mittleres Element (K) gewählt und als rechter Knoten von (G) gespeichert. Das Vorgehen wird auf allen tieferen Ebenen angewendet bis die Liste keine Elemente übrig hat. Das Ergebnis des Vorgehens ist eine perfekt ausbalancierte TreeMap, bei der jeder Knoten einen linken und rechten Teilbaum verfügt und dessen Knotenzahl sich höchstens um den Wert 1 unterscheidet.

TreeMap ausbalancieren

Programmcode

In dem folgenden Programmcode wird eine TreeMap erstellt und einzelne Knoten werden an willkürlichen Positionen in der TreeMap gespeichert. Die TreeMap ist daher nicht ausbalanciert. Die Testwerte können beliebige Objekte sein, die das "java.lang.Comparable"-Interface implementieren. In diesem Beispiel werden einfachheitshalber String-Objekte verwendet. In der 18. Zeile wird auf das Objekt der nicht balancierten TreeMap die Methode getPerfectlyBalancedCopy() aufgerufen, diese liefert als Kopie eine ausbalancierte TreeMap.

public static void main(String[] args) {
    MyTreeMap unbalancedTreeMap = new MyTreeMap();
    unbalancedTreeMap.put(new String("A"), "A");
    unbalancedTreeMap.put(new String("B"), "B");
    unbalancedTreeMap.put(new String("C"), "C");
    unbalancedTreeMap.put(new String("D"), "D");
    unbalancedTreeMap.put(new String("E"), "E");
    unbalancedTreeMap.put(new String("F"), "F");
    unbalancedTreeMap.put(new String("G"), "G");
    unbalancedTreeMap.put(new String("H"), "H");
    unbalancedTreeMap.put(new String("I"), "I");
    unbalancedTreeMap.put(new String("J"), "J");
    unbalancedTreeMap.put(new String("K"), "K");
    unbalancedTreeMap.put(new String("L"), "L");
    unbalancedTreeMap.put(new String("M"), "M");
    unbalancedTreeMap.print(); // print
	
    MyTreeMap balancedTreeMap = unbalancedTreeMap.getPerfectlyBalancedCopy();
    balancedTreeMap.print(); // print
}

Die folgende Methode getPerfectlyBalancedCopy erstellt eine LinkedHashMap aus allen Einträgen der ersten TreeMap und eine neue TreeMap, die als Parameter die LinkedHashMap der Einträge aus der ersten TreeMap erhält. Der Konstructor ist der Klasse MyTreeMap erstellt aus der LinkedHashMap der Einträge eine perfekt ausbalancierte Baumstruktur.

public MyTreeMap getPerfectlyBalancedCopy(){
    LinkedHashMap list = this.getAllEntriesAsList();
    MyTreeMap treeCopy = new MyTreeMap(list);
    return treeCopy;
}


Der Konstruktion der Klasse MyTreeMap erhält als Parameter eine LinkedHashMap mit Werten, die in der TreeMap balanciert gespeichert werden sollen. Es wird davon ausgegangen, das sämtliche Werte der LinkedHashMap sortiert vorliegen. Da später bestimmte Ausschnitte der eingetragenen Werte der Map benötigt werden und eine List dafür die Methode Sublist anbietet, wird in diesem Schritt einfachheitshalber eine List aus der LinkedHashMap erstellt.
In dem nächsten Schritt (Zeile 8) wird die Liste mit den Einträgen der Methode balance übergeben. Die Methode ruft sich rekursiv auf und erstellt eine ausbalancierte TreeMap. Als Ergebnis liefert die Methode balance den obersten Knoten (Wurzelknoten) der ausbalancierten TreeMap zurück.

public MyTreeMap(LinkedHashMap map) {
    // Initialisierung der TreeMap
    this.root = null;
    this.size = 0;
	
    List> mapAsList = new ArrayList>(map.entrySet());
		
    this.root = balance(this.root, mapAsList);
}


Der folgende Programmcode beschreibt die Methode balance zum ausbalancieren einer TreeMap. Die Methode führt das Konzept aus der am Anfang beschriebenen Grafik aus. In der 2. Zeile wird ein Knoten initialisiert, der zurückgeliefert werden soll. Beim 1. Aufruf dieser rekursiven Methode, ist dieser Knoten der Wurzelknoten.
Auf den linken Teil der Liste (Ab dem Anfang der Liste bis zum mittleren Wert der Liste) wird die balance-Methode rekursiv angewendet. Der zurückgelieferte Knoten, daher der mittlere Knoten der linken Liste wird in der linken Abzweigung des aktuellen Knoten gespeichert.
Das Key-Value Paar des mittleren Wertes der aktuellen Liste wird in dem Knoten-Objekt node gespeichert.
Auf den rechten Teil der Liste (nach dem mittleren Wert bis zum Ende der Liste) wird die balance-Methode ebenfalls rekursiv angewendet. Der zurückgelieferte Knoten, daher der mittlere Knoten der rechten Liste, wird in der rechten Abzweigung des aktuellen Knoten gespeichert. Das Prinzip wird so oft aufgerufen bis zu den Blättern der TreeMap, bzw. bis die Listen nicht mehr weiter halbiert werden können.

private Node balance(Node nodeUp, List> list) {
    Node node = new Node(null, null);
		
    if(list.size()/2 > 0 && list.size()>=1){
        ArrayList> leftList = new ArrayList>(list.subList(0, list.size()/2));
        node.left = balance(nodeUp, leftList);
    }

    Entry middleNodeEntry;
    if (list.size()==1){
        middleNodeEntry = list.get(0);
    } else if (list.size()>1) {
        middleNodeEntry = list.get((list.size()/2));
    } else {
        middleNodeEntry = null;
    }
	
    if(middleNodeEntry!=null && middleNodeEntry.getKey()!=null && middleNodeEntry.getValue()!=null){
        node.key = middleNodeEntry.getKey();
        node.value = middleNodeEntry.getValue();
    }
		
    if((list.size()/2+1) < list.size() && list.size()>1){
        ArrayList> rightList = new ArrayList>(list.subList(list.size()/2+1, list.size()));
        node.right = balance(nodeUp, rightList);
    }
	
    return node;
}

BalanceTreeMap Github Project