Die fünfte Abgabe in DSAL.
Hier der Java-Code, welcher (vielleicht) zur Generierung der RS-Bäume verwendet wurde. Im großen und ganzen ist er aus der Vorlesung von Prof. Woeginger geklaut. Theoretisch kann dieser Code durch minimale anpassung auch AVL- bzw normale binäre Bäume ausgeben, dies ist aber nicht getestet.
Damit LaTeX diese Figuren Compiliert, müssen die Requirements aus LaTeX-Snippets: Rot-Schwarz-Bäume erfüllt sein.
ACHTUNG: Die Methoden zum Löschen aus einem RS-Baum funktionieren aus einem mir nicht erklärbaren Grund nicht.
Ich entschuldige mich für die komische Formatierung, ich war zu faul Emacs umzustellen.
a11.java
public class a11{
public static void main(String[] args){
Tree t = new Tree();
t.root = new Node();
t.root.color=Color.BLACK;
t.root.key=6;
System.out.println("\\newsubsubproblem[1]");
t.toTeX("\\texttt{Einf\\\"uge-Operation} von 6");
//2
System.out.println("\\newsubsubproblem[2]");
Tree.rbtIns(t,new Node(0));
//3.
System.out.println("\\newsubsubproblem[3]");
Tree.rbtIns(t,new Node(2));
//4.
System.out.println("\\newsubsubproblem[4]");
Tree.rbtIns(t,new Node(19));
//5.
System.out.println("\\newsubsubproblem[5]");
Tree.rbtIns(t,new Node(12));
//6.
System.out.println("\\newsubsubproblem[6]");
Tree.rbtIns(t,new Node(12));
}
}
Node.java:
public class Node {
int key;
Node left, right;
Node parent;
Color color;
static Color BLACK = Color.BLACK;
static Color RED = Color.RED;
public Node(){
}
public Node(int k){
key=k;
}
public Node(int k,Color c){
key=k;
color= c;
}
public Node(int k,Color c, Node l, Node r){
key=k;
color= c;
left=l;
right=r;
}
public String toTeX() {
String result = "node [";
if (color == RED) {
result = result + "redTreeNode";
} else {
result = result + "blackTreeNode";
}
//Children
result = result + "] {" + key + "}\nchild { \n";
if (left == null) {
result = result + "node [externalBlackNode] {}";
} else {
result = result + left.toTeX();
}
result = result + "} \nchild { \n";
if(right==null)
{
result = result + "node [externalBlackNode] {}";
}else
{
result = result + right.toTeX();
}
result=result+"}\n";
return result;
}
}
Tree.java
import java.lang.Math;
public class Tree{
Node root;
static Color BLACK = Color.BLACK;
static Color RED = Color.RED;
//VL 10 Folie 16
static void bstIns ( Tree t, Node node)
{ // Fuege node in t ein
// Suche freien Platz
Node root = t.root;
Node parent = null;
while (root!=null)
{
parent = root;
if ( node.key < root.key ){
root = root.left;
} else {
root = root.right;
}
} // Einfuegen
node.parent = parent;
if (parent==null) { // t war leer = > neue Wurzel
t.root = node;
} else if ( node.key < parent.key ) { // richtige Seite
parent.left = node;
} else {
parent.right = node;
}
}
//VL 10 Folie 22
// Ersetzt im Baum t den Teilbaum old durch
// den Teilbaum node ( ohne Sortierung !)
static void bstReplace ( Tree t , Node old , Node node ) {
if ( node!=null ) { // erlaube node == null !
node.parent = old.parent;
% System.out.println("Node == null");
}
if (old.parent==null) { // war die Wurzel
t.root = node ;
} else if ( old == old.parent.left ) {
// war linkes Kind
old.parent.left = node ;
} else { // rechtes Kind
old.parent.right = node ;
}
}
static Node bstMin ( Node root ) { // root != null
while ( root.left!=null) {
root = root.left ;
}
return root ;
}
//VL 10 Folie 20
static Node bstSucc ( Node node ) // node != nul
{
if ( node.right!=null) {
return bstMin ( node.right );
}
// Abbruch, wenn node nicht mehr rechtes Kind
// oder wenn node.parent leer
while ( node.parent!=null && node.parent.right == node ) {
node = node.parent;
}
return node.parent;
}
//VL 10 Folie 28
// Entfernt node aus dem Baum .
// Danach kann node ggf.aus Speicher entfernt werden
static void bstDel ( Tree t, Node node )
{
if ( node.left!=null && node.right!=null ) { // zwei Kinder
Node tmp = bstMin ( node.right );
bstDel (t, tmp ); // hochstens ein Kind, rechts
bstSwap (t, node, tmp );
} else if ( node.left!=null ) { // ein Kind, links
bstReplace (t, node, node.left );
} else { // ein oder kein Kind ( node.right == null )
bstReplace (t, node, node.right );
}
}
// Tauscht den Knoten old gegen node aus ;
// die Kinder von old sind weiterhin im BST !
static void bstSwap ( Tree t , Node old , Node node ) {
// uebernimm linken Teilbaum
node.left = old.left ; // auch moeglich : swap ()
if ( node.left!=null ) {
node.left.parent = node ;
}
// rechten Teilbaum
node.right = old . right ;
if ( node.right!=null ) {
node.right.parent = node ;
}
// fuege den Knoten ein
bstReplace (t , old , node ) ;
}
//VL 10 Folie 34
static void leftRotate ( Tree t, Node node1 )
{
// voellig analog : rightRotate ()
Node node2 = node1.right;
// Baum B verschieben
node1.right = node2.left;
if ( node1.right!=null ) {
node1.right.parent = node1;
}
// node2 wieder einhaengen
node2.parent = node1.parent;
if ( node1.parent==null ) { // node1 war die Wurzel
t.root = node2;
} else if ( node1 == node1.parent.left ) {
node2.parent.left = node2;
} else { // war rechtes Kind
node2.parent.right = node2;
}
// node1 einhaengen
node2.left = node1;
node1.parent = node2;
t.toTeX("\\texttt{Left-Rotate} \\\"uber "+node1.key);
}
//VL 10 Folie 34
static void rightRotate ( Tree t, Node node1 )
{
// voellig analog : rightRotate ()
Node node2 = node1.left;
// Baum B verschieben
node1.left = node2.right;
if ( node1.left!=null ) {
node1.left.parent = node1;
}
// node2 wieder einhaengen
node2.parent = node1.parent;
if ( node1.parent==null ) { // node1 war die Wurzel
t.root = node2;
} else if ( node1 == node1.parent.right ) {
node2.parent.right = node2;
} else { // war linkes Kind
node2.parent.left = node2;
}
// node1 einhaengen
node2.right = node1;
node1.parent = node2;
t.toTeX("\\texttt{Right-Rotate} \\\"uber "+node1.key);
}
//VL 10 Folie 39
static void AVLIns ( Tree t, Node node ) {
bstIns (t, node );
// Node d e e p e s t U n b a l a n c e d N o d e ( Tree t, Node node )
// gibt null zurueck wenn t balanziert ist
// und den tiefsten unbalan zierten Knoten in t sonst
// ( der Parameter node wird zur effizienten
// I mp l em en ti er u ng verwendet )
Node A = deepestUnbalancedNode(t, node);
if ( A != null ) balance (t, A );
}
//VL 10 Folie 40
static void balance ( Tree t, Node A ) {
// A ist tiefster unbala nzierter Knoten in t
if ( height ( A.left ) > height ( A.right ) ) {
if ( height ( A.left.left ) >= height ( A.left.right ) ) {// LL
rightRotate (t, A );
} else { // LR
leftRotate (t, A.left ); rightRotate (t, A );
}
} else {
if ( height ( A.right.right ) >= height ( A.right.left ) ) {
// RR
leftRotate (t, A );
} else { // RL
rightRotate (t, A.right ); leftRotate (t, A );
}
}
}
//VL 10 Folie 42
static void AVLDel ( Tree t, Node node ) {
bstDel (t, node );
// Node d e e p e s t U n b a l a n c e d N o d e ( Tree t, Node node )
// gibt null zurueck wenn t balanziert ist
// und den tiefsten unb alanzier ten Knoten in t sonst
//( der Parameter node wird zur effizienten
// Im pl e me nt ie r un g verwendet )
Node A = deepestUnbalancedNode (t, node );
while ( A != null )
{
// bool balanced ( Tree t, Node A )
// gibt true zurueck wenn A balanziert ist in t
// und false sonst
if (! balanced (t, A ) ) {
balance (t, A );
A = A.parent.parent;
} else {
A = A.parent;
}
}
}
//VL 11 Folie 13
static void rbtIns ( Tree t , Node node ) {
// Fuege node in den Baum t ein
bstIns(t , node ) ; // Einfuegen wie beim BST
node.left = null ;
node.right = null ;
node.color = RED ;
t.toTeX("\\texttt{Einf\\\"uge-Operation} von "+node.key);
// eingefuegter Knoten immer zunaechst rot
// stelle Rot - Schwarz - Eigenschaft ggf . wieder her
rbtInsFix (t , node ) ;
}
//VL 11 Folie 18
// Behebe eventuelle Rot - Rot - Verletzung mit Vater
// Knoten node ist rot
static void rbtInsFix ( Tree t , Node node ) {
// solange noch eine Rot - Rot - Verletzung besteht
while ( node.parent != null && node . parent . color == RED ) {
if ( node . parent == node . parent . parent . left ) {
// der von uns betrachtete Fall
node = leftAdjust (t , node ) ;
// node jetzt weiter oben ?
// ( node = node . parent . parent im Fall 1 von
// leftAdjust )
} else {
// der dazu symmetrischer Fall
node = rightAdjust (t , node ) ;
}
}
t . root . color = BLACK ; // Wurzel bleibt schwarz
}
//VL 11 Folie 19
static Node leftAdjust ( Tree t , Node node ) {
Node uncle = node.parent.parent.right ;
if ( uncle != null && uncle.color == RED ) { // Fall 1
node.parent.parent.color = RED ; // Grossvater
node.parent.color = BLACK ; // Vater
uncle.color = BLACK ; // Onkel
t.toTeX("\\texttt{Umf\\\"arbung}");
return node.parent.parent ; // pruefe Rot - Rot weiter
// oben
} else { // Fall 2 und 3
if ( node == node.parent.right ) { // Fall 2
// dieser Knoten wird das linke , rote Kind :
node = node.parent ;
leftRotate (t , node ) ;
} // Fall 3
rightRotate (t , node . parent . parent ) ;
node.parent.color = BLACK ;
node.parent.right.color = RED ;
t.toTeX("\\texttt{Umf\\\"arbung}");
return node ; // fertig , node . parent . color == BLACK
}
}
//Analog zu VL 11 FOlie 19
static Node rightAdjust ( Tree t , Node node ) {
Node uncle = node.parent.parent.left ;
if ( uncle != null && uncle.color == RED ) { // Fall 1
node.parent.parent.color = RED ; // Grossvater
node.parent.color = BLACK ; // Vater
uncle.color = BLACK ; // Onkel
t.toTeX("\\texttt{Umf\\\"arbung}");
return node.parent.parent ; // pruefe Rot - Rot weiter
// oben
} else { // Fall 2 und 3
if ( node == node.parent.left ) { // Fall 2
// dieser Knoten wird das linke , rote Kind :
node = node.parent ;
rightRotate (t , node ) ;
} // Fall 3
leftRotate (t , node . parent . parent ) ;
node.parent.color = BLACK ;
node.parent.left.color = RED ;
t.toTeX("\\texttt{Umf\"arbung}");
return node ; // fertig , node . parent . color == BLACK
}
}
//VL 11 Folie 29
// Entfernt node aus dem Baum .
static void rbtDel ( Tree t , Node node ) {
if ( node . left!=null && node . right!=null ) { // zwei Kinder
Node tmp = bstMin ( node . right ) ; // finde Nachfolger
rbtDel (t , tmp ) ; // loesche Nachfolger
bstSwap (t , node , tmp ) ; // ersetze node durch Nfolger
t.toTeX("\\texttt{L\\\"oschung} von "+node.key);
tmp . color = node . color ; // uebernimm die Farbe
t.toTeX("\\texttt{Umf\\\"arbe-Operation}");
} else { // ein Kind , oder kein Kind
Node child ; // Hilfsvariable
if ( node . left!= null ) child = node . left ; // Kind ist links
else if ( node . right!= null ) child = node . right ; // rechts
else child = null ; // kein Kind
rbtDelFix (t , node , child ) ;
t.toTeX("\\texttt{L\\\"oschung} von "+node.key+" mit "+
"anschlie\\ss{}ender \\texttt{Umf\\\"arbung}");
bstReplace (t , node , child ) ;
}
}
//VL 11 Folie 32
// node soll geloescht werden , child ist einziges Kind
// ( bzw . node hat keine Kinder , und child == null ) ;
// Ist node rot , so ist nichts zu tun ; sonst suchen wir
// einen roten Knoten , der durch Umfaerben auf schwarz
// die schwarze Farbe von node uebernimmt
static void rbtDelFix ( Tree t , Node node , Node child )
{
if ( node . color == RED ) return ;
if ( child != null && child . color == RED ) {
child . color = BLACK ;
} else {
Node searchPos = node ;
// solange Schwarzwert nicht eingefuegt werden kann
while ( searchPos . parent != null && searchPos . color == BLACK ) {
if ( searchPos == searchPos . parent . left ) // linkes Kind
searchPos = delLeftAdjust (t , searchPos ) ;
else // rechtes Kind
searchPos = delRightAdjust (t , searchPos ) ;
}
searchPos . color = BLACK ;
}
}
//VL 11 Folie 33
// Erleichtert node um einen Schwarzwert ,
// wobei node das linke Kind ist .
static Node delLeftAdjust ( Tree t , Node node )
{
// brother existiert immer wegen Schwarzhoehe
Node brother = node . parent . right ;
if ( brother . color == RED ) {
// Fall 1: Reduktion auf 2 ,3 ,4
brother . color = BLACK ;
node . parent . color = RED ; // Vater
leftRotate (t , node . parent ) ;
brother = node . parent . right ; // nun Bruder von node
}
if ( brother . left . color == BLACK &&
brother . right . color == BLACK ) { // Fall 2
brother . color = RED ;
return node . parent ; // Doppel - schwarz weiter oben ...
} else { // Fall 3 und 4
if ( brother . right . color == BLACK ) {// Fall 3
brother . left . color = BLACK ;
brother . color = RED ;
rightRotate (t , brother ) ;
brother = node . parent . right ; // nun Bruder von node
} // Fall 4
brother . color = node . parent . color ;
node . parent . color = BLACK ;
brother . right . color = BLACK ;
leftRotate (t , node . parent ) ;
return t . root ; // Fertig .
}
}
static Node delRightAdjust ( Tree t , Node node )
{
// brother existiert immer wegen Schwarzhoehe
Node brother = node . parent . left ;
if ( brother . color == RED ) {
// Fall 1: Reduktion auf 2 ,3 ,4
brother . color = BLACK ;
node . parent . color = RED ; // Vater
rightRotate (t , node . parent ) ;
brother = node . parent . left ; // nun Bruder von node
}
if ( brother . right . color == BLACK &&
brother . left . color == BLACK ) { // Fall 2
brother . color = RED ;
return node . parent ; // Doppel - schwarz weiter oben ...
} else { // Fall 3 und 4
if ( brother . left . color == BLACK ) {// Fall 3
brother . right . color = BLACK ;
brother . color = RED ;
leftRotate (t , brother ) ;
brother = node . parent . left ; // nun Bruder von node
} // Fall 4
brother . color = node . parent . color ;
node . parent . color = BLACK ;
brother . left . color = BLACK ;
rightRotate (t , node . parent ) ;
return t . root ; // Fertig .
}
}
//Eigene Methoden
static Node deepestUnbalancedNode(Tree t, Node a)
{
Node unbalancedLeft = deepestUnbalancedNode(t,a.left);
Node unbalancedRight = deepestUnbalancedNode(t,a.right);
if(unbalancedRight == null){
if(unbalancedLeft != null){
return unbalancedLeft;
}else{
if(Math.abs(height(a.left)-height(a.right))==2){
return a;
}else{
return null;
}
}
}else{
if(unbalancedLeft == null){
return unbalancedRight;
}else{
//Beides unbalanciert
if(height(unbalancedLeft)<=height(unbalancedRight)){
return unbalancedLeft;
}else{
return unbalancedRight;
}
}
}
}
static int height(Tree t){
return height(t.root);
}
static int height(Node a){
if(a==null){
return 0;
}
return Math.max(height(a.left),height(a.right))+1;
}
static boolean balanced(Tree t, Node a){
return deepestUnbalancedNode(t,a) == null;
}
String toTeX(){
return toTeX("");
}
String toTeX(String caption){
String TeX = "\\begin{figure}[H]\n"+
"\\centering\n"+
"\\begin{tikzpicture}\n"+
"[sibling distance = 3em,\n"+
" level distance = 3em,\n"+
" edge from parent/.style = {draw, -latex},\n"+
" every node/.style = {font=\\footnotesize},\n"+
" level 1/.style={sibling distance=8em},\n"+
" level 2/.style={sibling distance=4em},\n"+
" level 3/.style={sibling distance=2em},\n"+
" level 4/.style={sibling distance=1em},\n"+
" sloped\n"+
"]\n"+
"\\"+root.toTeX()+
";\n"+
"\\end{tikzpicture}\n"+
"\\caption{"+caption+"}\n"+
"\\end{figure}\n";
System.out.println(TeX);
return TeX;
}
}