12-05-2011, 12:54 PM
SUBMITTED BY
CHANDRASHEKHAR RAI
GAURAV KUMAR GOYAL
MOHAMMAD FAISAL
RAJESH SINGH
[attachment=13654]
INTRODUCTION
Red-black trees-
A red-black tree is a binary search tree + 1 bit per node: an attribute color, which
is either red or black.
All leaves are empty (nil) and colored black.
• We use a single sentinel, nil[T ], for all the leaves of red-black tree T .
• color[nil[T ]] is black.
• The root.s parent is also nil[T ].
All other attributes of binary search trees are inherited by red-black trees (key, left,
right, and p). We don.t care about the key in nil[T ].
Red-black properties-
1. Every node is either red or black.
2. The root is black.
3. Every leaf (nil[T ]) is black.
4. If a node is red, then both its children are black. (Hence no two reds in a row
on a simple path from the root to a leaf.)
5. For each node, all paths from the node to descendant leaves contain the samenumber of black nodes.
HARDWARE REQUREMENT-
Processor Pentium III with 733 MHz
Random Access Memory 256 MB
Hard Disk 10GB
Screen Resolution 800 by 600
Color Quality 16 bit
SOFTWARE REQUREMENT-
OS ALL VERSION OF WINDOWS
Front End JAVA
LANGUAGE USED –JAVA
Code:
CODING-
import java.io.*;
import java.util.*;
import java.awt.*;
import java.awt.event.*;
/* <applet code=RedBlackTree.java width=1024 height=600>
</applet>*/
class Node
{
int level; // root level = 0, next level = 1, etc. used only by new node
int indent; // leftmost node in a level = 0, 1 is next right node, etc. used only by new node
Node parent;
Node leftTree;
Node rightTree;
int value;
Color color;
public Node(int v, Color clr)
{
level = 0;
indent = 0;
parent = null;
value = v;
color = clr;
leftTree = null;
rightTree = null;
}
int getValue() { return value; }
Node getParent() { return parent; }
Node getRightTree() { return rightTree; }
Node getLeftTree() { return leftTree; }
int getLevel() { return level; }
int getIndent() { return indent; }
Color getColor() { return color; }
void setValue(int v) { value = v; }
void setParent(Node p) { parent = p; }
void setLeftTree(Node lt) { leftTree = lt; }
void setRightTree(Node rt) { rightTree = rt; }
void setLevel(int lv) { level = lv; }
void setIndent(int in) { indent = in; }
void setColor(Color c) { color = c; }
boolean isRightChild() {
return (this == parent.getRightTree());
}
boolean isLeftChild() {
return (this == parent.getLeftTree());
}
}
class TreePanel extends Panel
{
RedBlackTree graph;
Node pick;
Node deletingNode;
Color deletingSaveColor;
boolean deleteNode = false, removingNode = false;
TreePanel(RedBlackTree graph) { this.graph = graph; }
Image offscreen;
Dimension offscreensize;
Graphics offScreen;
int offset = 28;
public void paint(Graphics g) {
update(g);
}
public void update(Graphics g)
{
Dimension d = getSize();
if ((offscreen == null) || (d.width != offscreensize.width) ||
(d.height != offscreensize.height))
{
offscreen = createImage(d.width, d.height);
offscreensize = d;
offScreen = offscreen.getGraphics();
offScreen.setFont(getFont());
}