BinarySearchTree - @std/data-structures

class BinarySearchTree

implements Iterable<T>

An unbalanced binary search tree. The values are in ascending order by default, using JavaScript's built-in comparison operators to sort the values.

For performance, it's recommended that you use a self-balancing binary search tree instead of this one unless you are extending this to create a self-balancing tree. See RedBlackTree for an example of how BinarySearchTree can be extended to create a self-balancing binary search tree.

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

Examples

Example 1

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

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",
]);

Constructors

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

Type Parameters

T

Static Methods

from<T>(collection: ArrayLike<T> | Iterable<T> | BinarySearchTree<T>): BinarySearchTree<T>

Creates a new binary search tree from an array like or iterable object.

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

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

Properties

readonly

size: number

The amount of values stored in the binary search tree.

protected

_size: number

protected

root: BinarySearchNode<T> | null

Methods

[Symbol.iterator](): IterableIterator<T>

Returns an iterator that uses in-order (LNR) tree traversal for retrieving values from the binary search tree.

clear(): void

Removes all values from the binary search tree.

find(value: T): T | null

Returns node value if found in the binary search tree.

protected

findNode(value: T): BinarySearchNode<T> | null

insert(value: T): boolean

Adds the value to the binary search tree if it does not already exist in it. Returns true if successful.

protected

insertNode(Node: BinarySearchNode,
value: T
): BinarySearchNode<T> | null

isEmpty(): boolean

Checks if the binary search tree is empty.

lnrValues(): IterableIterator<T>

Returns an iterator that uses in-order (LNR) tree traversal for retrieving values from the binary search tree.

lrnValues(): IterableIterator<T>

Returns an iterator that uses post-order (LRN) tree traversal for retrieving values from the binary search tree.

lvlValues(): IterableIterator<T>

Returns an iterator that uses level order tree traversal for retrieving values from the binary search tree.

max(): T | null

Returns the maximum value in the binary search tree or null if empty.

min(): T | null

Returns the minimum value in the binary search tree or null if empty.

nlrValues(): IterableIterator<T>

Returns an iterator that uses pre-order (NLR) tree traversal for retrieving values from the binary search tree.

remove(value: T): boolean

Removes node value from the binary search tree if found. Returns true if found and removed.

protected

removeNode(node: BinarySearchNode<T>): BinarySearchNode<T> | null

Removes the given node, and returns the node that was physically removed from the tree.

rnlValues(): IterableIterator<T>

Returns an iterator that uses reverse in-order (RNL) tree traversal for retrieving values from the binary search tree.

protected

rotateNode(node: BinarySearchNode<T>,
direction: Direction
): void

@std/data-structures@0.215.0

Examples

Example 1

Constructors

Type Parameters

Static Methods

Properties

Methods

Report package