Home Manual Reference Source

References

api

summary
public	V empty: * Same as RedBlackTree.empty.

color

summary
public	V BLACK: number Constant for black.
public	V RED: number Constant for red.

debug

summary
private	F _debug(colors: Object): Function Builds a debug function from color handlers.

deletion

summary
public	F delete_case0(n: Node): Node Preconditions: n is black all root-leaf paths going through n have a black height of b - 1 all other root-leaf paths have a black height of b
public	F delete_case1(n: Node): Node Preconditions: n is black all root-leaf paths going through n have a black height of b - 1 all other root-leaf paths have a black height of b n is not the root
public	F delete_case2(n: Node): Node Preconditions: n is black all root-leaf paths going through n have a black height of b - 1 all other root-leaf paths have a black height of b n is not the root n's sibling is black
public	F delete_case5(n: Node): Node Preconditions: n is black all root-leaf paths going through n have a black height of b - 1 all other root-leaf paths have a black height of b n is not the root n's sibling is black if n is a left child, the right child of n's sibling is red if n is a right child, the left child of n's sibling is red
public	F delete_no_child(n: Node): Node Delete a node `n` that has no non-leaf child.
public	F delete_one_child(n: Node) Delete a node `n` with one non-leaf left child and one leaf right child.
public	F prune(root: Node) Prune subtree rooted at input node.
public	F replace_node(A: Node, B: Node) Replaces node `A` by node `B`.

family

summary
public	F grandparent(node: Node): Node Computes the grandparent (parent of parent) of the input node.
public	F predecessor(node: Node): Node Computes the predecessor of the input node, in the subtree rooted at the input node, when this predecessor is guaranteed to exist.
public	F sibling(node: Node): Node Computes the sibling of the input node.
public	F uncle(node: Node): Node Computes the uncle of the input node when the grandparent is guaranteed to exist.

insertion

summary
public	F insert(compare: Function, A: Node, B: Node): Node Walks the tree rooted at `A` down the only path that satisfies the following property: if at a node `C` we make a left (resp.
public	F insert_case0(n: Node): Node Preconditions: n is red.
public	F insert_case1(n: Node): Node Preconditions: n is red.
public	F insert_case2(n: Node): Node Preconditions: n is red.
public	F insert_case3(n: Node): Node Preconditions: n is red.
public	F insert_case4(n: Node): Node Preconditions: n is red.

rotate

summary
public	F rotate_left(A: Node) Rotate tree left.
public	F rotate_right(B: Node) Rotate tree right.

search

summary
public	F search(compare: Function, root: Node, key: any): Node Search for the first node whose key equals `key`.

swap

summary
public	F swap_color(A: Node, B: Node) Swap colors of two arbitrary nodes.
public	F swap_left(A: Node): Node Swap pointers and colors of a node and its left child B with one constraint: B's right child is a leaf NOTE: This constraint is implied because B is A's in-subtree predecessor.
public	F swap_non_adjacent(A: Node, B: Node) Swap pointers and colors of two NON-ADJACENT nodes with three constraints: B is not the root B is its parent right child B's right child is a leaf NOTE: These three constraints are implied because B is A's in-subtree predecessor without being A's left child. `p q q p \| \ \ \| -A +B +A -B / \ / \ / \ / \ u v x - -> x - u v`

traversal

summary
public	F * inordertraversal(node: Node): IterableIterator Traverses the tree rooted at `node` in order.
public	F * leftOpenRangeTraversal(compare: Function, root: Node, right: any): IterableIterator Yields all the keys in the tree rooted at `root` that lie in the interval `(-oo, right[`, in order.
public	F * rangetraversal(compare: Function, root: Node, left: any, right: any): IterableIterator Yields all the keys in the tree rooted at `root` that lie in the interval `[left, right[`, in order.
public	F * rightOpenRangeTraversal(compare: Function, root: Node, left: any): IterableIterator Yields all the keys in the tree rooted at `root` that lie in the interval `[left, +oo)`, in order.

types

summary
public	C RedBlackTree A RedBlackTree with key-only nodes.
public	F Node(color: number, key: any) An internal node.

Directories