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:
- Each node is either red or black
- Each leaf is black
- Each red node has only black sons
- 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 |
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 |
RED
public static final byte RED
- Constant for red nodes.
BLACK
public static final byte BLACK
- Constant for black nodes.
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 keysleft_is_smaller
- if true
, smaller keys are stored in the left
partial tree, otherwise in the right
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 permissionargument
- the argument of the requested action- Returns:
true
, if the Owner
allows the requested action, false
otherwise