Skip to main content
Module

x/collections/mod.ts>BSTree

Collection data structures that are not standard built-in objects in JavaScript. This includes a vector (double-ended queue), binary heap (priority queue), binary search tree, and a red black tree.
udibo/collections
Very Popular
Go to Latest
class BSTree
implements Iterable<T>
import { BSTree } from "https://deno.land/x/collections@v0.10.1/mod.ts";

A 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?: compare<Partial<T>> | compareDefined<Partial<T>>)

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

Removes all values from the binary search tree.

find(value: Partial<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: Partial<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, U>(collection: ArrayLike<T> | Iterable<T>): BSTree<U>

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

from<T, U>(collection: ArrayLike<T> | Iterable<T>, options: { Tree?: BSTree; Node?: BSNode; compare?: compare<Partial<U>> | compareDefined<Partial<U>>; }): BSTree<U>
from<T, U, V>(collection: ArrayLike<T> | Iterable<T>, options: { Tree?: BSTree; Node?: BSNode; compare?: compare<Partial<U>> | compareDefined<Partial<U>>; map: mapDefined<T, U>; thisArg?: V; }): BSTree<U>