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

public class | source

RedBlackTree

A RedBlackTree with key-only nodes.

Static Method Summary

Static Public Methods
public static	empty(compare: Function): RedBlackTree Constructs an empty red-black tree.
public static	from(compare: Function, iterable: Iterable): RedBlackTree Constructs a red-black tree from an input iterable.

Constructor Summary

Public Constructor
public	constructor(compare: Function) Constructs a new empty red-black tree.

Member Summary

Public Members
public	compare: *
public	root: *

Method Summary

Public Methods
public	[Symbol.iterator](): * Same as RedBlackTree#items.
public	add(key: any): Node Adds a key to the tree.
public	get(key: any): any Search for the input key in the tree.
public	has(key: any): boolean Returns `true` if and only if the tree contains the input key.
public	isEmpty(): boolean Tells whether the tree is empty.
public	* items(): IterableIterator Returns an in order iterator over the keys of the tree.
public	* range(left: any, right: any): IterableIterator Returns an in order iterator over the keys of the tree that lie in the interval [left, right[.
public	remove(key: any): boolean Search for the first node of the tree whose key equals the input key (with RedBlackTree#_search), then delete that node (with RedBlackTree#unlink).
public	unlink(node: Node) Deletes the input node from the tree.

Private Methods
private	_search(key: any): Node Search for the input key in the tree.

Static Public Methods

public static empty(compare: Function): RedBlackTree source

Constructs an empty red-black tree.

Params:

Name	Type	Attribute	Description
compare	Function		The comparison function to use.

Return:

RedBlackTree

public static from(compare: Function, iterable: Iterable): RedBlackTree source

Constructs a red-black tree from an input iterable.

Params:

Name	Type	Attribute	Description
compare	Function		The comparison function to use.
iterable	Iterable		The input iterable.

Return:

RedBlackTree

Public Constructors

public constructor(compare: Function) source

Constructs a new empty red-black tree.

Params:

Name	Type	Attribute	Description
compare	Function		The comparison function for node keys.

Public Members

public compare: * source

public root: * source

Public Methods

public [Symbol.iterator](): * source

Same as RedBlackTree#items.

Return:

public add(key: any): Node source

Adds a key to the tree.

Params:

Name	Type	Attribute	Description
key	any		The key to add.

Return:

Node	The newly added node.

public get(key: any): any source

Search for the input key in the tree. Returns the first node key found in this way (with RedBlackTree#_search. If no such key exists in the tree, returns null.

Params:

Name	Type	Attribute	Description
key	any		The input key.

Return:

any

public has(key: any): boolean source

Returns true if and only if the tree contains the input key.

Params:

Name	Type	Attribute	Description
key	any		The input key.

Return:

boolean

public isEmpty(): boolean source

Tells whether the tree is empty.

Return:

boolean

true if empty, false otherwise.

public * items(): IterableIterator source

Returns an in order iterator over the keys of the tree.

Return:

IterableIterator

public * range(left: any, right: any): IterableIterator source

Returns an in order iterator over the keys of the tree that lie in the interval [left, right[.

Params:

Name	Type	Attribute	Description
left	any		The left bound of the interval.
right	any		The right bound of the interval.

Return:

IterableIterator

public remove(key: any): boolean source

Search for the first node of the tree whose key equals the input key (with RedBlackTree#_search), then delete that node (with RedBlackTree#unlink). If such a node is found and deleted then return true. Return false otherwise.

Params:

Name	Type	Attribute	Description
key	any		The input key.

Return:

boolean

Whether the key existed in the tree before removal.

public unlink(node: Node) source

Deletes the input node from the tree.

Params:

Name	Type	Attribute	Description
node	Node		The input node to delete.

Private Methods

private _search(key: any): Node source

Search for the input key in the tree. Returns the first node whose key equals the input key. If no such node exists, returns null.

Params:

Name	Type	Attribute	Description
key	any		The input key.

Return:

Node