[1716] in java-interest
Re: linked list w/o references or ptrs?
daemon@ATHENA.MIT.EDU (Chuck McManis)
Fri Sep 15 02:07:12 1995
Date: Thu, 14 Sep 1995 20:10:57 -0700
From: cmcmanis@scndprsn.Eng.Sun.COM (Chuck McManis)
To: fgreco@lehman.com, java-interest@java.Eng.Sun.COM
This is an example of implementing "Red-Black" trees from the Rivest
book on algorithms. It creates a balanced binary tree and supports
both adding and deleting nodes. It is a good example of a traditional
linked list. There are two files here, separated by dashed lines
RedBlackTree.java and Main.java, the latter is simply a simple
exerciser for the former to show how it works.
--Chuck
--------------------------- RedBlackTree.java
/*
* @(#)RedBlackTree.java 1.1 95/09/14
*
* Copyright (c) 1995 Sun Microsystems, Inc. All Rights Reserved.
*
* Permission to use, copy, modify, and distribute this software
* and its documentation for NON-COMMERCIAL purposes and without
* fee is hereby granted provided that this copyright notice
* appears in all copies. Please refer to the file "copyright.html"
* for further important copyright and licensing information.
*
* SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
* THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
* TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
* PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
* ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
* DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
*/
// package sun.misc;
import java.io.PrintStream;
import java.util.Dictionary;
import java.util.Enumeration;
import java.util.NoSuchElementException;
/**
* This class implements a Dictionary using a B-tree. This exact type
* of tree is called a "red-black" tree since it uses a color algorithim
* to insure that it is always balanced. Note that the key object must
* be an object of class String for this class. This is because the
* implementation uses compareTo() to determine if a node should be on
* the right or left hand branch.
*
* @author Chuck McManis
* @version 1.1, 14 Sep 1995
* @see Dictionary
*/
public class RedBlackTree {
private RedBlackTreeNode listRoot;
private final int RED = 0;
private final int BLACK = 1;
private int count = 0;
private long treeGen = 0; // This tree's generation count.
/**
* Returns the number of elements in the tree.
*/
public int size() {
return (count);
}
/**
* Returns true if the tree is empty.
*/
public boolean isEmpty() {
return (listRoot == null);
}
/**
* Return an enumeration of the trees keys. This will return the
* keys in sorted order as it does an inorder walk from the minimum
* valued key to the maximum valued key.
*/
public Enumeration keys() {
return new RedBlackTreeEnumerator(this, true);
}
/**
* Return an enumeration of the trees objects. This will return the
* elements in sorted order as it does an inorder walk from minimum
* key to the maximum key.
*/
public Enumeration elements() {
return new RedBlackTreeEnumerator(this, false);
}
/**
* Return the value for a given key.
*/
public Object get(Object key) {
if (key instanceof String) {
RedBlackTreeNode x = lookup((String) key);
return ((x != null) ? x.value : null);
}
return (null); // throw something?
}
/**
* Add a new object to the tree. Note that if there is already a
* node in the tree with this key value, the old value is replaced
* with the new value. The old value is returned. If no previous
* node exists, this returns null.
*/
public Object put(Object key, Object value) throws Exception {
if (key instanceof String) {
RedBlackTreeNode x = add((String) key, value);
if (x == null)
count++; // Added a new element
return ((x != null) ? x.value : null);
}
throw new Exception("Cannot add");
}
/**
* Remove an object from the tree. This returns null if the key did
* not reference an object in the tree.
*/
public Object remove(Object key) {
if (key instanceof String) {
RedBlackTreeNode x = lookup((String) key);
if (x != null) {
delete(x);
count--;
return (x.value);
}
}
return (null); // throw something?
}
/* ******************************************* *
* PRIVATE Implementation of Red-Black B-trees *
* ******************************************* */
/**
* Return the value of the generation variable
*/
long generation() {
return treeGen;
}
/**
* Rotate the tree left about node 'x'.
*/
private void rotateLeft(RedBlackTreeNode x) {
RedBlackTreeNode y = x.right;
x.right = y.left;
if (y.left != null)
y.left.parent = x;
y.parent = x.parent;
if (x.parent == null)
listRoot = y;
else {
if (x == x.parent.left)
x.parent.left = y;
else
x.parent.right = y;
}
y.left = x;
x.parent = y;
}
/**
* Return the color of node x, note if node x is null then
* the color is presumed to be black.
*/
private int color(RedBlackTreeNode x) {
if (x == null)
return BLACK;
else
return (x.color);
}
/**
* Rotate the tree right about the node y. Rotations preserve
* the key ordering of their children nodes.
*/
private void rotateRight(RedBlackTreeNode y) {
RedBlackTreeNode x = y.left;
y.left = x.right;
if (x.right != null)
x.right.parent = y;
x.parent = y.parent;
if (y.parent == null)
listRoot = x;
else {
if (y == y.parent.left)
y.parent.left = x;
else
y.parent.right = x;
}
x.right = y;
y.parent = x;
}
/**
* Simple node insertion. After insertion the red-black properties
* are "fixed" by rotating the correct number of nodes to balance
* the tree. See add below.
*/
private RedBlackTreeNode insert(RedBlackTreeNode z) {
RedBlackTreeNode x = listRoot;
RedBlackTreeNode y = null;
int i;
while (x != null) {
y = x;
x = (x.key.compareTo(z.key) > 0) ? x.left : x.right;
}
z.parent = y;
if (y == null) {
listRoot = z;
} else {
i = y.key.compareTo(z.key);
if (i > 0)
y.left = z;
else if (i < 0)
y.right = z;
else { // They have the same key
Object t;
t = z.value; // swap values
z.value = y.value;
y.value = t;
return (z); // return old value
}
}
return (null);
}
/**
* Return the lowest key valued node. (needed for enumerations)
*/
RedBlackTreeNode minimum() {
return minimum(listRoot);
}
/**
* Return the lowest key value in the subtree under x
*/
private RedBlackTreeNode minimum(RedBlackTreeNode x) {
if (x == null)
x = listRoot;
while (x != null) {
if (x.left == null)
return x;
x = x.left;
}
return null;
}
/**
* Return the highest value key under the subtree x
*/
private RedBlackTreeNode maximum(RedBlackTreeNode x) {
if (x == null)
x = listRoot;
while (x != null) {
if (x.right == null)
return x;
x = x.right;
}
return null;
}
/**
* Return the next higher key value following x.
*/
RedBlackTreeNode successor(RedBlackTreeNode x) {
if (x.right != null)
return (minimum(x.right));
RedBlackTreeNode y = x.parent;
while ((y != null) && (x == y.right)) {
x = y;
y = x.parent;
}
return y;
}
/**
* Return the next lower node to node x in key order
*/
private RedBlackTreeNode predecessor(RedBlackTreeNode x) {
if (x.left != null)
return (maximum(x.left));
RedBlackTreeNode y = x.parent;
while ((y != null) && (x == y.left)) {
x = y;
y = x.parent;
}
return y;
}
/**
* Add a new node to the B-tree. Do the insertion, followed by
* balancing. If the node is simply a replacement, skip the
* balancing section.
*/
private synchronized RedBlackTreeNode add(String key, Object datum) {
RedBlackTreeNode x = new RedBlackTreeNode(key, datum);
RedBlackTreeNode y;
RedBlackTreeNode oldValue = null;
oldValue = insert(x);
if (oldValue != null) {
return (oldValue);
}
treeGen++; // note that it is a new tree
x.color = RED;
/* now fix up the tree */
while ((x != listRoot) && (x.parent.color == RED)) {
if (x.parent == x.parent.parent.left) {
y = x.parent.parent.right;
if ((y != null) && (y.color == RED)) {
x.parent.color = BLACK;
y.color = BLACK;
x.parent.parent.color = RED;
x = x.parent.parent;
} else {
if (x == x.parent.right) {
x = x.parent;
rotateLeft(x);
}
x.parent.color = BLACK;
x.parent.parent.color = RED;
rotateRight(x.parent.parent);
}
} else {
y = x.parent.parent.left;
if ((y != null) && (y.color == RED)) {
x.parent.color = BLACK;
y.color = BLACK;
x.parent.parent.color = RED;
x = x.parent.parent;
} else {
if (x == x.parent.left) {
x = x.parent;
rotateRight(x);
}
x.parent.color = BLACK;
x.parent.parent.color = RED;
rotateLeft(x.parent.parent);
}
}
}
listRoot.color = BLACK;
return null;
}
/**
* Return the node indexed by key.
*/
private synchronized RedBlackTreeNode lookup(String key) {
RedBlackTreeNode x = listRoot;
int ci;
while (x != null) {
ci = x.key.compareTo(key);
if (ci < 0)
x = x.right;
else if (ci > 0)
x = x.left;
else
return x;
}
return (null);
}
/**
* return a string of length 'n' blanks (helper for printNode)
*/
private String blanks(int n) {
StringBuffer z = new StringBuffer(n);
for (int q = 0; q < n; q++)
z.append(" ");
return (z.toString());
}
/**
* Print a nice graphical representation of the tree on the
* PrintStream passed. See printTree for the output.
*/
private void printNode(RedBlackTreeNode x, String indent, PrintStream out) {
if (x == null)
return;
if (x.right != null) {
if ((x.parent != null) && (x == x.parent.left))
printNode(x.right, indent+"|"+blanks(x.key.length()+2), out);
else
printNode(x.right, indent+blanks(x.key.length()+3), out);
}
out.print(indent);
out.print((x.color == BLACK) ? "@ " : "O ");
out.print(x.key);
if ((x.right != null) || (x.left != null))
out.println(" +");
else
out.println();
if (x.left == null) {
if (x.parent != null) {
if (x == x.parent.right)
indent = indent + "|";
else
indent = indent + " ";
}
out.println(indent);
} else {
if ((x.parent != null) && (x == x.parent.right))
indent = indent + "|" + blanks(x.key.length()+2);
else
indent = indent + " " + blanks(x.key.length()+2);
out.println(indent+"|");
printNode(x.left, indent, out);
}
}
/**
* Print a graphical version of the tree (ignores the 80 column limit)
* on terminals. This function walks the tree and outputs a graphical
* form with the keys in place. The format is as follows:
* <pre>
* O fraz
* |
* @ foo +
* |
* @ bletch +
* |
* | O baz
* | |
* @ bar +
*</pre>
* Each node is represented by '@' if it is black, and 'O' if it is
* red, followed by its key, and its children. Nodes to the right in
* output are lower in the tree than nodes to the left, the root node
* is in column 1. Nodes lower on the output are to the "left" of
* nodes earlier or higher in the output. (rotate 90 degrees clockwise)
*/
public void printTree(PrintStream o) {
printNode(listRoot, "", o);
}
/**
* Print the tree to System.out
*/
public void printTree() {
printNode(listRoot, "", System.out);
}
/**
* Fix up the coloring of the tree after a remove operation.
*/
private void delete_fixup(RedBlackTreeNode x) {
RedBlackTreeNode w;
if (x.parent == null) // deleted last node in tree
return;
while ((x != listRoot) && (x.color == BLACK)) {
if (((x == nilNode) && (x.parent.left == null)) ||
(x == x.parent.left)) {
w = x.parent.right;
if (color(w) == RED) {
w.color = BLACK;
w.parent.color = RED;
rotateLeft(x.parent);
w = x.parent.right;
}
if ((color(w.left) == BLACK) && (color(w.right) == BLACK)) {
w.color = RED;
x = x.parent;
} else {
if (color(w.right) == BLACK) {
w.left.color = BLACK;
w.color = RED;
rotateRight(w);
w = x.parent.right;
}
w.color = x.parent.color;
x.parent.color = BLACK;
w.right.color = BLACK;
rotateLeft(x.parent);
x = listRoot;
}
} else {
w = x.parent.left;
if (color(w) == RED) {
w.color = BLACK;
w.parent.color = RED;
rotateRight(x.parent);
w = x.parent.left;
}
if ((color(w.left) == BLACK) && (color(w.right) == BLACK)) {
w.color = RED;
x = x.parent;
} else {
if (color(w.left) == BLACK) {
w.right.color = BLACK;
w.color = RED;
rotateLeft(w);
w = x.parent.left;
}
w.color = x.parent.color;
x.parent.color = BLACK;
w.left.color = BLACK;
rotateRight(x.parent);
x = listRoot;
}
}
}
x.color = BLACK;
}
// makes the delete algorithm cleaner
private RedBlackTreeNode nilNode = new RedBlackTreeNode("Nil", "Nil");
/**
* Remove a node from the tree and if it is black, fix up the
* tree so that the black height remains balanced.
*/
private synchronized RedBlackTreeNode delete(RedBlackTreeNode z) {
RedBlackTreeNode x = null, y = null;
nilNode.color = BLACK;
treeGen++; // tree has changed, flag enumerators
if ((z.left == null) || (z.right == null))
y = z; // Z has only one child
else
y = successor(z);
if (y.left != null)
x = y.left;
else
x = (y.right == null) ? nilNode : y.right;
x.parent = y.parent;
if (y.parent == null)
listRoot = (x == nilNode) ? null : x;
else {
if (y == y.parent.left)
y.parent.left = (x == nilNode) ? null : x;
else
y.parent.right = (x == nilNode) ? null : x;
}
if (y != z) {
z.key = y.key;
z.value = y.value;
}
if (y.color == BLACK)
delete_fixup(x);
return (y);
}
public String toString() {
return ("RedBlackTree object with "+count+" elements.");
}
}
/**
* This class defines an individual node on the B-tree itself. It is
* private to btrees and has no methods.
*/
class RedBlackTreeNode {
int color;
Object value;
String key;
RedBlackTreeNode right, left, parent;
public RedBlackTreeNode(String nodeKey, Object nodeValue) {
super();
key = nodeKey;
value = nodeValue;
}
public String toString() {
return ("K("+((color == 0)?"R":"B")+"):"+key);
}
}
/**
* This is the enumerator class. It implements the enumeration interface
* and is very straightforward.
*
* Note that there is a race condition whereby an enumerator becomes
* "invalid" should the tree be changed while it is held.
*/
class RedBlackTreeEnumerator implements Enumeration {
// state for the enumerator
private boolean keys;
private RedBlackTree tree;
private RedBlackTreeNode x;
private long generation;
/**
* Create a new enumerator.
*/
RedBlackTreeEnumerator(RedBlackTree tree, boolean keys) {
this.tree = tree;
this.keys = keys;
this.x = tree.minimum();
this.generation = tree.generation();
}
/**
* Returns true if there is another element in the list.
*/
public boolean hasMoreElements() {
return (x != null);
}
/**
* Returns the next element.
* @exception NoSuchElementException thrown if it is out of elements.
* @exception Exception thrown if the tree has been modified.
*/
public Object nextElement() {
RedBlackTreeNode y = x;
if (x == null)
throw new NoSuchElementException("RedBlackTreeEnumerator");
if (generation != tree.generation())
throw new NoSuchElementException(
"RedBlackTreeEnumerator: Tree modified during enumeration");
x = tree.successor(x);
return ((keys) ? y.key : y.value);
}
}
--------------------------- Main.java
/*
* @(#)Main.java 1.1 95/09/14
*
* Copyright (c) 1995 Sun Microsystems, Inc. All Rights Reserved.
*
* Permission to use, copy, modify, and distribute this software
* and its documentation for NON-COMMERCIAL purposes and without
* fee is hereby granted provided that this copyright notice
* appears in all copies. Please refer to the file "copyright.html"
* for further important copyright and licensing information.
*
* SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
* THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
* TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
* PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
* ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
* DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
*/
import java.util.Enumeration;
/**
* This class exercises a red-black tree.
*
* @author Chuck McManis
* @version 1.1, 14 Sep 1995
*/
public class Main {
static String unsortedList[] = {
"Red",
"Blue",
"Violet",
"Magenta",
"Cyan",
"Grey",
"Purple",
"Chartruese",
"Pink",
"Orange",
"Yellow",
"White",
"Green",
"Mauve",
"Periwinkle",
"Maroon",
"Gold",
"Silver",
"Bronze",
"Black" };
static void remove(String name, RedBlackTree tree) {
System.out.println("Remove : "+ name);
tree.remove(name);
tree.printTree();
System.out.println("=======================");
}
public static void main(String args[]) {
RedBlackTree tree = new RedBlackTree();
for (int i = 0; i < unsortedList.length; i++) {
tree.put(unsortedList[i], unsortedList[i]);
}
System.out.println("Final tree: ");
tree.printTree();
System.out.println("=========================");
System.out.println("Enumerated list:");
int q = 1;
for (Enumeration e = tree.keys(); e.hasMoreElements(); q++)
System.out.println("["+ q +"] - "+e.nextElement());
System.out.println("-------------------------");
System.out.println("Removing nodes from the tree:.\n");
Main.remove("Cyan", tree);
Main.remove("Black", tree);
Main.remove("Blue", tree);
Main.remove("Gold", tree);
Main.remove("Green", tree);
Main.remove("Chartruese", tree);
}
}
--------------------------- end
-
Note to Sun employees: this is an EXTERNAL mailing list!
Info: send 'help' to java-interest-request@java.sun.com
