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.
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.htmlhttp://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx
Defined in: redblacktree.js.
Constructor Attributes | Constructor Name and Description |
---|---|
R.struct.RedBlackTree(name)
Create a red-black tree object.
|
Method Attributes | Method Name and Description |
---|---|
find(x)
Find an item in the tree.
|
|
findMax()
Find the largest item in the tree.
|
|
findMin()
Find the smallest item the tree.
|
|
findNode(x)
Find the node containing an item in the tree.
|
|
insert(item)
Insert into the tree.
|
|
isEmpty()
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