Beispiel für einen Rot-Schwarz Baum in Java


#1
Hallo,

hier mal ein Beispiel für eine Rot-Schwarz Baum Implementierung in Java:
//EDIT dies ist eine Fehlerbereinigte Version -- siehe Erklärung unten
http://de.wikipedia.org/wiki/Rot-Schwarz-Baum
Java:
package de.tutorials;
 
import java.util.BitSet;
import java.util.Random;
 
/**
 * @author Thomas.Darimont
 * 
 */
public class RedBlackTree<TKey extends Comparable<TKey>, TValue> {
 
    private class Node {
        private Node left, right;
        private boolean color;
        private TKey key;
        private TValue value;
 
        public Node(TKey key, TValue value, boolean color) {
            this.key = key;
            this.value = value;
            this.color = color;
        }
 
        @Override
        public String toString() {
            return key + ": value " + (color ? "R" : "B");
        }
    }
 
    private static final boolean RED = true;
    private static final boolean BLACK = false;
    private Node root;
 
    public TValue get(TKey key) {
        Node node = root;
 
        while (node != null) {
            int cmp = key.compareTo(node.key);
            if (cmp < 0) {
                node = node.left;
            } else if (cmp > 0) {
                node = node.right;
            } else if (cmp == 0) {
                return node.value;
            }
        }
 
        return null;
    }
 
    private boolean isRed(Node node) {
        if (node == null) {
            return false;
        }
        return node.color;
    }
 
    private Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        return x;
    }
 
    private Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        return x;
    }
 
    private Node insert(Node node, TKey key, TValue value, boolean isRed) {
 
        if (node == null) {
            return new Node(key, value, RED); // RED was isRed before
        }
 
        if (isRed(node.left) && isRed(node.right)) {
            node.color = RED;
            node.left.color = BLACK;
            node.right.color = BLACK;
        }
 
        int cmp = key.compareTo(node.key);
 
        if (cmp < 0) {
            node.left = insert(node.left, key, value, BLACK); // /*BLACK was
                                                                // isRed
                                                                // before*/
 
            if (isRed(node) && isRed(node.left) && isRed) {
                node = rotateRight(node);
            }
 
            if (isRed(node.left) && isRed(node.left.left)) {
                node = rotateRight(node);
                node.color = BLACK;
                node.right.color = RED;
            }
 
        } else {
            node.right = insert(node.right, key, value, RED);
 
            if (isRed(node) && isRed(node.right) && !isRed) {
                node = rotateLeft(node);
            }
 
            if (isRed(node.right) && isRed(node.right.right)) {
                node = rotateLeft(node);
                node.color = BLACK;
                node.left.color = RED;
            }
        }
        return node;
    }
 
    public void insert(TKey key, TValue value) {
        this.root = insert(this.root, key, value, BLACK);
        this.root.color = BLACK;
    }
 
    private void printDotGraph() {
        System.out.println("//2-3-4 Red-Black Tree in graphviz dot-Format:");
        printDotNode(root, true, 0);
    }
 
    private void printDotNode(Node node, boolean isRoot, int index) {
        if (isRoot) {
            System.out.printf("digraph g0 {%n");
            System.out.printf("node [height=.1, style=filled];%n");
        }
 
        if (node != null) {
            System.out
                    .printf("node%s_%s[label=\"%s\", color=black, fillcolor=%s, fontcolor=%s];%n",
                            index, node.key, node.value, isRed(node) ? "red"
                                    : "black", isRed(node) ? "black" : "white");
 
            if (node.left != null) {
                printDotNode(node.left, false, index + 1);
                System.out.printf("node%s_%s -> node%s_%s;%n", index, node.key,
                        index + 1, node.left.key);
            } else {
                System.out
                        .printf("nil_node_l_%s_%s[ width=.3, fontsize=7, label=\"NIL\", color=black, fontcolor=white, shape=record ];%n",
                                index, node.key);
                System.out.printf("node%s_%s -> nil_node_l_%s_%s;%n", index,
                        node.key, index, node.key);
            }
 
            if (node.right != null) {
                printDotNode(node.right, false, index + 1);
                System.out.printf("node%s_%s -> node%s_%s;%n", index, node.key,
                        index + 1, node.right.key);
            } else {
                System.out
                        .printf("nil_node_r_%s_%s[ width=.3, fontsize=7, label=\"NIL\", color=black, fontcolor=white, shape=record ];%n",
                                index, node.key);
                System.out.printf("node%s_%s -> nil_node_r_%s_%s;%n", index,
                        node.key, index, node.key);
            }
        } else {
            System.out
                    .printf("nil_node_root_%s[width=.3, fontsize=7, label=\"NIL\", color=black, fontcolor=white, shape=record ];%n",
                            index);
        }
 
        if (isRoot) {
            System.out.printf("}");
        }
    }
 
    private static void outputRedBlackTreeWithRandomElements(int elementCount,
            int seed, int maxRandomNumberExclusive) {
        System.out.println("//RedBack_" + elementCount + "_elements");
        RedBlackTree<String, String> tree = new RedBlackTree<String, String>();
        Random random = new Random(seed);
 
        BitSet alreadySeen = new BitSet(maxRandomNumberExclusive);
        for (int i = 0; i < elementCount;) {
            int value = random.nextInt(maxRandomNumberExclusive);
 
            if (!alreadySeen.get(value)) {
                alreadySeen.set(value);
                i++;
                tree.insert(String.valueOf(value), "V-" + String.valueOf(value));
            }
        }
 
        tree.printDotGraph();
    }
 
    public static void main(String[] args) {
        outputRedBlackTreeWithRandomElements(20, 4711, 1000);
        //outputRedBlackTreeWithRandomElements(100, 4711, 1000);
        //outputRedBlackTreeWithRandomElements(350, 4711, 1000);
    }
}
Gruß Tom
 

Fred12

Grünschnabel
#2
hi, hab mal ne Frage... deckt deine rechts bzw linksrotation wirklich alle fälle ab?

wenn man nur vater und kindknoten hat , geht eine RR ja nicht wenns ein rechtes kind vom vater ist..
wenns ein linkes kind ist muss man nur vater und kind tauschen...
wenn man noch großvater hat und macht eine RR um den GV ist der GV rechtes kind vom Vater und der Vaterknoten wird oben an den vorgänger vom großvater angehängt ..
usw... da gibs doch noch mehr fälle oder seh ich das falsch? genauso beim linken knoten...
 

Fred12

Grünschnabel
#4
Ich kann kein Testcase aufsetzen, dafür bräucht ich den kompletten Baum :p und ich bin auch noch Anfänger...
aber in den beispielen kann ich nirgends ein rot schwarz baum erkennen...
ich weiss nur dass man verschiedene Fälle analysieren muss beim einfügen eines Knotens und dem anschließenden Ausbalancieren des Baums...
 
Zuletzt bearbeitet:

Fred12

Grünschnabel
#5
ausserdem check ich deine Methode insert nicht, bei insert gibst du ja einen KNoten als parameter an, nur welchen? Wenn node == null ist , dann fügst du einen Anfangsknoten ein als "root" also die Wurzel, und diesen gibst du am Ende zurueck (return node), und wie gehts dann weiter?
Beim Einfuegen eines 2ten Knotens, wo fängst du dann wieder an? Bei root oder bei dem zuletzt eingefuegten KnoteN? Weil man muss ja eigentlich einen Knoten als root festlegen , und von diesem aus die Knotenkeywerte mit dem neuen knotenkeywert vergleichen sonst machts kein Sinn
 
#6
Hallo,

in Anbetracht dessen, dass das Beispiel schon 4 Jahre alt ist und bisher niemand darauf geantwortet hat, finde ich es etwas schade das du deine Fragen in einem IMHO etwas patzigen Ton schreibst - aber okay.
...
Beim Einfuegen eines 2ten Knotens, wo fängst du dann wieder an? Bei root oder bei dem zuletzt eingefuegten KnoteN?
...
...
weil man muss ja eigentlich einen Knoten als root festlegen , und von diesem aus die Knotenkeywerte mit dem neuen knotenkeywert vergleichen sonst machts kein Sinn
..-
Laut Implementierung der Methode:
Java:
    public void insert(TKey key, TValue value) {
        this.root = insert(this.root, key, value, BLACK);
        this.root.color = BLACK;
    }
wird der Root-Knoten beim Einfügen wenn nötig neu definiert - dabei fängt man
beim einfügen eines zweiten bzw. weiteren Knotens beim Root-Knoten
(der nun nicht mehr null ist) an und sucht eine entsprechende Einfügestelle... Wie gesagt das
Verfahren ist so aus dem oben genannten Buch entnommen.

Außerdem ist das Beispiel, wie man leicht sieht, ja nur ein kleiner Teil einer Rot-Schwarz-Baum Implementierung und keines Falls vollständig. Da fehlen z.Bsp. noch entsprechende Update- / Delete- / Tranversierungs-Methoden.

Gruß Tom
 

Fred12

Grünschnabel
#7
sry wenn es patzig geklungen hat, sollte ganz neutral sein ;)

aber wenn ich einen Knoten einfügen und der mein root ist, und ich beim nächsten mal ein kleineren knoten einfüge , also an linker Seite, und diesen als mein neuen root definiere, dann hab ich ein PRoblem wenn ich beim 3ten einfügen einen KNoten einfüge der grösser als beide vorhergehenden KNoten ist und füge erst beim zweiten (neu definierten Knoten) rechts ein dann ist das falsch weil ich eigentlich beim 1ten root schon nach rechts hätte gehen müssen oder seh ich das falsch?
 

Fred12

Grünschnabel
#8
hi,

hab dein Programm mal durchgetestet mit verschiedenen Strings als Werten, die werden zwar richtig eingeordnet links bzw rechts von root, der baum wird aber nicht ausbalanciert, hat also leider nichts mit einem Rot-Schwarz-Baum zu tun...
 
#9
Hallo,

den Algorithmus findet man wie bereits erwähnt, in einer etwas kryptischen Form,
im Buch Algorithmen in Java 3., aktualisierte Auflage Teil 1-4:
http://www.pearson-studium.de/main/main.asp?page=bookdetails&ProductID=37201

Bei dem Algorithmus handelt es sich um die Einfüge-Routine in einen 2-3-4 Baum mit Hilfe der Rot Scharz Darstellung.
...2-3-4-Bäume werden beispielsweise durch Rot-Schwarz-Bäume implementiert....
Siehe: http://de.wikipedia.org/wiki/2-3-4-Baum

In der obigen Variante sind tatsächlich Fehler:

in Zeile 72 muss es heißen:
Java:
...
if (node == null) {
	return new Node(key, value, RED); //RED was isRed
}
...
und in Zeile 84 muss es heißen:
Java:
...
node.left = insert(node.left, key, value, BLACK); ///*BLACK was isRed before*/
...
Diese Fehler habe ich jetzt in der unten stehenden Version behoben - ich hätte das "damals" besser wohl testen müssen - danke für das wache Auge :) schau doch mal bitte nach, ob die Fehler auch aus deiner Sicht behoben sind.

Ich habe das Beispiel mal um eine Routine zur Ausgabe der Rot-Schwarz-Baum Struktur im Graphviz .dot-Format erweitert.

Hier der Download für die Graphviz Umgebung (Windows)
http://www.graphviz.org/Download_windows.php

Wenn man sich Graphviz installiert hat, kann man sich Beispielsweise über das Tool GVEdit die grafische Darstellung der in den .dot Files beschriebenen Graph-Strukturen anschauen.

In der obigen (fehlerhaften Version) sieht der Graph der Baumstruktur wie folgt aus:
Man erkennt schnell, dass der Baum tatsächlich nicht korrekt balanciert wird.
red_black_tree_wrong_balancing_3.png


Gefixte-Variante:
Java:
package de.tutorials;

import java.util.BitSet;
import java.util.Random;

/**
 * @author Thomas.Darimont
 * 
 */
public class RedBlackTree<TKey extends Comparable<TKey>, TValue> {

	private class Node {
		private Node left, right;
		private boolean color;
		private TKey key;
		private TValue value;

		public Node(TKey key, TValue value, boolean color) {
			this.key = key;
			this.value = value;
			this.color = color;
		}

		@Override
		public String toString() {
			return key + ": value " + (color ? "R" : "B");
		}
	}

	private static final boolean RED = true;
	private static final boolean BLACK = false;
	private Node root;

	public TValue get(TKey key) {
		Node node = root;

		while (node != null) {
			int cmp = key.compareTo(node.key);
			if (cmp < 0) {
				node = node.left;
			} else if (cmp > 0) {
				node = node.right;
			} else if (cmp == 0) {
				return node.value;
			}
		}

		return null;
	}

	private boolean isRed(Node node) {
		if (node == null) {
			return false;
		}
		return node.color;
	}

	private Node rotateLeft(Node h) {
		Node x = h.right;
		h.right = x.left;
		x.left = h;
		return x;
	}

	private Node rotateRight(Node h) {
		Node x = h.left;
		h.left = x.right;
		x.right = h;
		return x;
	}

	private Node insert(Node node, TKey key, TValue value, boolean isRed) {

		if (node == null) {
			return new Node(key, value, RED); // RED was isRed before
		}

		if (isRed(node.left) && isRed(node.right)) {
			node.color = RED;
			node.left.color = BLACK;
			node.right.color = BLACK;
		}

		int cmp = key.compareTo(node.key);

		if (cmp < 0) {
			node.left = insert(node.left, key, value, BLACK); // /*BLACK was
																// isRed
																// before*/

			if (isRed(node) && isRed(node.left) && isRed) {
				node = rotateRight(node);
			}

			if (isRed(node.left) && isRed(node.left.left)) {
				node = rotateRight(node);
				node.color = BLACK;
				node.right.color = RED;
			}

		} else {
			node.right = insert(node.right, key, value, RED);

			if (isRed(node) && isRed(node.right) && !isRed) {
				node = rotateLeft(node);
			}

			if (isRed(node.right) && isRed(node.right.right)) {
				node = rotateLeft(node);
				node.color = BLACK;
				node.left.color = RED;
			}
		}
		return node;
	}

	public void insert(TKey key, TValue value) {
		this.root = insert(this.root, key, value, BLACK);
		this.root.color = BLACK;
	}

	private void printDotGraph() {
		System.out.println("//2-3-4 Red-Black Tree in graphviz dot-Format:");
		printDotNode(root, true, 0);
	}

	private void printDotNode(Node node, boolean isRoot, int index) {
		if (isRoot) {
			System.out.printf("digraph g0 {%n");
			System.out.printf("node [height=.1, style=filled];%n");
		}

		if (node != null) {
			System.out
					.printf("node%s_%s[label=\"%s\", color=black, fillcolor=%s, fontcolor=%s];%n",
							index, node.key, node.value, isRed(node) ? "red"
									: "black", isRed(node) ? "black" : "white");

			if (node.left != null) {
				printDotNode(node.left, false, index + 1);
				System.out.printf("node%s_%s -> node%s_%s;%n", index, node.key,
						index + 1, node.left.key);
			} else {
				System.out
						.printf("nil_node_l_%s_%s[ width=.3, fontsize=7, label=\"NIL\", color=black, fontcolor=white, shape=record ];%n",
								index, node.key);
				System.out.printf("node%s_%s -> nil_node_l_%s_%s;%n", index,
						node.key, index, node.key);
			}

			if (node.right != null) {
				printDotNode(node.right, false, index + 1);
				System.out.printf("node%s_%s -> node%s_%s;%n", index, node.key,
						index + 1, node.right.key);
			} else {
				System.out
						.printf("nil_node_r_%s_%s[ width=.3, fontsize=7, label=\"NIL\", color=black, fontcolor=white, shape=record ];%n",
								index, node.key);
				System.out.printf("node%s_%s -> nil_node_r_%s_%s;%n", index,
						node.key, index, node.key);
			}
		} else {
			System.out
					.printf("nil_node_root_%s[width=.3, fontsize=7, label=\"NIL\", color=black, fontcolor=white, shape=record ];%n",
							index);
		}

		if (isRoot) {
			System.out.printf("}");
		}
	}

	private static void outputRedBlackTreeWithRandomElements(int elementCount,
			int seed, int maxRandomNumberExclusive) {
		System.out.println("//RedBack_" + elementCount + "_elements");
		RedBlackTree<String, String> tree = new RedBlackTree<String, String>();
		Random random = new Random(seed);

		BitSet alreadySeen = new BitSet(maxRandomNumberExclusive);
		for (int i = 0; i < elementCount;) {
			int value = random.nextInt(maxRandomNumberExclusive);

			if (!alreadySeen.get(value)) {
				alreadySeen.set(value);
				i++;
				tree.insert(String.valueOf(value), "V-" + String.valueOf(value));
			}
		}

		tree.printDotGraph();
	}

	public static void main(String[] args) {
		outputRedBlackTreeWithRandomElements(20, 4711, 1000);
		//outputRedBlackTreeWithRandomElements(100, 4711, 1000);
		//outputRedBlackTreeWithRandomElements(350, 4711, 1000);
	}
}
Hier die Grafik für die "fixed" Insert-Routine (mit passendem Balancing):
red_black_tree_fixed_balancing_3.png

Hier die .dot Graph Beschreibung:
Code:
//RedBack_20_elements
//2-3-4 Red-Black Tree in graphviz dot-Format:
digraph g0 {
node [height=.1, style=filled];
node0_515[label="V-515", color=black, fillcolor=black, fontcolor=white];
node1_240[label="V-240", color=black, fillcolor=red, fontcolor=black];
node2_20[label="V-20", color=black, fillcolor=black, fontcolor=white];
node3_121[label="V-121", color=black, fillcolor=black, fontcolor=white];
node4_107[label="V-107", color=black, fillcolor=red, fontcolor=black];
nil_node_l_4_107[ width=.3, fontsize=7, label="NIL", color=black, fontcolor=white, shape=record ];
node4_107 -> nil_node_l_4_107;
nil_node_r_4_107[ width=.3, fontsize=7, label="NIL", color=black, fontcolor=white, shape=record ];
node4_107 -> nil_node_r_4_107;
node3_121 -> node4_107;
node4_161[label="V-161", color=black, fillcolor=red, fontcolor=black];
nil_node_l_4_161[ width=.3, fontsize=7, label="NIL", color=black, fontcolor=white, shape=record ];
node4_161 -> nil_node_l_4_161;
nil_node_r_4_161[ width=.3, fontsize=7, label="NIL", color=black, fontcolor=white, shape=record ];
node4_161 -> nil_node_r_4_161;
node3_121 -> node4_161;
node2_20 -> node3_121;
node3_211[label="V-211", color=black, fillcolor=black, fontcolor=white];
nil_node_l_3_211[ width=.3, fontsize=7, label="NIL", color=black, fontcolor=white, shape=record ];
node3_211 -> nil_node_l_3_211;
node4_229[label="V-229", color=black, fillcolor=red, fontcolor=black];
nil_node_l_4_229[ width=.3, fontsize=7, label="NIL", color=black, fontcolor=white, shape=record ];
node4_229 -> nil_node_l_4_229;
nil_node_r_4_229[ width=.3, fontsize=7, label="NIL", color=black, fontcolor=white, shape=record ];
node4_229 -> nil_node_r_4_229;
node3_211 -> node4_229;
node2_20 -> node3_211;
node1_240 -> node2_20;
node2_349[label="V-349", color=black, fillcolor=black, fontcolor=white];
node3_291[label="V-291", color=black, fillcolor=black, fontcolor=white];
nil_node_l_3_291[ width=.3, fontsize=7, label="NIL", color=black, fontcolor=white, shape=record ];
node3_291 -> nil_node_l_3_291;
nil_node_r_3_291[ width=.3, fontsize=7, label="NIL", color=black, fontcolor=white, shape=record ];
node3_291 -> nil_node_r_3_291;
node2_349 -> node3_291;
node3_471[label="V-471", color=black, fillcolor=black, fontcolor=white];
node4_407[label="V-407", color=black, fillcolor=red, fontcolor=black];
nil_node_l_4_407[ width=.3, fontsize=7, label="NIL", color=black, fontcolor=white, shape=record ];
node4_407 -> nil_node_l_4_407;
nil_node_r_4_407[ width=.3, fontsize=7, label="NIL", color=black, fontcolor=white, shape=record ];
node4_407 -> nil_node_r_4_407;
node3_471 -> node4_407;
nil_node_r_3_471[ width=.3, fontsize=7, label="NIL", color=black, fontcolor=white, shape=record ];
node3_471 -> nil_node_r_3_471;
node2_349 -> node3_471;
node1_240 -> node2_349;
node0_515 -> node1_240;
node1_706[label="V-706", color=black, fillcolor=black, fontcolor=white];
node2_664[label="V-664", color=black, fillcolor=black, fontcolor=white];
node3_530[label="V-530", color=black, fillcolor=red, fontcolor=black];
nil_node_l_3_530[ width=.3, fontsize=7, label="NIL", color=black, fontcolor=white, shape=record ];
node3_530 -> nil_node_l_3_530;
nil_node_r_3_530[ width=.3, fontsize=7, label="NIL", color=black, fontcolor=white, shape=record ];
node3_530 -> nil_node_r_3_530;
node2_664 -> node3_530;
node3_670[label="V-670", color=black, fillcolor=red, fontcolor=black];
nil_node_l_3_670[ width=.3, fontsize=7, label="NIL", color=black, fontcolor=white, shape=record ];
node3_670 -> nil_node_l_3_670;
nil_node_r_3_670[ width=.3, fontsize=7, label="NIL", color=black, fontcolor=white, shape=record ];
node3_670 -> nil_node_r_3_670;
node2_664 -> node3_670;
node1_706 -> node2_664;
node2_921[label="V-921", color=black, fillcolor=red, fontcolor=black];
node3_87[label="V-87", color=black, fillcolor=black, fontcolor=white];
nil_node_l_3_87[ width=.3, fontsize=7, label="NIL", color=black, fontcolor=white, shape=record ];
node3_87 -> nil_node_l_3_87;
nil_node_r_3_87[ width=.3, fontsize=7, label="NIL", color=black, fontcolor=white, shape=record ];
node3_87 -> nil_node_r_3_87;
node2_921 -> node3_87;
node3_962[label="V-962", color=black, fillcolor=black, fontcolor=white];
node4_949[label="V-949", color=black, fillcolor=red, fontcolor=black];
nil_node_l_4_949[ width=.3, fontsize=7, label="NIL", color=black, fontcolor=white, shape=record ];
node4_949 -> nil_node_l_4_949;
nil_node_r_4_949[ width=.3, fontsize=7, label="NIL", color=black, fontcolor=white, shape=record ];
node4_949 -> nil_node_r_4_949;
node3_962 -> node4_949;
nil_node_r_3_962[ width=.3, fontsize=7, label="NIL", color=black, fontcolor=white, shape=record ];
node3_962 -> nil_node_r_3_962;
node2_921 -> node3_962;
node1_706 -> node2_921;
node0_515 -> node1_706;
}
Zum Spaß hier mal noch ein Beispielbaum mit 350 Elementen:
(Im Anhang das Bild im zip-Archiv- Das Forum rechnet das Bild leider automatisch klein...)
red_black_tree_fixed_balancing_350.jpg

Gruß Tom
 

Anhänge

Fred12

Grünschnabel
#10
ok eine Frage hab ich noch, was passiert bei den Methoden
Java:
if (isRed(node) && isRed(node.right) && !isRed)
und
if (isRed(node) && isRed(node.left) && isRed)
? was bedeutet &&isRed am Ende? bzw für was gilt das?

naja egal ich habs getestet und jetzt klappts auch wieder mit der Rebalancierung :)
 
Zuletzt bearbeitet:

Neue Beiträge