Class Index | File Index

Classes


Class R.struct.RedBlackTree


Extends R.engine.PooledObject.
An implementation of a RedBlackTree data structure. RedBlackTree has a worst-case time of O(log n) which is fast enough to quickly locate objects in the tree. Duplicates are not allowed in a RedBlackTree.

Items added to a RedBlackTree must implement a compareTo(t) method which returns a Number. Zero if the value of the item is equal to "t", -1 if the value is less than t, 1 if the value is greater than "t".

References: http://www.java-tips.org/java-se-tips/java.lang/red-black-tree-implementation-in-java.html
http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx
Defined in: redblacktree.js.

Class Summary
Constructor Attributes Constructor Name and Description
 
Create a red-black tree object.
Method Summary
Method Attributes Method Name and Description
 
find(x)
Find an item in the tree.
 
Find the largest item in the tree.
 
Find the smallest item the tree.
 
Find the node containing an item in the tree.
 
insert(item)
Insert into the tree.
 
Test if the tree is logically empty.
 
Make the tree logically empty.
 
replace(oldItem, newItem)
Replace the the item in the tree with the new item.
 
Rotate binary tree node with left child.
 
Rotate binary tree node with right child.
Methods borrowed from class R.engine.PooledObject:
clearObjectDataModel, destroy, getId, getName, getObjectDataModel, getProperties, isDestroyed, release, setName, setObjectDataModel, toString, toXML
Class Detail
R.struct.RedBlackTree(name)
Create a red-black tree object.
Parameters:
name
{String} The name of the container. Default: RBTree
Method Detail
{Object} find(x)
Find an item in the tree. The item "x" must implement the compareTo(t)method.
Parameters:
x
{Object} the item to search for.
Returns:
{Object} the matching item or null if not found.

findMax()
Find the largest item in the tree.
Returns:
the largest item or null if empty.

findMin()
Find the smallest item the tree.
Returns:
the smallest item or null if empty.

{RedBlackNode} findNode(x)
Find the node containing an item in the tree. The item "x" must implement the compareTo(t)method.
Parameters:
x
{Object} the item to search for.
Returns:
{RedBlackNode} the matching node or null if not found.

insert(item)
Insert into the tree. item must implement the compareTo(t) method, otherwise insertion will fail with an assertion.
Parameters:
item
{Object} the item to insert.

isEmpty()
Test if the tree is logically empty.
Returns:
true if empty, false otherwise.

makeEmpty()
Make the tree logically empty.

replace(oldItem, newItem)
Replace the the item in the tree with the new item.
Parameters:
oldItem
{Object} The object to find
newItem
{Object} The object to replace it with

rotateWithLeftChild(k2)
Rotate binary tree node with left child.
Parameters:
k2

rotateWithRightChild(k1)
Rotate binary tree node with right child.
Parameters:
k1

Documentation generated by JsDoc Toolkit 2.4.0 on Mon Mar 18 2013 16:09:21 GMT-0400 (EDT)