Red/Black Trees (animation)
import java.io.*;
import java.util.*;
import java.awt.*;
class Dot
{
int level; // 0 is top, 1 is next, etc.
int indent; // 0 is leftmost, 1 is next, etc.
int left; // pixels in from left
int top; // pixels in from top
Dot leftTree;
Dot rightTree;
int number;
Dot shadow;
Color color;
public Dot(int n, Color clr)
{
number = n;
color = clr;
leftTree = null;
rightTree = null;
shadow = null;
}
int numberOf() { return number; }
int setLeft(int lf) { return left = lf; }
int setTop(int tp) { return top = tp; }
void setLevel(int lv) { level = lv; }
void setIndent(int in) { indent = in; }
void setShadow(Dot d) { shadow = d; }
void setLefttree (Dot lt)
{
leftTree = lt;
lt.setIndent(2*indent);
lt.setLevel(level+1);
}
void setLeftTree (Dot lt) { leftTree = lt; }
void setRightTree (Dot rt) { rightTree = rt; }
void setRighttree(Dot rt)
{
rightTree = rt;
rt.setIndent(2*indent+1);
rt.setLevel(level+1);
}
void setColor(Color c) { color = c; }
Dot shadowOf() { return shadow; }
Dot rightTreeOf() { return rightTree; }
Dot leftTreeOf() { return leftTree; }
int leftOf() { return left; }
int topOf() { return top; }
int levelOf() { return level; }
int indentOf() { return indent; }
Color colorOf() { return color; }
}
class DotPanel extends Panel implements Runnable
{
RB graph;
Thread relaxer;
Dot pick;
DotPanel(RB graph) { this.graph = graph; }
public void run()
{
while (true)
{
repaint();
try
{
Thread.sleep(85 + graph.getNDots()/2);
}
catch (InterruptedException e) { break; }
}
}
Image offscreen;
Dimension offscreensize;
Graphics offgraphics;
int left(Dot dot)
{
Dimension d = size();
double wid = (double)d.width/(1+(1 << dot.levelOf()));
return (int)(wid*(dot.indentOf()+1)) + 15;
}
int top(Dot dot) { return 20+dot.levelOf()*50 + 15; }
int offset = 28;
public void paintDot(Graphics g, Dot dot, FontMetrics fm, int ox, int oy)
{
int x = left(dot);
int y = top(dot);
int tx = dot.leftOf();
int ty = dot.topOf();
String lbl = String.valueOf(dot.numberOf());
int w = fm.stringWidth(lbl);
int h = fm.getHeight();
g.setColor(dot.colorOf());
g.fillOval(tx+ox-offset, ty+oy, 30, 30);
g.setColor(Color.white);
g.drawString(lbl, tx+ox-offset-w/2+15, ty+oy+12+h/2);
dot.setLeft((dot.leftOf()+x)/2);
dot.setTop((dot.topOf()+y)/2);
}
public void paintPickedDot(Graphics g, Dot dot, FontMetrics fm)
{
int tx = dot.leftOf();
int ty = dot.topOf();
String lbl = String.valueOf(dot.numberOf());
int w = fm.stringWidth(lbl);
int h = fm.getHeight();
g.setColor(dot.colorOf());
g.fillOval(tx-offset, ty, 30, 30);
g.setColor(Color.white);
g.drawString(lbl, tx-offset-w/2+15, ty+12+h/2);
}
public void paintEdgesOfDot(Graphics g, Dot dot)
{
g.setColor(Color.black);
int x = dot.leftOf()+15;
int y = dot.topOf()+15;
if (dot.leftTreeOf() != null)
{
int lx = dot.leftTreeOf().leftOf()+15;
int ly = dot.leftTreeOf().topOf()+15;
g.drawLine(x-offset,y,lx-offset,ly);
}
if (dot.rightTreeOf() != null)
{
int rx = dot.rightTreeOf().leftOf()+15;
int ry = dot.rightTreeOf().topOf()+15;
g.drawLine(x-offset,y,rx-offset,ry);
}
}
public void update(Graphics g)
{
Dimension d = size();
if ((offscreen == null) || (d.width != offscreensize.width) ||
(d.height != offscreensize.height))
{
offscreen = createImage(d.width, d.height);
offscreensize = d;
offgraphics = offscreen.getGraphics();
offgraphics.setFont(getFont());
}
offgraphics.setColor(graph.getColor());
offgraphics.fillRect(0, 0, d.width, d.height);
FontMetrics fm = offgraphics.getFontMetrics();
Dot dt[] = graph.getDots();
int nd = graph.getNDots();
for (int i=0 ; i < nd ; i++)
paintEdgesOfDot(offgraphics, dt[i]);
for (int i=0 ; i < nd ; i++)
if (dt[i] != pick) paintDot(offgraphics, dt[i], fm, 0, 0);
else paintPickedDot(offgraphics, dt[i], fm);
if (graph.getNewest() != null)
paintDot(offgraphics, graph.getNewest(), fm, -30, -15);
g.drawImage(offscreen, 0, 0, null);
}
public boolean mouseDown(Event evt, int x, int y)
{
Dot dot[] = graph.getDots();
for (int i=0 ; i < graph.getNDots() ; i++)
{
if (x-dot[i].leftOf() < 0 && y-dot[i].topOf() < 30 &&
x > dot[i].leftOf()-30 && y > dot[i].topOf())
{
pick = dot[i];
return true;
}
}
return true;
}
public boolean mouseDrag(Event evt, int x, int y)
{
if (pick != null)
{
pick.setLeft(x+20);
pick.setTop(y-10);
}
return true;
}
public boolean mouseUp(Event evt, int x, int y)
{
pick = null;
return true;
}
public void start() { relaxer = new Thread(this); relaxer.start(); }
public void stop() { relaxer.stop(); }
}
public class RB extends java.applet.Applet
{
DotPanel panel;
Dot shadow;
int sysLock = 0;
Dot cdot[] = new Dot[100];
int cndots = 0;
Dot dot[] = new Dot[100];
int ndots = 0;
Dot ss[] = new Dot[100];
Dot rev1 = null, rev2 = null, rev3 = null;
int ssindex = 0;
Dot head = null;
Dot chead = null;
Dot temp = null;
Dot newest = null;
Dot stopdot = new Dot(0, Color.black);
Button addbutton, nextbutton, undobutton, startbutton, tempbutton;
TextField val;
Panel p;
Color bgcolor = new Color(190,190,190);
Dot[] getDots() { return dot; }
int getNDots() { return ndots; }
Dot getNewest() { return newest; }
Color getColor()
{
if (rev1 == null && rev2 == null && rev3 == null &&
temp == null && !(head == null && newest != null) &&
ssindex == 0 && (head != null && head.colorOf() == Color.black))
{
bgcolor = new Color(190,190,190);
}
return bgcolor;
}
public void init()
{
setLayout(new BorderLayout());
panel = new DotPanel(this);
add("Center", panel);
p = new Panel();
add("South", p);
p.add(startbutton = new Button("Restart"));
p.add(undobutton = new Button("Undo"));
p.add(val = new TextField(5));
p.add(addbutton = new Button("Add Node"));
p.add(nextbutton = new Button("Next Step"));
p.add(new Button("Delete Node (future)"));
}
public void start() { panel.start(); }
public void stop() { panel.stop(); }
Dot copyTree(Dot root)
{
if (root == null) return null;
Dot dot = new Dot(root.numberOf(), root.colorOf());
dot.setTop(root.topOf());
dot.setLeft(root.leftOf());
dot.setLevel(root.levelOf());
dot.setIndent(root.indentOf());
dot.setLeftTree(copyTree(root.leftTreeOf()));
dot.setRightTree(copyTree(root.rightTreeOf()));
root.setShadow(dot);
return dot;
}
int insertCopy(Dot root, Dot p[], int ss)
{
if (root == null) return ss;
p[ss++] = root;
ss = insertCopy(root.leftTreeOf(), p, ss);
ss = insertCopy(root.rightTreeOf(), p, ss);
return ss;
}
void reLevel(Dot dot, int ind, int lvl)
{
if (dot == null) return;
dot.setLevel(lvl);
dot.setIndent(ind);
reLevel(dot.leftTreeOf(), 2*ind, lvl+1);
reLevel(dot.rightTreeOf(), 2*ind+1 , lvl+1);
}
void leftRotate(Dot chld, Dot prnt)
{
prnt.setLeftTree(chld.rightTreeOf());
chld.setRightTree(prnt.leftTreeOf().leftTreeOf());
prnt.leftTreeOf().setLeftTree(chld);
reLevel(head, 0, 0);
}
void srightRotate(Dot chld, Dot prnt)
{
prnt.setRightTree(chld.leftTreeOf());
chld.setLeftTree(prnt.rightTreeOf().rightTreeOf());
prnt.rightTreeOf().setRightTree(chld);
reLevel(head, 0, 0);
}
void rightRotate(Dot chld, Dot prnt)
{
prnt.setLeftTree(chld.leftTreeOf());
chld.setLeftTree(prnt.leftTreeOf().rightTreeOf());
prnt.leftTreeOf().setRightTree(chld);
reLevel(head, 0, 0);
}
void sleftRotate(Dot chld, Dot prnt)
{
prnt.setRightTree(chld.rightTreeOf());
chld.setRightTree(prnt.rightTreeOf().leftTreeOf());
prnt.rightTreeOf().setLeftTree(chld);
reLevel(head, 0, 0);
}
void rightRotate(Dot dot)
{
head = dot.leftTreeOf();
dot.setLeftTree(head.rightTreeOf());
head.setRightTree(dot);
reLevel(head, 0, 0);
}
void sleftRotate(Dot dot)
{
head = dot.rightTreeOf();
dot.setRightTree(head.leftTreeOf());
head.setLeftTree(dot);
reLevel(head, 0, 0);
}
int upward()
{
if (ssindex > 0)
{
if (ss[ssindex-1].colorOf() == Color.red &&
ss[ssindex].colorOf() == Color.red)
{
if (ssindex > 1 && ss[ssindex] == ss[ssindex-1].leftTreeOf() &&
ss[ssindex-1] == ss[ssindex-2].leftTreeOf())
{
if (ss[ssindex-2].rightTreeOf() == null ||
ss[ssindex-2].rightTreeOf().colorOf() == Color.black)
{
if (ssindex > 2)
{
if (ss[ssindex-3].leftTreeOf() == ss[ssindex-2])
rightRotate(ss[ssindex-2], ss[ssindex-3]);
else
srightRotate(ss[ssindex-2], ss[ssindex-3]);
play(getCodeBase(), "audio/ah.au");
rev1 = ss[ssindex-1];
rev2 = ss[ssindex-2];
ss[ssindex-2] = ss[ssindex-1];
ssindex -= 2;
return 1;
}
else
{
rightRotate(ss[ssindex-2]);
play(getCodeBase(), "audio/ooh.au");
rev1 = head;
rev2 = head.rightTreeOf();
ssindex = 0;
return 1;
}
}
else
{
rev1 = ss[ssindex-2];
rev2 = ss[ssindex-2].leftTreeOf();
rev3 = ss[ssindex-2].rightTreeOf();
ssindex -= 2;
return 2;
}
}
else
if (ssindex > 1 && ss[ssindex] == ss[ssindex-1].rightTreeOf() &&
ss[ssindex-1] == ss[ssindex-2].leftTreeOf())
{
if (ss[ssindex-2].rightTreeOf() == null ||
ss[ssindex-2].rightTreeOf().colorOf() == Color.black)
{
leftRotate(ss[ssindex-1], ss[ssindex-2]);
play(getCodeBase(), "audio/ah.au");
Dot tt = ss[ssindex];
ss[ssindex] = ss[ssindex-1];
ss[ssindex-1] = tt;
return 1;
}
else
{
rev1 = ss[ssindex-2];
rev2 = ss[ssindex-2].leftTreeOf();
rev3 = ss[ssindex-2].rightTreeOf();
ssindex -= 2;
return 2;
}
}
else
if (ssindex > 1 && ss[ssindex] == ss[ssindex-1].rightTreeOf() &&
ss[ssindex-1] == ss[ssindex-2].rightTreeOf())
{
if (ss[ssindex-2].leftTreeOf() == null ||
ss[ssindex-2].leftTreeOf().colorOf() == Color.black)
{
if (ssindex > 2)
{
if (ss[ssindex-3].rightTreeOf() == ss[ssindex-2])
sleftRotate(ss[ssindex-2], ss[ssindex-3]);
else
leftRotate(ss[ssindex-2], ss[ssindex-3]);
play(getCodeBase(), "audio/ooh.au");
rev1 = ss[ssindex-1];
rev2 = ss[ssindex-2];
ss[ssindex-2] = ss[ssindex-1];
ssindex -= 2;
return 1;
}
else
{
sleftRotate(ss[ssindex-2]);
play(getCodeBase(), "audio/ooh.au");
rev1 = head;
rev2 = head.leftTreeOf();
ssindex = 0;
return 1;
}
}
else
{
rev1 = ss[ssindex-2];
rev2 = ss[ssindex-2].leftTreeOf();
rev3 = ss[ssindex-2].rightTreeOf();
ssindex -= 2;
return 2;
}
}
else
if (ssindex > 1 && ss[ssindex] == ss[ssindex-1].leftTreeOf() &&
ss[ssindex-1] == ss[ssindex-2].rightTreeOf())
{
if (ss[ssindex-2].leftTreeOf() == null ||
ss[ssindex-2].leftTreeOf().colorOf() == Color.black)
{
srightRotate(ss[ssindex-1], ss[ssindex-2]);
play(getCodeBase(), "audio/ah.au");
Dot tt = ss[ssindex];
ss[ssindex] = ss[ssindex-1];
ss[ssindex-1] = tt;
return 1;
}
else
{
rev1 = ss[ssindex-2];
rev2 = ss[ssindex-2].leftTreeOf();
rev3 = ss[ssindex-2].rightTreeOf();
ssindex -= 2;
return 2;
}
}
}
else
{
return 0;
}
}
return 0;
}
Dot insertDot(Dot dot, Dot root)
{
if (root == null) return null;
if (dot.numberOf() == root.numberOf())
{
play(getCodeBase(), "audio/drip.au");
return newest = null;
}
else
if (dot.numberOf() < root.numberOf())
{
dot.setLevel(root.levelOf()+1);
dot.setIndent(2*root.indentOf());
if (root.leftTreeOf() == null)
{
stopdot.setColor(Color.green);
return stopdot;
}
return root.leftTreeOf();
}
else
{
dot.setLevel(root.levelOf()+1);
dot.setIndent(2*root.indentOf()+1);
if (root.rightTreeOf() == null)
{
stopdot.setColor(Color.yellow);
return stopdot;
}
return root.rightTreeOf();
}
}
Dot reverseColor(Dot dot)
{
if (dot.colorOf() == Color.black) dot.setColor(Color.red);
else
if (dot.colorOf() == Color.red) dot.setColor(Color.black);
return null;
}
public boolean action(Event evt, Object arg)
{
if (evt.target.equals(startbutton))
{
ndots = cndots = ssindex = 0;
head = chead = rev1 = rev2 = rev3 = newest = temp = null;
for (int i=0 ; i < 100 ; i++) { dot[i] = cdot[i] = ss[i] = null; }
bgcolor = new Color(190, 190, 190);
return super.action(evt, arg);
}
else
if (evt.target.equals(undobutton))
{
if (chead == null) return super.action(evt, arg);
for (int i=0 ; i < ndots ; i++)
{
if ((shadow = dot[i].shadowOf()) != null)
{
shadow.setLeft(dot[i].leftOf());
shadow.setTop(dot[i].topOf());
}
}
for (int i=0 ; i < cndots ; i++) { dot[i] = cdot[i]; ss[i] = null; }
ndots = cndots;
head = chead;
chead = null;
rev1 = rev2 = rev3 = newest = temp = null;
ssindex = 0;
return super.action(evt, arg);
}
else
if (evt.target.equals(addbutton))
{
if (rev1 != null || rev2 != null || rev3 != null ||
temp != null || (head == null && newest != null) ||
ssindex != 0 || (head != null && head.colorOf() != Color.black))
{
play(getCodeBase(), "audio/ooh.au");
}
else
if (newest == null)
{
cndots = insertCopy(chead = copyTree(head), cdot, 0);
ssindex = 0;
int num = Integer.parseInt(val.getText());
newest = new Dot(num, Color.red);
newest.setLevel(0);
newest.setIndent(0);
temp = head;
bgcolor = new Color(0,190,190);
}
return super.action(evt, arg);
}
else
if (evt.target.equals(nextbutton))
{
if (rev1 != null || rev2 != null || rev3 != null)
{
if (rev1 != null) rev1 = reverseColor(rev1);
if (rev2 != null) rev2 = reverseColor(rev2);
if (rev3 != null) rev3 = reverseColor(rev3);
}
else
if (temp != null) // Insert the dot (way down)
{
ss[ssindex++] = temp;
if ((temp = insertDot(newest, temp)) == stopdot)
{
if (stopdot.colorOf()==Color.green)
ss[ssindex-1].setLefttree(newest);
else
ss[ssindex-1].setRighttree(newest);
dot[ndots++] = ss[ssindex] = newest;
newest = temp = null;
play(getCodeBase(), "audio/ooh.au");
}
}
else
if (head == null && newest != null) // Special case - first dot
{
dot[ndots++] = ss[ssindex] = head = newest;
newest.setColor(Color.black);
newest = temp = null;
play(getCodeBase(), "audio/whoopy.au");
}
else
if (ssindex > 0)
{
int tell;
if ((tell = upward()) == 2)
{
if (rev1 != null) rev1 = reverseColor(rev1);
if (rev2 != null) rev2 = reverseColor(rev2);
if (rev3 != null) rev3 = reverseColor(rev3);
}
else
if (tell == 0 && rev1 == null && rev2 == null && rev3 == null)
{
play(getCodeBase(), "audio/train.au");
ssindex = 0;
}
}
else
if (head.colorOf() != Color.black)
head.setColor(Color.black);
if (rev1 == null && rev2 == null && rev3 == null &&
temp == null && !(head == null && newest != null) &&
ssindex == 0 && (head != null && head.colorOf() == Color.black))
{
play(getCodeBase(), "audio/train.au");
bgcolor = new Color(190,190,190);
}
}
return super.action(evt, arg);
}
}