Function

Static Public Summary
public	Node(color: number, key: any) An internal node.
public	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	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	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	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	delete_no_child(n: Node): Node Delete a node `n` that has no non-leaf child.
public	delete_one_child(n: Node) Delete a node `n` with one non-leaf left child and one leaf right child.
public	grandparent(node: Node): Node Computes the grandparent (parent of parent) of the input node.
public	* inordertraversal(node: Node): IterableIterator Traverses the tree rooted at `node` in order.
public	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	insert_case0(n: Node): Node Preconditions: n is red.
public	insert_case1(n: Node): Node Preconditions: n is red.
public	insert_case2(n: Node): Node Preconditions: n is red.
public	insert_case3(n: Node): Node Preconditions: n is red.
public	insert_case4(n: Node): Node Preconditions: n is red.
public	* 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	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	prune(root: Node) Prune subtree rooted at input node.
public	* 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	replace_node(A: Node, B: Node) Replaces node `A` by node `B`.
public	* 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.
public	rotate_left(A: Node) Rotate tree left.
public	rotate_right(B: Node) Rotate tree right.
public	search(compare: Function, root: Node, key: any): Node Search for the first node whose key equals `key`.
public	sibling(node: Node): Node Computes the sibling of the input node.
public	swap_color(A: Node, B: Node) Swap colors of two arbitrary nodes.
public	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	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`
public	uncle(node: Node): Node Computes the uncle of the input node when the grandparent is guaranteed to exist.

Static Private Summary
private	_debug(colors: Object): Function Builds a debug function from color handlers.

Static Public

public Node(color: number, key: any) source

import Node from '@binary-search-tree/red-black-tree/src/types/Node.js'

An internal node. This node can be red or black.

Params:

Name	Type	Attribute	Description
color	number		The color of the node.
key	any		The key of the node.

public delete_case0(n: Node): Node source

import delete_case0 from '@binary-search-tree/red-black-tree/src/deletion/delete_case0.js'

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

Params:

Name	Type	Attribute	Description
n	Node		The input node.

Return:

Node	The root of the modified subtree.

public delete_case1(n: Node): Node source

import delete_case1 from '@binary-search-tree/red-black-tree/src/deletion/delete_case1.js'

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

Params:

Name	Type	Attribute	Description
n	Node		The input node.

Return:

Node	The root of the modified subtree.

public delete_case2(n: Node): Node source

import delete_case2 from '@binary-search-tree/red-black-tree/src/deletion/delete_case2.js'

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

Params:

Name	Type	Attribute	Description
n	Node		The input node.

Return:

Node	The root of the modified subtree.

public delete_case5(n: Node): Node source

import delete_case5 from '@binary-search-tree/red-black-tree/src/deletion/delete_case5.js'

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

Params:

Name	Type	Attribute	Description
n	Node		The input node.

Return:

Node	The root of the modified subtree.

public delete_no_child(n: Node): Node source

import delete_no_child from '@binary-search-tree/red-black-tree/src/deletion/delete_no_child.js'

Delete a node n that has no non-leaf child.

Precondition:

n has no non-leaf child.
n is not the root

Params:

Name	Type	Attribute	Description
n	Node		The node to delete.

Return:

Node	The root of the modified subtree.

public delete_one_child(n: Node) source

import delete_one_child from '@binary-search-tree/red-black-tree/src/deletion/delete_one_child.js'

Delete a node n with one non-leaf left child and one leaf right child.

  p
  |
  n (BLACK)
 / \

RED - / \

Precondition:

n has exactly one non-leaf child.
n is not the root
n's only non-leaf child is n's left child.
hence, n's right child is a leaf
hence, n's left child is RED
hence, n is BLACK

Params:

Name	Type	Attribute	Description
n	Node		The node to delete.

public grandparent(node: Node): Node source

import grandparent from '@binary-search-tree/red-black-tree/src/family/grandparent.js'

Computes the grandparent (parent of parent) of the input node.

Params:

Name	Type	Attribute	Description
node	Node		The input node.

Return:

Node

public * inordertraversal(node: Node): IterableIterator source

import inordertraversal from '@binary-search-tree/red-black-tree/src/traversal/inordertraversal.js'

Traverses the tree rooted at node in order.

Params:

Name	Type	Attribute	Description
node	Node		The root of the tree.

Return:

IterableIterator

public insert(compare: Function, A: Node, B: Node): Node source

import insert from '@binary-search-tree/red-black-tree/src/insertion/insert.js'

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. right), then B < C (resp. B >= C). Once we hit the end of the path, we can add node B at this position. By the property of the path, the tree rooted at A is still a binary search tree. For our red-black tree, all that is left to do is fix the red-black tree properties in case they have been violated by this insertion. This is fixed by insert_case0.

Params:

Name	Type	Attribute	Description
compare	Function		The comparison function to use.
A	Node		The root of the tree.
B	Node		The node to insert.

Return:

Node	B - The node that has been inserted.

public insert_case0(n: Node): Node source

import insert_case0 from '@binary-search-tree/red-black-tree/src/insertion/insert_case0.js'

Preconditions:

n is red.
n's children are BLACK

Params:

Name	Type	Attribute	Description
n	Node		The input node.

Return:

Node	The root of the modified subtree.

public insert_case1(n: Node): Node source

import insert_case1 from '@binary-search-tree/red-black-tree/src/insertion/insert_case1.js'

Preconditions:

n is red.
n's children are BLACK
n is not the root of the tree.

Params:

Name	Type	Attribute	Description
n	Node		The input node.

Return:

Node	The root of the modified subtree.

public insert_case2(n: Node): Node source

import insert_case2 from '@binary-search-tree/red-black-tree/src/insertion/insert_case2.js'

Preconditions:

n is red.
n's children are BLACK
n is not the root of the tree.
n's parent is red.

Params:

Name	Type	Attribute	Description
n	Node		The input node.

Return:

Node	The root of the modified subtree.

public insert_case3(n: Node): Node source

import insert_case3 from '@binary-search-tree/red-black-tree/src/insertion/insert_case3.js'

Preconditions:

n is red.
n's children are BLACK
n is not the root of the tree.
n's parent is red.
n's uncle is black.

Here we fix the input subtree to pass the preconditions of insert_case4.

Params:

Name	Type	Attribute	Description
n	Node		The input node.

Return:

Node	The root of the modified subtree.

public insert_case4(n: Node): Node source

import insert_case4 from '@binary-search-tree/red-black-tree/src/insertion/insert_case4.js'

Preconditions:

n is red.
n's children are BLACK
n is not the root of the tree.
n's parent is red.
n's uncle is black.
the path from n to its grandparent makes a left-left or right-right.

Params:

Name	Type	Attribute	Description
n	Node		The input node.

Return:

Node	The root of the modified subtree.

public * leftOpenRangeTraversal(compare: Function, root: Node, right: any): IterableIterator source

import leftOpenRangeTraversal from '@binary-search-tree/red-black-tree/src/traversal/leftOpenRangeTraversal.js'

Yields all the keys in the tree rooted at root that lie in the interval (-oo, right[, in order.

Params:

Name	Type	Attribute	Description
compare	Function		The comparison function.
root	Node		The root of the tree.
right	any		The non-inclusive upper bound of the interval.

Return:

IterableIterator

public predecessor(node: Node): Node source

import predecessor from '@binary-search-tree/red-black-tree/src/family/predecessor.js'

Computes the predecessor of the input node, in the subtree rooted at the input node, when this predecessor is guaranteed to exist.

Params:

Name	Type	Attribute	Description
node	Node		The input node.

Return:

Node

public prune(root: Node) source

import prune from '@binary-search-tree/red-black-tree/src/deletion/prune.js'

Prune subtree rooted at input node.

Params:

Name	Type	Attribute	Description
root	Node		The root of the subtree to prune.

public * rangetraversal(compare: Function, root: Node, left: any, right: any): IterableIterator source

import rangetraversal from '@binary-search-tree/red-black-tree/src/traversal/rangetraversal.js'

Yields all the keys in the tree rooted at root that lie in the interval [left, right[, in order.

Params:

Name	Type	Attribute	Description
compare	Function		The comparison function.
root	Node		The root of the tree.
left	any		The inclusive lower bound of the interval.
right	any		The non-inclusive upper bound of the interval.

Return:

IterableIterator

public replace_node(A: Node, B: Node) source

import replace_node from '@binary-search-tree/red-black-tree/src/deletion/replace_node.js'

Replaces node A by node B.

Params:

Name	Type	Attribute	Description
A	Node		The node to replace.
B	Node		The replacement node.

public * rightOpenRangeTraversal(compare: Function, root: Node, left: any): IterableIterator source

import rightOpenRangeTraversal from '@binary-search-tree/red-black-tree/src/traversal/rightOpenRangeTraversal.js'

Yields all the keys in the tree rooted at root that lie in the interval [left, +oo), in order.

Params:

Name	Type	Attribute	Description
compare	Function		The comparison function.
root	Node		The root of the tree.
left	any		The inclusive lower bound of the interval.

Return:

IterableIterator

public rotate_left(A: Node) source

import rotate_left from '@binary-search-tree/red-black-tree/src/rotate/rotate_left.js'

Rotate tree left. (see https://en.wikipedia.org/wiki/Tree_rotation)

    p                p
    |                |
    A                B
   / \              / \
  x   B     ->     A   y
     / \          / \
    b   y        x   b

Params:

Name	Type	Attribute	Description
A	Node		The root of the tree.

public rotate_right(B: Node) source

import rotate_right from '@binary-search-tree/red-black-tree/src/rotate/rotate_right.js'

Rotate tree right. (see https://en.wikipedia.org/wiki/Tree_rotation)

    p                p
    |                |
    B                A
   / \              / \
  A   y     ->     x   B
 / \                  / \
x   b                b   j

Params:

Name	Type	Attribute	Description
B	Node		The root of the tree.

public search(compare: Function, root: Node, key: any): Node source

import search from '@binary-search-tree/red-black-tree/src/search/search.js'

Search for the first node whose key equals key.

Params:

Name	Type	Attribute	Description
compare	Function		The comparison function.
root	Node		The root of the tree to scan.
key	any		The key to search for.

Return:

Node

public sibling(node: Node): Node source

import sibling from '@binary-search-tree/red-black-tree/src/family/sibling.js'

Computes the sibling of the input node.

Params:

Name	Type	Attribute	Description
node	Node		The input node.

Return:

Node

public swap_color(A: Node, B: Node) source

import swap_color from '@binary-search-tree/red-black-tree/src/swap/swap_color.js'

Swap colors of two arbitrary nodes.

   -A        +B      ->      +A        -B

Params:

Name	Type	Attribute	Description
A	Node		The first node.
B	Node		The second node.

public swap_left(A: Node): Node source

import swap_left from '@binary-search-tree/red-black-tree/src/swap/swap_left.js'

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.

    p                   p
    |                   |
   -A                  -B
   / \                 / \
 +B   c       ->     +A   c
 / \                 / \
a   -               a   -

Params:

Name	Type	Attribute	Description
A	Node		The node.

Return:

Node	The node B.

public swap_non_adjacent(A: Node, B: Node) source

import swap_non_adjacent from '@binary-search-tree/red-black-tree/src/swap/swap_non_adjacent.js'

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

Params:

Name	Type	Attribute	Description
A	Node		The first node.
B	Node		The second node.

public uncle(node: Node): Node source

import uncle from '@binary-search-tree/red-black-tree/src/family/uncle.js'

Computes the uncle of the input node when the grandparent is guaranteed to exist.

Params:

Name	Type	Attribute	Description
node	Node		The input node.

Return:

Node

Static Private

private _debug(colors: Object): Function source

import _debug from '@binary-search-tree/red-black-tree/src/debug/_debug.js'

Builds a debug function from color handlers.

Params:

Name	Type	Attribute	Description
colors	Object		The colors to use.

Return:

Function

The debug function.