gishur.core
Class RedBlackTree

java.lang.Object
  |
  +--gishur.core.BasicTree
        |
        +--gishur.core.BinarySearchTree
              |
              +--gishur.core.RedBlackTree
All Implemented Interfaces:
java.lang.Cloneable, Cloneable, ControlledCloneable, Owner, java.io.Serializable

public class RedBlackTree
extends BinarySearchTree

A red-black-tree, i.e. a completely balanced BinarySearchTree tree with those features:

  1. Each node is either red or black
  2. Each leaf is black
  3. Each red node has only black sons
  4. Each descending path from a node to any leaf contains the same number of black nodes.
To ensure the completeness of the tree, the null-pointers at the former leafs must now supposed to be leafs (but BasicTreeItem.isLeaf() still returns true for nodes with a null-pointer). After this definition, it is possible that a leaf (of the old definition) may be red. The height of a RedBlackTree is maximally 1*log(length()+1). That means that search, insertion and deletion take O(log(length()))-time.

Version:
1.0
Author:
Thomas Wolf
See Also:
Serialized Form

Field Summary
static byte BLACK
          Constant for black nodes.
static byte RED
          Constant for red nodes.
 
Fields inherited from class gishur.core.BasicTree
_access, ANY_ACCESS, CHILDS_ROOT_ORDER, KEY, LEFT_RIGHT_ROOT_ORDER, LEFT_ROOT_RIGHT_ORDER, NO_ACCESS, ROOT_CHILDS_ORDER, ROOT_LEFT_RIGHT_ORDER, TREEITEM, VALUE
 
Fields inherited from interface gishur.core.ControlledCloneable
DEEP, FLAT
 
Constructor Summary
RedBlackTree()
          Empty constructor.
RedBlackTree(Comparitor comparitor)
          Standard constructor receiving a Comparitor-object to perform the comparisons between the tree's elements and defining an order for the tree.
RedBlackTree(Comparitor comparitor, boolean left_is_smaller)
          Constructs a binary tree using the specified Comparitor and following the definition if smaller elements shall be stored in the left or in the right partial tree.
 
Method Summary
protected  TreeItem add_item(TreeItem item)
          Finally inserts the TreeItem item into the tree.
 int blackHeight()
          Returns the black-height of the whole tree.
 int blackHeight(TreeItem root)
          Returns the so-called black-height of the partial tree starting with root.
 TreeItem remove(TreeItem item)
          Removes item from the tree and returns it (or null, if the deletion was not successful).
 boolean requestAccess(int accesstype, java.lang.Object who, java.lang.Object argument)
          The owned object who asks its Owner for permission to perform an action specified by accesstype with argument argument.
 
Methods inherited from class gishur.core.BinarySearchTree
add, add, add, add, add, add, add, add, afterAdd, afterRemove, allowDuplicates, beforeAdd, beforeRemove, clear, clone, clone, comparitor, contains, double_rotation, empty, find, find, findBigger, findBigger, findPath, findSmaller, findSmaller, first, first, height, height, keys, keys, last, last, leftIsSmaller, length, length, max, max, min, min, next, next, onDoubleRotation, onLeftRotate, onRightRotate, prev, prev, remove, root, rotation, setAllowDuplicates, treeItems, values, values
 
Methods inherited from class gishur.core.BasicTree
add, add, allowAccess, connect, copy, countItems, cutTree, emptyEnumeration, enumerate, enumerate, find, findLast, first, fitInPlace, getListItemChain, getRemovableTreeItem, getTreeString, last, next, ownTree, ownTree, prev, removeSym, removeTree, storeInArray, toString
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

RED

public static final byte RED
Constant for red nodes.

BLACK

public static final byte BLACK
Constant for black nodes.
Constructor Detail

RedBlackTree

public RedBlackTree()
Empty constructor. To compare the tree's elements, their keys' hash codes are evaluated.

RedBlackTree

public RedBlackTree(Comparitor comparitor)
Standard constructor receiving a Comparitor-object to perform the comparisons between the tree's elements and defining an order for the tree.
Parameters:
comparitor - a Comparitor to order the tree

RedBlackTree

public RedBlackTree(Comparitor comparitor,
                    boolean left_is_smaller)
Constructs a binary tree using the specified Comparitor and following the definition if smaller elements shall be stored in the left or in the right partial tree.
Parameters:
comparitor - a Comparitor-object to compare keys
left_is_smaller - if true, smaller keys are stored in the left partial tree, otherwise in the right
Method Detail

blackHeight

public int blackHeight(TreeItem root)
Returns the so-called black-height of the partial tree starting with root. The black-heigth is the number of black nodes of one (and therefore all) paths from root to a leaf of the tree (not including the root itself). As the real leafs of a RedBlackTree are the null-pointers at the last nodes in the tree (and these leafs are black by definition, see above), the returned black-height is one bigger than the real black-height. That means that for root==null zero is returned and for a root with root.child()==null one is returned. If root is not part of this tree, a negative value will be returned.
Parameters:
root - the root-node of the partial tree to examine
Returns:
the black-height of the specified partial tree

blackHeight

public int blackHeight()
Returns the black-height of the whole tree.
Returns:
the black-height of this tree
See Also:
blackHeight(TreeItem)

add_item

protected TreeItem add_item(TreeItem item)
Finally inserts the TreeItem item into the tree. This method is used by all add-methods and thus ensures that the tree is rebalanced after the insertion.
Overrides:
add_item in class BinarySearchTree
Parameters:
item - new TreeItem
Returns:
inserted TreeItem

remove

public TreeItem remove(TreeItem item)
Removes item from the tree and returns it (or null, if the deletion was not successful). After the deletion, the tree is rebalanced and and recoloured to keep it a RedBlackTree.
Overrides:
remove in class BinarySearchTree
Parameters:
{@link - TreeItem} to be removed from the tree
Returns:
removed TreeItem

requestAccess

public boolean requestAccess(int accesstype,
                             java.lang.Object who,
                             java.lang.Object argument)
The owned object who asks its Owner for permission to perform an action specified by accesstype with argument argument. This method overrides BasicTree.requestAccess() to make it more restrictive (BasicTree#key and BasicTree#maxRank must stay unchanged).
Overrides:
requestAccess in class BinarySearchTree
Parameters:
accesstype - type of requested action (i.e. the access needed for this action)
who - object asking for permission
argument - the argument of the requested action
Returns:
true, if the Owner allows the requested action, false otherwise