structure5
Class RedBlackSearchTree<E extends java.lang.Comparable<E>>

java.lang.Object
  structure5.AbstractStructure<E>
      structure5.RedBlackSearchTree<E>

All Implemented Interfaces:

java.lang.Iterable<E>, OrderedStructure<E>, Structure<E>

public class RedBlackSearchTree<E extends java.lang.Comparable<E>>
extends AbstractStructure<E>
implements OrderedStructure<E>

Red black trees, are binary trees that guarantee the following three properties.
1. Every child of every leaf is considered black
2. Every red node has two black children
3. Every path from a node to a descendant leaf contains the same number of black nodes.

These properties ensure that elements can be inserted, deleted, and located in logorithmic time.

Example usage:

To create a red-black tree containing the months of the year and to print out this tree as it grows we could use the following

 public static void main(String[] argv){
     RedBlackSearchTree test = new RedBlackSearchTree();
       
     //declare an array of months
     String[] months = new String[]{"March", "May", "November", "August", 
                                    "April", "January", "December", "July",
                                    "February", "June", "October", "September"};
      
     //add the months to the tree and print out the tree as it grows
     for(int i=0; i < months.length; i++){
        test.add(months[i]);
        System.out.println("Adding: " + months[i] + "\n" +test.treeString());
      }
  }
 

See Also:

AVLTree, SplayTree, BinaryTree

Field Summary

protected int	count The number of nodes in the tree
protected RedBlackTree<E>	root A reference to the root of the tree

Constructor Summary

RedBlackSearchTree()
Constructs a red-black search tree with no data

Method Summary

void	add(E value) Add a (possibly duplicate) value to the red-black tree, and ensure that the resulting tree is a red-black tree.
void	clear() Removes all data from the binary search tree
boolean	contains(E value) Determines if the red-black search tree contains a value
int	hashCode() Returns the hashCode of the value stored by this object.
boolean	isEmpty() Checks for an empty binary search tree
boolean	isRedBlack() Returns true iff this tree is a red-black tree.
java.util.Iterator<E>	iterator() Returns an iterator over the red-black search tree.
E	remove(E value) Remove an value "equals to" the indicated value.
int	size() Determines the number of data values within the tree
java.lang.String	toString() Returns a string representing tree
java.lang.String	treeString() Returns a (possibly long) string representing tree.

Methods inherited from class structure5.AbstractStructure

elements, values

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface structure5.Structure

elements, values

Field Detail

root

protected RedBlackTree<E extends java.lang.Comparable<E>> root

A reference to the root of the tree

count

protected int count

The number of nodes in the tree

Constructor Detail

RedBlackSearchTree

public RedBlackSearchTree()

Constructs a red-black search tree with no data

Postcondition:

Constructs an empty red-black tree

Method Detail

isEmpty

public boolean isEmpty()

Checks for an empty binary search tree

Specified by:

isEmpty in interface Structure<E extends java.lang.Comparable<E>>

Overrides:

isEmpty in class AbstractStructure<E extends java.lang.Comparable<E>>

Returns:

True iff the tree contains no data

Postcondition:

Returns true iff the binary search tree is empty

clear

public void clear()

Removes all data from the binary search tree

Specified by:

clear in interface Structure<E extends java.lang.Comparable<E>>

Postcondition:

Removes all elements from binary search tree

size

public int size()

Determines the number of data values within the tree

Specified by:

size in interface Structure<E extends java.lang.Comparable<E>>

Returns:

The number of nodes in the binary search tree

Postcondition:

Returns the number of elements in binary search tree

add

public void add(E value)

Add a (possibly duplicate) value to the red-black tree, and ensure that the resulting tree is a red-black tree.

Specified by:

add in interface Structure<E extends java.lang.Comparable<E>>

Parameters:

val - A reference to non-null object

Postcondition:

Adds a value to binary search tree

remove

public E remove(E value)

Remove an value "equals to" the indicated value. Only one value is removed, and no guarantee is made concerning which of duplicate values are removed. Value returned is no longer part of the structure

Specified by:

remove in interface Structure<E extends java.lang.Comparable<E>>

Parameters:

val - Value sought to be removed from tree

Returns:

Value to be removed from tree or null if no value removed

Postcondition:

Removes one instance of val, if found

contains

public boolean contains(E value)

Determines if the red-black search tree contains a value

Specified by:

contains in interface Structure<E extends java.lang.Comparable<E>>

Overrides:

contains in class AbstractStructure<E extends java.lang.Comparable<E>>

Parameters:

val - The value sought. Should be non-null

Returns:

True iff the tree contains a value "equals to" sought value

Postcondition:

Returns true iff val is a value found within the tree

isRedBlack

public boolean isRedBlack()

Returns true iff this tree is a red-black tree. WARNING: This method executes in linear time and should not be frequently called during the process of insertion and deletion if the user wants

Returns:

True iff this tree is a red-black tree.

iterator

public java.util.Iterator<E> iterator()

Returns an iterator over the red-black search tree. Iterator should not be used if tree is modified, as behavior may be unpredicatable Traverses elements using in-order traversal order

Specified by:

iterator in interface java.lang.Iterable<E extends java.lang.Comparable<E>>

Specified by:

iterator in interface Structure<E extends java.lang.Comparable<E>>

Returns:

An iterator over red-black search tree

See Also:

AbstractIterator, Iterator, Enumeration, Structure.elements()

Postcondition:

Returns iterator to traverse red-blackST

treeString

public java.lang.String treeString()

Returns a (possibly long) string representing tree. Differs from toString() in that toString() outputs a single line representation of the contents of the tree. treeString, however, prints out a graphical representations of the tree's structure.

Returns:

String representation of tree

Postcondition:

Generates a string representation of the AVLST

toString

public java.lang.String toString()

Returns a string representing tree

Overrides:

toString in class java.lang.Object

Returns:

String representation of tree

Postcondition:

Generates a string representation of the AVLST

hashCode

public int hashCode()

Returns the hashCode of the value stored by this object.

Overrides:

hashCode in class AbstractStructure<E extends java.lang.Comparable<E>>

Returns:

The hashCode of the value stored by this object.