RedBlack

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

struct RedBlack (

V

A = AttributeDummy

) {

import ocean.core.Verify;;

alias Type = RedBlack!(V, A);

alias Ref = Type*;

anonymousenum RED;

static if(!is(typeof(A) == AttributeDummy))

static if(!is(typeof(A) == AttributeDummy))

Ref set(V v, A a);

Ref set(V v);

Ref dup(Ref delegate() alloc);

void checkImplementation();

Ref leftmost();

Ref rightmost();

bool isRoot();

Ref successor();

Ref predecessor();

Ref find(V value, Compare!(V) cmp);

Ref findFirst(V value, Compare!(V) cmp, bool after);

int count(V value, Compare!(V) cmp);

static if(!is(typeof(A) == AttributeDummy))

Ref findAttribute(A attribute, Compare!(A) cmp);

static if(!is(typeof(A) == AttributeDummy))

int countAttribute(A attrib, Compare!(A) cmp);

static if(!is(typeof(A) == AttributeDummy))

Ref find(V value, A attribute, Compare!(V) cmp);

Ref copyTree(Ref delegate() alloc);

Ref insertLeft(Ref cell, Ref root);

Ref insertRight(Ref cell, Ref root);

Ref remove(Ref root);

static Ref swapPosition(Ref x, Ref y, Ref root);

static bool colorOf(Ref p);

static Ref parentOf(Ref p);

static void setColor(Ref p, bool c);

static Ref leftOf(Ref p);

static Ref rightOf(Ref p);

Ref rotateLeft(Ref root);

Ref rotateRight(Ref root);

Ref fixAfterInsertion(Ref root);

Ref fixAfterDeletion(Ref root);

}

Members

Aliases

Ref alias Ref = Type*: Undocumented in source.
Type alias Type = RedBlack!(V, A): Undocumented in source.

Enums

RED anonymousenum RED: Undocumented in source.

Functions

checkImplementation void checkImplementation(): * See_Also: ocean.util.collection.model.View.View.checkImplementation.
copyTree Ref copyTree(Ref delegate() alloc): * Return a new subtree containing each value of current subtree
count int count(V value, Compare!(V) cmp): * Return number of nodes of current subtree containing value. * Uses Comparator cmp to find and to check equality.
countAttribute int countAttribute(A attrib, Compare!(A) cmp): Undocumented in source. Be warned that the author may not have intended to support it.
dup Ref dup(Ref delegate() alloc): * 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.)
find Ref find(V value, Compare!(V) cmp): * Return node of current subtree containing value as value(), * if it exists, else null. * Uses Comparator cmp to find and to check equality.
find Ref find(V value, A attribute, Compare!(V) cmp): * find and return a cell holding (key, element), or null if no such
findAttribute Ref findAttribute(A attribute, Compare!(A) cmp): Undocumented in source. Be warned that the author may not have intended to support it.
findFirst Ref findFirst(V value, Compare!(V) cmp, bool after): * 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.
fixAfterDeletion Ref fixAfterDeletion(Ref root): From CLR *
fixAfterInsertion Ref fixAfterInsertion(Ref root): From CLR *
insertLeft Ref insertLeft(Ref cell, Ref root): * 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!)
insertRight Ref insertRight(Ref cell, Ref 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!)
isRoot bool isRoot(): * Return true if node is a root (i.e., has a null parent)
leftmost Ref leftmost(): * Return the minimum value of the current (sub)tree
predecessor Ref predecessor(): * Return the inorder predecessor, or null if no such
remove Ref remove(Ref root): * 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!)
rightmost Ref rightmost(): * Return the maximum value of the current (sub)tree
root Ref root(): * Return the root (parentless node) of the tree
rotateLeft Ref rotateLeft(Ref root): From CLR *
rotateRight Ref rotateRight(Ref root): From CLR *
set Ref set(V v, A a): Undocumented in source. Be warned that the author may not have intended to support it.
set Ref set(V v): * Make a new Cell with given value, null links, and BLACK color. * Normally only called to establish a new root.
size int size(): * Return the number of nodes in the subtree
successor Ref successor(): * Return the inorder successor, or null if no such

Static functions

colorOf bool colorOf(Ref p): * 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.) *
leftOf Ref leftOf(Ref p): * return left child of node p, or null if p is null
parentOf Ref parentOf(Ref p): * return parent of node p, or null if p is null
rightOf Ref rightOf(Ref p): * return right child of node p, or null if p is null
setColor void setColor(Ref p, bool c): * Set the color of node p, or do nothing if p is null
swapPosition Ref swapPosition(Ref x, Ref y, Ref root): * Swap the linkages of two nodes in a tree. * Return new root, in case it changed.

Variables

attribute A attribute;: Undocumented in source.
color bool color;: * The node color (RED, BLACK)
left Ref left;: * Pointer to left child
parent Ref parent;: * Pointer to parent (null if root)
right Ref right;: * Pointer to right child
value V value;: Undocumented in source.

Meta

Source

See Implementation