You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
344 lines
13 KiB
344 lines
13 KiB
import java.io.FileWriter;
|
|
import java.io.IOException;
|
|
//
|
|
class RBTree<T extends Comparable<T>> {
|
|
|
|
private static final boolean RED = true;
|
|
private static final boolean BLACK = false;
|
|
|
|
private class Node {
|
|
T key; // Node<Integer>, generischer Datentyp, der Schlüssel (key) des Knotens vom Typ Integer ist.
|
|
Node left, right, parent; // Elternknoten hinzugefügt
|
|
boolean color;
|
|
|
|
public Node(T key) { // Konstruktor von Node-Class
|
|
this.key = key;
|
|
left = right = parent = null;
|
|
this.color = true; // Neue Knoten sind standardmäßig rot
|
|
}
|
|
}
|
|
|
|
private Node root;
|
|
|
|
|
|
public void insertNode(T key) { // hier nicht int-DT, sondern T,
|
|
// mit jedem vergleichbaren Datentyp (T)
|
|
// verwendet werden kann, solange dieser das Comparable-Interface implementiert.
|
|
|
|
Node node = root;
|
|
Node parent = null;
|
|
|
|
// Traverse the tree to the left or right depending on the key,
|
|
// finding a correct position for the insertion of nodes later + keep the structure of the tree
|
|
while (node != null) {
|
|
parent = node;
|
|
if (key.compareTo(node.key) < 0) { // key < node.key
|
|
node = node.left;
|
|
} else if (key.compareTo(node.key) > 0) { // key > node.key
|
|
node = node.right;
|
|
} else {
|
|
throw new IllegalArgumentException("BST already contains a node with key " + key);
|
|
}
|
|
}
|
|
|
|
// Insert new node
|
|
Node newNode = new Node(key);
|
|
newNode.color = true; // neuer Knoten immer rot
|
|
if (parent == null) {
|
|
root = newNode;
|
|
} else if (key.compareTo(parent.key) < 0) { // key < parent.key
|
|
parent.left = newNode;
|
|
} else if (key.compareTo(parent.key) > 0){ // key > parent.key
|
|
parent.right = newNode;
|
|
}
|
|
newNode.parent = parent; // etablieren die Verbindung des Knotens zu seinem Vater
|
|
fixAfterInsert(newNode);
|
|
}
|
|
|
|
private Node getUncle(Node parent) { // für spätere Implementierung fix()
|
|
Node grandparent = parent.parent;
|
|
|
|
if (grandparent.left == parent) {
|
|
return grandparent.right; // right is the uncle
|
|
|
|
} else if (grandparent.right == parent) {
|
|
return grandparent.left; // left is the uncle
|
|
|
|
} else {
|
|
throw new IllegalStateException("Parent is not a child of its grandparent");
|
|
}
|
|
}
|
|
|
|
private void fixAfterInsert(Node node) {
|
|
Node parent = node.parent;
|
|
|
|
// Case 1: no root, add node as new root, root is always black
|
|
if (parent == null) {
|
|
node.color = false;
|
|
return;
|
|
}
|
|
|
|
// Parent is black --> nothing to do
|
|
if (parent.color == false) { // Abbildung S.312, aber beide Knoten sind schon schwarz gefärbt
|
|
return;
|
|
}
|
|
|
|
// From here on, parent(vater) is red
|
|
Node grandparent = parent.parent;
|
|
|
|
Node uncle = getUncle(parent); // Get the uncle (maybe nil, in which case its color is BLACK)
|
|
|
|
// Case 3 (parent uncle red, Abbildung S.313, 314): recolor parent, grandparent
|
|
// and uncle
|
|
if (uncle != null && uncle.color == true) {
|
|
parent.color = false;
|
|
uncle.color = false;
|
|
grandparent.color = true;
|
|
|
|
// Call recursively for grandparent, which is now red. fix recursively
|
|
fixAfterInsert(grandparent);
|
|
}
|
|
|
|
// Parent is left child of grandparent
|
|
// Case 4a: Uncle is black(nil is default black) and node is left --> right
|
|
// "inner child" of its grandparent
|
|
else if (parent == grandparent.left) {
|
|
|
|
if (node == parent.right) {
|
|
rotateLeft(parent);
|
|
|
|
// Let "parent" point to the new root node of the rotated sub-tree.
|
|
// It will be recolored in the next step, which we're going to fall-through to.
|
|
parent = node;
|
|
}
|
|
|
|
// Case 5a: Uncle is black and node is left->left "outer child" of its grandparent
|
|
rotateRight(grandparent);
|
|
|
|
// Recolor original parent and grandparent
|
|
parent.color = false;
|
|
grandparent.color = true;
|
|
}
|
|
|
|
// Parent is right child of grandparent
|
|
else if (parent == grandparent.right) {
|
|
// Case 4b: Uncle is black and node is right->left "inner child" of its
|
|
// grandparent
|
|
if (node == parent.left) {
|
|
rotateRight(parent);
|
|
|
|
// Let "parent" point to the new root node of the rotated sub-tree.
|
|
// It will be recolored in the next step, which we're going to fall-through to.
|
|
parent = node;
|
|
}
|
|
|
|
// Case 5b: Uncle is black and node is right->right "outer child" of its
|
|
// grandparent
|
|
rotateLeft(grandparent);
|
|
|
|
// Recolor original parent and grandparent
|
|
parent.color = false;
|
|
grandparent.color = true;
|
|
}
|
|
}
|
|
|
|
private Node rotateLeft(Node node) {
|
|
Node rightChild = node.right;
|
|
Node parent = node.parent;
|
|
|
|
node.right = rightChild.left;
|
|
if (rightChild.left != null) {
|
|
rightChild.left.parent = node;
|
|
}
|
|
|
|
rightChild.left = node;
|
|
node.parent = rightChild;
|
|
|
|
rightChild.parent = parent;
|
|
if (parent == null) {
|
|
root = rightChild;
|
|
} else if (node == parent.left) {
|
|
parent.left = rightChild;
|
|
} else if (node == parent.right) {
|
|
parent.right = rightChild;
|
|
} else {
|
|
throw new IllegalStateException("Node is not a child of its parent");
|
|
}
|
|
|
|
|
|
RootBlack();
|
|
|
|
return rightChild;
|
|
}
|
|
|
|
private Node rotateRight(Node node) {
|
|
Node leftChild = node.left;
|
|
Node parent = node.parent;
|
|
|
|
node.left = leftChild.right;
|
|
if (leftChild.right != null) {
|
|
leftChild.right.parent = node;
|
|
}
|
|
|
|
leftChild.right = node;
|
|
node.parent = leftChild;
|
|
|
|
leftChild.parent = parent;
|
|
if (parent == null) {
|
|
root = leftChild;
|
|
} else if (node == parent.left) {
|
|
parent.left = leftChild;
|
|
} else if (node == parent.right) {
|
|
parent.right = leftChild;
|
|
} else {
|
|
throw new IllegalStateException("Node is not a child of its parent");
|
|
}
|
|
|
|
RootBlack();
|
|
|
|
return leftChild;
|
|
}
|
|
|
|
/* private void flipColors(Node node) {
|
|
node.color = !node.color;
|
|
node.left.color = !node.left.color;
|
|
node.right.color = !node.right.color;
|
|
} */
|
|
|
|
private void RootBlack() {
|
|
root.color = BLACK;
|
|
}
|
|
|
|
/*
|
|
* public void printDOTAfterInsert(String filename, T key) {
|
|
* try (FileWriter writer = new FileWriter(filename)) {
|
|
* writer.write("digraph G {\n");
|
|
* writer.write("\tnode [style=filled, color=black, shape=circle, width=.6,\n");
|
|
* writer.write("\t\tfontname=Helvetica, fontweight=bold, fontcolor=white,\n");
|
|
* writer.write("\t\tfontsize=24, fixedsize=true];\n");
|
|
*
|
|
* root = insert(root, null, key); // Füge das Element ein und aktualisiere den
|
|
* Baum
|
|
* printDOTRecursive(root, writer);
|
|
*
|
|
* writer.write("}\n");
|
|
* } catch (IOException e) {
|
|
* e.printStackTrace();
|
|
* }
|
|
* }
|
|
*/
|
|
|
|
public void printDOTAfterInsert(String filename) {
|
|
|
|
try (FileWriter writer = new FileWriter(filename)) {
|
|
writer.write("digraph G {\n");
|
|
writer.write("\tnode [style=filled, color=black, shape=circle, width=.6,\n");
|
|
writer.write("\t\tfontname=Helvetica, fontweight=bold, fontcolor=white,\n");
|
|
writer.write("\t\tfontsize=24, fixedsize=true];\n");
|
|
|
|
// Hier wird der gesamte Baum gezeichnet, nicht nur der neu eingefügte Schlüssel
|
|
printDOTRecursive(root, writer);
|
|
|
|
writer.write("}\n");
|
|
} catch (IOException e) {
|
|
e.printStackTrace();
|
|
}
|
|
}
|
|
|
|
private void printDOTRecursive(Node node, FileWriter writer) throws IOException {
|
|
if (node != null) {
|
|
String keyString = node.key.toString().replaceAll("[^a-zA-Z0-9]", "_");
|
|
String fillColor = (node.color == RED) ? "red" : "black";
|
|
String fontColor = (node.color == RED) ? "white" : "white";
|
|
|
|
writer.write("\t\"" + keyString + "\" [fillcolor=" + fillColor + ", fontcolor=" + fontColor + "];\n");
|
|
|
|
// Print parent link
|
|
/* if (node.parent != null) {
|
|
String parentKeyString = node.parent.key.toString().replaceAll("[^a-zA-Z0-9]", "_");
|
|
writer.write("\t\"" + parentKeyString + "\" -> \"" + keyString + "\" [style=dotted];\n");
|
|
} */
|
|
|
|
// Print left child
|
|
if (node.left != null) {
|
|
String leftKeyString = node.left.key.toString().replaceAll("[^a-zA-Z0-9]", "_");
|
|
writer.write("\t\"" + keyString + "\" -> \"" + leftKeyString + "\";\n");
|
|
printDOTRecursive(node.left, writer);
|
|
} else {
|
|
String leftNilKeyString = keyString + "_NIL_L";
|
|
writer.write("\t\"" + leftNilKeyString + "\" [shape=plaintext, label=\"NIL\", fontsize=16];\n");
|
|
writer.write("\t\"" + keyString + "\" -> \"" + leftNilKeyString + "\";\n");
|
|
}
|
|
|
|
// Print right child
|
|
if (node.right != null) {
|
|
String rightKeyString = node.right.key.toString().replaceAll("[^a-zA-Z0-9]", "_");
|
|
writer.write("\t\"" + keyString + "\" -> \"" + rightKeyString + "\";\n");
|
|
printDOTRecursive(node.right, writer);
|
|
} else {
|
|
String rightNilKeyString = keyString + "_NIL_R";
|
|
writer.write("\t\"" + rightNilKeyString + "\" [shape=plaintext, label=\"NIL\", fontsize=16];\n");
|
|
writer.write("\t\"" + keyString + "\" -> \"" + rightNilKeyString + "\";\n");
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
/*public void printDOTAfterInsert(String filename, T key) {
|
|
try (FileWriter writer = new FileWriter(filename)) {
|
|
writer.write("digraph G {\n");
|
|
writer.write("\tnode [style=filled, color=black, shape=circle, width=.6,\n");
|
|
writer.write("\t\tfontname=Helvetica, fontweight=bold, fontcolor=white,\n");
|
|
writer.write("\t\tfontsize=24, fixedsize=true];\n");
|
|
|
|
// Hier wird der gesamte Baum gezeichnet, nicht nur der neu eingefügte Schlüssel
|
|
printDOTRecursive(root, writer);
|
|
|
|
writer.write("}\n");
|
|
} catch (IOException e) {
|
|
e.printStackTrace();
|
|
}
|
|
}
|
|
|
|
private void printDOTRecursive(Node node, FileWriter writer) throws IOException {
|
|
if (node != null) {
|
|
String keyString = node.key.toString().replaceAll("[^a-zA-Z0-9]", "_");
|
|
String fillColor = (node.color == RED) ? "red" : "black";
|
|
String fontColor = (node.color == RED) ? "white" : "white";
|
|
|
|
writer.write("\t\"" + keyString + "\" [fillcolor=" + fillColor + ", fontcolor=" + fontColor + "];\n");
|
|
|
|
/*
|
|
* Print parent link
|
|
* if (node.parent != null) {
|
|
* String parentKeyString =
|
|
* node.parent.key.toString().replaceAll("[^a-zA-Z0-9]", "_");
|
|
* writer.write("\t\"" + parentKeyString + "\" -> \"" + keyString +
|
|
* "\" [style=dotted];\n");
|
|
* }
|
|
|
|
|
|
// Print left child
|
|
if (node.left != null) {
|
|
String leftKeyString = node.left.key.toString().replaceAll("[^a-zA-Z0-9]", "_");
|
|
writer.write("\t\"" + keyString + "\" -> \"" + leftKeyString + "\";\n");
|
|
printDOTRecursive(node.left, writer);
|
|
} else {
|
|
String leftNilKeyString = keyString + "_NIL_L";
|
|
writer.write("\t\"" + leftNilKeyString + "\" [shape=plaintext, label=\"NIL\", fontsize=16];\n");
|
|
writer.write("\t\"" + keyString + "\" -> \"" + leftNilKeyString + "\";\n");
|
|
}
|
|
|
|
// Print right child
|
|
if (node.right != null) {
|
|
String rightKeyString = node.right.key.toString().replaceAll("[^a-zA-Z0-9]", "_");
|
|
writer.write("\t\"" + keyString + "\" -> \"" + rightKeyString + "\";\n");
|
|
printDOTRecursive(node.right, writer);
|
|
} else {
|
|
String rightNilKeyString = keyString + "_NIL_R";
|
|
writer.write("\t\"" + rightNilKeyString + "\" [shape=plaintext, label=\"NIL\", fontsize=16];\n");
|
|
writer.write("\t\"" + keyString + "\" -> \"" + rightNilKeyString + "\";\n");
|
|
}
|
|
}
|
|
*/
|
|
}
|