Module

std/collections/bs_tree.ts

Deno standard library
Go to Latest
class BSTree
implements Iterable<T>
import { BSTree } from "https://deno.land/std@0.145.0/collections/bs_tree.ts";

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

Constructors

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

Properties

protected
_size: number
protected
root: BSNode<T> | null
readonly
size: number

The amount of values stored in the binary search tree.

Methods

protected
findNode(value: T): BSNode<T> | null
protected
insertNode(Node: BSNode, value: T): BSNode<T> | null
protected
removeNode(value: T): BSNode<T> | null
protected
rotateNode(node: BSNode<T>, direction: direction)
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.

insert(value: T): boolean

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

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.

rnlValues(): IterableIterator<T>

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

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

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

Static Methods

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

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

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