Class RedBlackTree<T>

A red-black tree. This is a kind of self-balancing binary search tree. The values are in ascending order by default, using JavaScript's built-in comparison operators to sort the values.

Red-Black Trees require fewer rotations than AVL Trees, so they can provide faster insertions and removal operations. If you need faster lookups, you should use an AVL Tree instead. AVL Trees are more strictly balanced than Red-Black Trees, so they can provide faster lookups.

Method Average Case Worst Case
find(value) O(log n) O(log n)
insert(value) O(log n) O(log n)
remove(value) O(log n) O(log n)
min() O(log n) O(log n)
max() O(log n) O(log n)

Example: Usage

import {
  ascend,
  descend,
  RedBlackTree,
} from "@std/data-structures";
import { assertEquals } from "@std/assert";

const values = [3, 10, 13, 4, 6, 7, 1, 14];
const tree = new RedBlackTree<number>();
values.forEach((value) => tree.insert(value));
assertEquals([...tree], [1, 3, 4, 6, 7, 10, 13, 14]);
assertEquals(tree.min(), 1);
assertEquals(tree.max(), 14);
assertEquals(tree.find(42), null);
assertEquals(tree.find(7), 7);
assertEquals(tree.remove(42), false);
assertEquals(tree.remove(7), true);
assertEquals([...tree], [1, 3, 4, 6, 10, 13, 14]);

const invertedTree = new RedBlackTree<number>(descend);
values.forEach((value) => invertedTree.insert(value));
assertEquals([...invertedTree], [14, 13, 10, 7, 6, 4, 3, 1]);
assertEquals(invertedTree.min(), 14);
assertEquals(invertedTree.max(), 1);
assertEquals(invertedTree.find(42), null);
assertEquals(invertedTree.find(7), 7);
assertEquals(invertedTree.remove(42), false);
assertEquals(invertedTree.remove(7), true);
assertEquals([...invertedTree], [14, 13, 10, 6, 4, 3, 1]);

const words = new RedBlackTree<string>((a, b) =>
  ascend(a.length, b.length) || ascend(a, b)
);
["truck", "car", "helicopter", "tank", "train", "suv", "semi", "van"]
  .forEach((value) => words.insert(value));
assertEquals([...words], [
  "car",
  "suv",
  "van",
  "semi",
  "tank",
  "train",
  "truck",
  "helicopter",
]);
assertEquals(words.min(), "car");
assertEquals(words.max(), "helicopter");
assertEquals(words.find("scooter"), null);
assertEquals(words.find("tank"), "tank");
assertEquals(words.remove("scooter"), false);
assertEquals(words.remove("tank"), true);
assertEquals([...words], [
  "car",
  "suv",
  "van",
  "semi",
  "train",
  "truck",
  "helicopter",
]);

Typeparam

T The type of the values being stored in the tree.

Type Parameters

  • T
Hierarchy

Constructors

constructor

Accessors

size

Methods

[iterator] clear find insert isEmpty lnrValues lrnValues lvlValues max min nlrValues remove rnlValues from

Constructors

constructor

Accessors

size

  • get size(): number

  • The count of values stored in the binary search tree.

    The complexity of this operation is O(1).

    Returns number

    The count of values stored in the binary search tree.

    Example: Getting the size of the tree

    import { BinarySearchTree } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const tree = BinarySearchTree.from<number>([42, 43, 41]);

    assertEquals(tree.size, 3);

Methods

[iterator]

  • [iterator](): IterableIterator<T, any, any>

  • Create an iterator over this tree that traverses the tree in-order (LNR, Left-Node-Right).

    Returns IterableIterator<T, any, any>

    An iterator that traverses the tree in-order (LNR).

    Example: Using the in-order iterator

    import { BinarySearchTree } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const tree = BinarySearchTree.from([4, 1, 2, 5, 3]);

    assertEquals([...tree], [1, 2, 3, 4, 5]);

    See BinarySearchTree.prototype.lnrValues.

clear

  • clear(): void

  • Remove all values from the binary search tree.

    The complexity of this operation is O(1).

    Returns void

    Example: Clearing the tree

    import { BinarySearchTree } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const tree = BinarySearchTree.from<number>([42, 43, 41]);
    tree.clear();

    assertEquals(tree.size, 0);
    assertEquals(tree.find(42), null);

find

  • find(value): null | T

  • Check if a value exists in the binary search tree.

    The complexity of this operation depends on the underlying structure of the tree. Refer to the documentation of the structure itself for more details.

    Parameters

    • value: T

      The value to search for in the binary search tree.

    Returns null | T

    The value if it was found, or null if not found.

    Example: Finding values in the tree

    import { BinarySearchTree } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const tree = BinarySearchTree.from<number>([42]);

    assertEquals(tree.find(42), 42);
    assertEquals(tree.find(43), null);

insert

  • insert(value): boolean

  • Add a value to the red-black tree if it does not already exist in the tree.

    The complexity of this operation is on average and at worst O(log n), where n is the number of values in the tree.

    Parameters

    • value: T

      The value to insert into the tree.

    Returns boolean

    true if the value was inserted, false if the value already exists in the tree.

    Example: Inserting a value into the tree

    import { RedBlackTree } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const tree = new RedBlackTree<number>();

    assertEquals(tree.insert(42), true);
    assertEquals(tree.insert(42), false);

isEmpty

  • isEmpty(): boolean

  • Check if the binary search tree is empty.

    The complexity of this operation is O(1).

    Returns boolean

    true if the binary search tree is empty, false otherwise.

    Example: Checking if the tree is empty

    import { BinarySearchTree } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const tree = new BinarySearchTree<number>();

    assertEquals(tree.isEmpty(), true);

    tree.insert(42);

    assertEquals(tree.isEmpty(), false);

lnrValues

  • lnrValues(): IterableIterator<T, any, any>

  • Create an iterator over this tree that traverses the tree in-order (LNR, Left-Node-Right).

    Returns IterableIterator<T, any, any>

    An iterator that traverses the tree in-order (LNR).

    Example: Using the in-order LNR iterator

    import { BinarySearchTree } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const tree = BinarySearchTree.from([4, 1, 2, 5, 3]);

    assertEquals([...tree.lnrValues()], [1, 2, 3, 4, 5]);

lrnValues

  • lrnValues(): IterableIterator<T, any, any>

  • Create an iterator over this tree that traverses the tree in post-order (LRN, Left-Right-Node).

    Returns IterableIterator<T, any, any>

    An iterator that traverses the tree in post-order (LRN).

    Example: Using the post-order LRN iterator

    import { BinarySearchTree } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const tree = BinarySearchTree.from([4, 1, 2, 5, 3]);

    assertEquals([...tree.lrnValues()], [3, 2, 1, 5, 4]);

lvlValues

  • lvlValues(): IterableIterator<T, any, any>

  • Create an iterator over this tree that traverses the tree in level-order (BFS, Breadth-First Search).

    Returns IterableIterator<T, any, any>

    An iterator that traverses the tree in level-order (BFS).

    Example: Using the level-order BFS iterator

    import { BinarySearchTree } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const tree = BinarySearchTree.from([4, 1, 2, 5, 3]);

    assertEquals([...tree.lvlValues()], [4, 1, 5, 2, 3]);

max

  • max(): null | T

  • Retrieve the highest (right most) value in the binary search tree, or null if the tree is empty.

    The complexity of this operation depends on the underlying structure of the tree. Refer to the documentation of the structure itself for more details.

    Returns null | T

    The maximum value in the binary search tree, or null if the tree is empty.

    Example: Finding the maximum value in the tree

    import { BinarySearchTree } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const tree = BinarySearchTree.from<number>([42, 43, 41]);

    assertEquals(tree.max(), 43);

min

  • min(): null | T

  • Retrieve the lowest (left most) value in the binary search tree, or null if the tree is empty.

    The complexity of this operation depends on the underlying structure of the tree. Refer to the documentation of the structure itself for more details.

    Returns null | T

    The minimum value in the binary search tree, or null if the tree is empty.

    Example: Finding the minimum value in the tree

    import { BinarySearchTree } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const tree = BinarySearchTree.from<number>([42, 43, 41]);

    assertEquals(tree.min(), 41);

nlrValues

  • nlrValues(): IterableIterator<T, any, any>

  • Create an iterator over this tree that traverses the tree in pre-order (NLR, Node-Left-Right).

    Returns IterableIterator<T, any, any>

    An iterator that traverses the tree in pre-order (NLR).

    Example: Using the pre-order NLR iterator

    import { BinarySearchTree } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const tree = BinarySearchTree.from([4, 1, 2, 5, 3]);

    assertEquals([...tree.nlrValues()], [4, 1, 2, 3, 5]);

remove

  • remove(value): boolean

  • Remove a value from the red-black tree if it exists in the tree.

    The complexity of this operation is on average and at worst O(log n), where n is the number of values in the tree.

    Parameters

    • value: T

      The value to remove from the tree.

    Returns boolean

    true if the value was found and removed, false if the value was not found in the tree.

    Example: Removing values from the tree

    import { RedBlackTree } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const tree = RedBlackTree.from<number>([42]);

    assertEquals(tree.remove(42), true);
    assertEquals(tree.remove(42), false);

rnlValues

  • rnlValues(): IterableIterator<T, any, any>

  • Create an iterator over this tree that traverses the tree in reverse in-order (RNL, Right-Node-Left).

    Returns IterableIterator<T, any, any>

    An iterator that traverses the tree in reverse in-order (RNL).

    Example: Using the reverse in-order RNL iterator

    import { BinarySearchTree } from "@std/data-structures";
    import { assertEquals } from "@std/assert";

    const tree = BinarySearchTree.from([4, 1, 2, 5, 3]);
    [...tree.rnlValues()] // 5, 4, 3, 2, 1

Staticfrom

  • from<T>(collection, options?): RedBlackTree<T>

  • Create a new red-black tree from an array like, an iterable object, or an existing red-black tree.

    A custom comparison function can be provided to sort the values in a specific order. By default, the values are sorted in ascending order, unless a RedBlackTree is passed, in which case the comparison function is copied from the input tree.

    Type Parameters

    • T

    Parameters

    • collection: ArrayLike<T> | Iterable<T, any, any> | RedBlackTree<T>

      An array like, an iterable, or existing red-black tree.

    • Optionaloptions: {
          compare?: ((a: T, b: T) => number);
      }

      An optional options object to customize the comparison function.

      • Optionalcompare?: ((a: T, b: T) => number)
          • (a, b): number

          • Parameters

            Returns number

    Returns RedBlackTree<T>

    A new red-black tree with the values from the passed collection.

    Example: Creating a red-black tree from an iterable object

    import { RedBlackTree } from "@std/data-structures";

    const tree = RedBlackTree.from<number>((function*() {
      yield 3;
      yield 10;
      yield 13;
    })());

    Example: Creating a red-black tree from an existing red-black tree

    import { RedBlackTree } from "@std/data-structures";

    const tree = RedBlackTree.from<number>([3, 10, 13, 4, 6, 7, 1, 14]);
    const copy = RedBlackTree.from(tree);

    Typeparam

    T The type of the values being stored in the tree.

  • from<T, U, V>(collection, options): RedBlackTree<U>

  • Create a new red-black tree from an array like, an iterable object, or an existing red-black tree.

    A custom mapping function can be provided to transform the values before inserting them into the tree.

    A custom comparison function can be provided to sort the values in a specific order. A custom mapping function can be provided to transform the values before inserting them into the tree. By default, the values are sorted in ascending order, unless a RedBlackTree is passed, in which case the comparison function is copied from the input tree. The comparison operator is used to sort the values in the tree after mapping the values.

    Type Parameters

    • T
    • U
    • V = undefined

    Parameters

    • collection: ArrayLike<T> | Iterable<T, any, any> | RedBlackTree<T>

      An array like, an iterable, or existing red-black tree.

    • options: {
          compare?: ((a: U, b: U) => number);
          map: ((value: T, index: number) => U);
          thisArg?: V;
      }

      The options object to customize the mapping and comparison functions. The thisArg property can be used to set the this value when calling the mapping function.

      • Optionalcompare?: ((a: U, b: U) => number)
          • (a, b): number

          • Parameters

            Returns number

      • map: ((value: T, index: number) => U)
          • (value, index): U

          • Parameters

            • value: T
            • index: number

            Returns U

      • OptionalthisArg?: V

    Returns RedBlackTree<U>

    A new red-black tree with the mapped values from the passed collection.

    Typeparam

    T The type of the values in the passed collection.

    Typeparam

    U The type of the values being stored in the red-black tree.

    Typeparam

    V The type of the this context in the mapping function. Defaults to undefined.

Settings

Member Visibility

On This Page

Constructors
Accessors
Methods