BinarySearchTree

Example: Usage

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

const values = [3, 10, 13, 4, 6, 7, 1, 14];
const tree = new BinarySearchTree<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 BinarySearchTree<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 BinarySearchTree<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",
]);

constructor

new BinarySearchTree(compare?: (a: T, b: T) => number)

Construct an empty binary search tree.

To create a binary search tree from an array like, an iterable object, or an existing binary search tree, use the BinarySearchTree.from method.

compare?: (a: T, b: T) => number

A custom comparison function to sort the values in the tree. By default, the values are sorted in ascending order.

from

static from<T>(collection: ArrayLike<T> | Iterable<T> | StableBinarySearchTree<T>, options?: { compare?: (a: T, b: T) => number }): BinarySearchTree<T>

Creates a new binary search tree from an array like, an iterable object, or an existing binary search 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 BinarySearchTree is passed, in which case the comparison function is copied from the input tree.

collection: ArrayLike<T> | Iterable<T> | StableBinarySearchTree<T>

An array like, an iterable, or existing binary search tree.

options?: { compare?: (a: T, b: T) => number }

An optional options object to customize the comparison function.

Returns

A new binary search tree created from the passed collection.

import { BinarySearchTree } from "@ende/data-structures";

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

import { BinarySearchTree } from "@ende/data-structures";

const tree = BinarySearchTree.from<number>((function*() {
  yield 42;
  yield 43;
  yield 41;
})());

import { BinarySearchTree } from "@ende/data-structures";

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

import { BinarySearchTree, descend } from "@ende/data-structures";

const tree = BinarySearchTree.from<number>(
  [42, 43, 41],
  { compare: descend }
);

static from<T, U, V = undefined>(collection: ArrayLike<T> | Iterable<T> | StableBinarySearchTree<T>, options: { compare?: (a: U, b: U) => number; map: (value: T, index: number) => U; thisArg?: V }): BinarySearchTree<U>

Create a new binary search tree from an array like, an iterable object, or an existing binary search 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 BinarySearchTree 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.

collection: ArrayLike<T> | Iterable<T> | StableBinarySearchTree<T>

An array like, an iterable, or existing binary search 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.

Returns

A new binary search tree containing the mapped values from the passed collection.

import { BinarySearchTree } from "@ende/data-structures";

const tree = BinarySearchTree.from<number, string>(
  [42, 43, 41],
  { map: (value) => value.toString() }
);

static from<T, U, V>(collection: ArrayLike<T> | Iterable<T> | StableBinarySearchTree<T>, options?: { compare?: (a: U, b: U) => number; map?: (value: T, index: number) => U; thisArg?: V }): BinarySearchTree<U>

ceiling

ceiling(value: T): T | null

Finds the lowest (leftmost) value in the binary search tree which is greater than or equal to the given value, or null if the given value is higher than all elements of the 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.

value: T

The value to search for in the binary search tree.

Returns

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

import { BinarySearchTree } from "@ende/data-structures/unstable-binary-search-tree";
import { assertEquals } from "@ende/assert";

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

assertEquals(tree.ceiling(41), 42);
assertEquals(tree.ceiling(42), 42);
assertEquals(tree.ceiling(43), null);

floor

floor(value: T): T | null

Finds the highest (rightmost) value in the binary search tree which is less than or equal to the given value, or null if the given value is lower than all elements of the 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.

value: T

The value to search for in the binary search tree.

Returns

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

import { BinarySearchTree } from "@ende/data-structures/unstable-binary-search-tree";
import { assertEquals } from "@ende/assert";

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

assertEquals(tree.floor(41), null);
assertEquals(tree.floor(42), 42);
assertEquals(tree.floor(43), 42);

higher

higher(value: T): T | null

Finds the lowest (leftmost) value in the binary search tree which is strictly greater than the given value, or null if the given value is higher than or equal to all elements of the 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.

value: T

The value to search for in the binary search tree.

Returns

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

import { BinarySearchTree } from "@ende/data-structures/unstable-binary-search-tree";
import { assertEquals } from "@ende/assert";

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

assertEquals(tree.higher(41), 42);
assertEquals(tree.higher(42), null);
assertEquals(tree.higher(43), null);

lower

lower(value: T): T | null

Finds the highest (rightmost) value in the binary search tree which is strictly less than the given value, or null if the given value is lower than or equal to all elements of the 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.

value: T

The value to search for in the binary search tree.

Returns

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

import { BinarySearchTree } from "@ende/data-structures/unstable-binary-search-tree";
import { assertEquals } from "@ende/assert";

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

assertEquals(tree.lower(41), null);
assertEquals(tree.lower(42), null);
assertEquals(tree.lower(43), 42);