* See_Also: tango.util.collection.model.View.View.checkImplementation.
* Return a new subtree containing each value of current subtree
* Return number of nodes of current subtree containing value. * Uses Comparator cmp to find and to check equality.
* Return a new Ref with same value and color as self, * but with null links. (Since it is never OK to have * multiple identical links in a RB tree.)
* Return node of current subtree containing value as value(), * if it exists, else null. * Uses Comparator cmp to find and to check equality.
* find and return a cell holding (key, element), or null if no such
* Return node of subtree matching "value" * or, if none found, the one just after or before * if it doesn't exist, return null * Uses Comparator cmp to find and to check equality.
From CLR *
From CLR *
* There's no generic value insertion. Instead find the * place you want to add a node and then invoke insertLeft * or insertRight. * <P> * Insert Cell as the left child of current node, and then * rebalance the tree it is in. * @param Cell the Cell to add * @param root, the root of the current tree * Returns: the new root of the current tree. (Rebalancing * can change the root!)
* Insert Cell as the right child of current node, and then * rebalance the tree it is in. * @param Cell the Cell to add * @param root, the root of the current tree * Returns: the new root of the current tree. (Rebalancing * can change the root!)
* Return true if node is a root (i.e., has a null parent)
* Return the minimum value of the current (sub)tree
* Return the inorder predecessor, or null if no such
* Delete the current node, and then rebalance the tree it is in * @param root the root of the current tree * Returns: the new root of the current tree. (Rebalancing * can change the root!)
* Return the maximum value of the current (sub)tree
* Return the root (parentless node) of the tree
From CLR *
From CLR *
* Make a new Cell with given value, null links, and BLACK color. * Normally only called to establish a new root.
* Return the inorder successor, or null if no such
* Return the number of nodes in the subtree
* Return color of node p, or BLACK if p is null * (In the CLR version, they use * a special dummy `nil' node for such purposes, but that doesn't * work well here, since it could lead to creating one such special * node per real node.) *
* return left child of node p, or null if p is null
* return parent of node p, or null if p is null
* return right child of node p, or null if p is null
* Set the color of node p, or do nothing if p is null
* Swap the linkages of two nodes in a tree. * Return new root, in case it changed.
RedBlack implements basic capabilities of Red-Black trees, an efficient kind of balanced binary tree. The particular algorithms used are adaptations of those in Corman, Lieserson, and Rivest's <EM>Introduction to Algorithms</EM>. This class was inspired by (and code cross-checked with) a similar class by Chuck McManis. The implementations of rebalancings during insertion and deletion are a little trickier than those versions since they don't swap Cell contents or use special dummy nilnodes.
Doug Lea