Class BSTree<T>

An unbalanced binary search tree.

Operations take O(h) time, where h is the height of the tree: O(log n) on random input, but O(n) when values are inserted in sorted order. Many random removals mixed with insertions also make it deeper over time. Prefer AVLTree unless the input order is known to be random.

Like Array.from, from() called on a subclass creates an instance of that subclass. TypeScript requires the subclass constructor to accept the comparator as its only argument and the values to match the subclass type.

Example

const tree = new BSTree<number>();
tree.insert(3);
tree.insert(1);
tree.toArray(); // [1, 3]

Type Parameters

Hierarchy (View Summary)

SortedTree<T>
- BSTree

Index

Constructors

constructor

new BSTree<T>(compare: Comparator<T>): BSTree<T>
Type Parameters
- T
Parameters
- compare: Comparator<T>
  The sort order. Optional only for numbers, strings and bigints. In generic code where TypeScript cannot tell that T is one of them (T extends number), pass a comparator or create the tree with BSTree.from<T>([]).
Returns BSTree<T>

Throws
If compare is neither a function nor undefined.
Overrides SortedTree<T>.constructor
- Defined in bstree.ts:32
new BSTree<T>(...args: ComparatorArgs<T>): BSTree<T>
Type Parameters
- T
Parameters
- ...args: ComparatorArgs<T>
Returns BSTree<T>
Overrides SortedTree<T>.constructor
- Defined in bstree.ts:33

Accessors

height

get height(): number
The number of edges on the longest path from the root to a leaf: -1 for an empty tree and 0 for a tree with a single value. O(1).

Returns number
Inherited from SortedTree.height
- Defined in sorted-tree.ts:62

size

get size(): number
The number of values in the tree. O(1).

Returns number
Inherited from SortedTree.size
- Defined in sorted-tree.ts:54

Methods

[iterator]

"[iterator]"(): TreeIterator<T>
Same as SortedTree.values.

Returns TreeIterator<T>
Inherited from SortedTree.[iterator]
- Defined in sorted-tree.ts:273

ceil

ceil(value: T): T | undefined
Returns the least value greater than or equal to value.
Parameters
- value: T
Returns T | undefined

Throws
If the comparator rejects the value.
Inherited from SortedTree.ceil
- Defined in sorted-tree.ts:197

clear

clear(): void
Removes all values.

Returns void
Inherited from SortedTree.clear
- Defined in sorted-tree.ts:144

delete

delete(value: T): boolean
Removes the value equal to value.
Parameters
- value: T
Returns boolean
true if a value was removed.

Throws
If the comparator rejects the value.
Inherited from SortedTree.delete
- Defined in sorted-tree.ts:131

floor

floor(value: T): T | undefined
Returns the greatest value less than or equal to value.
Parameters
- value: T
Returns T | undefined

Throws
If the comparator rejects the value.
Inherited from SortedTree.floor
- Defined in sorted-tree.ts:188

forEach

forEach(
callback: (value: T, index: number, tree: this) => void,
thisArg?: unknown,
): void
Calls callback for every value in ascending order.
Parameters
- callback: (value: T, index: number, tree: this) => void
- OptionalthisArg: unknown
Returns void
Inherited from SortedTree.forEach
- Defined in sorted-tree.ts:278

get

get(value: T): T | undefined
Returns the stored value equal to value. Useful when the comparator only looks at a key: pass a probe with that key to get the stored record.
Parameters
- value: T
Returns T | undefined
Example
```
const users = new AVLTree<{ id: number; name: string }>((a, b) => a.id - b.id);
users.insert({ id: 1, name: "Alice" });
users.get({ id: 1, name: "" })?.name; // "Alice"
```
Throws
If the comparator rejects the value.
Inherited from SortedTree.get
- Defined in sorted-tree.ts:87

getOrInsert

getOrInsert(value: T): T

Returns the stored value equal to value, inserting value first if there is none.

Parameters

value: T

Returns T

Example

const book = new AVLTree<{ price: number; orders: number[] }>(
  (a, b) => a.price - b.price,
);
book.getOrInsert({ price: 10, orders: [] }).orders.push(1);
book.getOrInsert({ price: 10, orders: [] }).orders.push(2);
book.get({ price: 10, orders: [] })?.orders; // [1, 2]

Throws

If the comparator rejects the value.

has

has(value: T): boolean
Checks whether the tree contains a value equal to value.
Parameters
- value: T
Returns boolean

Throws
If the comparator rejects the value.
Inherited from SortedTree.has
- Defined in sorted-tree.ts:71

higher

higher(value: T): T | undefined
Returns the least value strictly greater than value.
Parameters
- value: T
Returns T | undefined

Throws
If the comparator rejects the value.
Inherited from SortedTree.higher
- Defined in sorted-tree.ts:215

insert

insert(value: T): boolean
Inserts value unless an equal value is already stored (that value is kept as is).
Parameters
- value: T
Returns boolean
true if the value was inserted.

Throws
If the comparator rejects the value.
Inherited from SortedTree.insert
- Defined in sorted-tree.ts:98

lower

lower(value: T): T | undefined
Returns the greatest value strictly less than value.
Parameters
- value: T
Returns T | undefined

Throws
If the comparator rejects the value.
Inherited from SortedTree.lower
- Defined in sorted-tree.ts:206

max

max(): T | undefined
Returns the largest value, or undefined if the tree is empty.

Returns T | undefined
Inherited from SortedTree.max
- Defined in sorted-tree.ts:155

min

min(): T | undefined
Returns the smallest value, or undefined if the tree is empty.

Returns T | undefined
Inherited from SortedTree.min
- Defined in sorted-tree.ts:150

popMax

popMax(): T | undefined
Removes and returns the largest value.

Returns T | undefined
Inherited from SortedTree.popMax
- Defined in sorted-tree.ts:172

popMin

popMin(): T | undefined
Removes and returns the smallest value.

Returns T | undefined
Inherited from SortedTree.popMin
- Defined in sorted-tree.ts:160

range

range(options?: RangeOptions<T>): TreeIterator<T>
Iterates over the values within the bounds, in ascending order unless reverse is set. Modifications during the iteration follow the same rules as for SortedTree.values.
Parameters
- Optionaloptions: RangeOptions<T>
Returns TreeIterator<T>
Example
```
const tree = AVLTree.from([1, 2, 3, 4, 5]);
[...tree.range({ gte: 2, lt: 4 })]; // [2, 3]
[...tree.range({ gt: 3, reverse: true })]; // [5, 4]
```
Throws
If both gt and gte (or lt and lte) are set, or if the comparator rejects a bound. When range is called, each bound is compared with itself and, if the tree is not empty, with a stored value, so an invalid bound throws before the iteration starts.
Inherited from SortedTree.range
- Defined in sorted-tree.ts:260

toArray

toArray(): T[]
Returns the values in ascending order.

Returns T[]
Inherited from SortedTree.toArray
- Defined in sorted-tree.ts:291

values

values(): TreeIterator<T>
Iterates over the values in ascending order.

The tree may be modified during the iteration: removed values are skipped, values inserted ahead of the iterator are visited and values inserted behind it are not. Unlike with a Set, a value is never visited twice, even if it is deleted and inserted again.

After the tree changes, the iterator finds its place again by comparing with the last value it returned. While you use the iterator, do not change the fields the comparator reads of that value, even after removing it from the tree.

Returns TreeIterator<T>
Inherited from SortedTree.values
- Defined in sorted-tree.ts:232

valuesReversed

valuesReversed(): TreeIterator<T>
Iterates over the values in descending order. Modifications during the iteration follow the same rules as for SortedTree.values.

Returns TreeIterator<T>
Inherited from SortedTree.valuesReversed
- Defined in sorted-tree.ts:240

`Static`from

from(
this: new (compare?: Comparator<number>) => BSTree<number>,
values: Iterable<number>,
): BSTree<number>
Creates a tree from numbers, strings or bigints.
Parameters
- this: new (compare?: Comparator<number>) => BSTree<number>
- values: Iterable<number>
Returns BSTree<number>
- Defined in bstree.ts:39
from(
this: new (compare?: Comparator<string>) => BSTree<string>,
values: Iterable<string>,
): BSTree<string>
Creates a tree from numbers, strings or bigints.
Parameters
- this: new (compare?: Comparator<string>) => BSTree<string>
- values: Iterable<string>
Returns BSTree<string>
- Defined in bstree.ts:43
from(
this: new (compare?: Comparator<bigint>) => BSTree<bigint>,
values: Iterable<bigint>,
): BSTree<bigint>
Creates a tree from numbers, strings or bigints.
Parameters
- this: new (compare?: Comparator<bigint>) => BSTree<bigint>
- values: Iterable<bigint>
Returns BSTree<bigint>
- Defined in bstree.ts:47
from<T>(
    this: NoInfer<new (compare: Comparator<T>) => BSTree<T>>,
    values: Iterable<T>,
    compare: Comparator<T>,
): BSTree<T>
Creates a tree from any values sorted by compare.
Type Parameters
- T
Parameters
- this: NoInfer<new (compare: Comparator<T>) => BSTree<T>>
- values: Iterable<T>
- compare: Comparator<T>
Returns BSTree<T>
- Defined in bstree.ts:52
from<T extends bigint>(
    this: NoInfer<new (compare?: Comparator<T>) => BSTree<T>>,
    values: Iterable<T>,
    compare?: Comparator<T>,
): BSTree<T>
Creates a tree from bigints of an explicit type, also in generic code (BSTree.from<T>(values) with T extends bigint).
Type Parameters
- T extends bigint
Parameters
- this: NoInfer<new (compare?: Comparator<T>) => BSTree<T>>
- values: Iterable<T>
- Optionalcompare: Comparator<T>
Returns BSTree<T>
- Defined in bstree.ts:61
from<T extends number>(
    this: NoInfer<new (compare?: Comparator<T>) => BSTree<T>>,
    values: Iterable<T>,
    compare?: Comparator<T>,
): BSTree<T>
Creates a tree from numbers of an explicit type, such as BSTree.from<1 | 2>([1, 2]), also in generic code (BSTree.from<T>(values) with T extends number).
Type Parameters
- T extends number
Parameters
- this: NoInfer<new (compare?: Comparator<T>) => BSTree<T>>
- values: Iterable<T>
- Optionalcompare: Comparator<T>
Returns BSTree<T>
- Defined in bstree.ts:71
from<T extends string>(
    this: NoInfer<new (compare?: Comparator<T>) => BSTree<T>>,
    values: Iterable<T>,
    compare?: Comparator<T>,
): BSTree<T>
Creates a tree from strings of an explicit type, also in generic code (BSTree.from<T>(values) with T extends string).
Type Parameters
- T extends string
Parameters
- this: NoInfer<new (compare?: Comparator<T>) => BSTree<T>>
- values: Iterable<T>
- Optionalcompare: Comparator<T>
Returns BSTree<T>
- Defined in bstree.ts:80

Class BSTree<T>

Example

Type Parameters

Hierarchy (View Summary)

Index

Constructors

Accessors

Methods

Constructors

constructor

Type Parameters

Parameters

Returns BSTree<T>

Throws

Type Parameters

Parameters

Returns BSTree<T>

Accessors

height

Returns number

size

Returns number

Methods

[iterator]

Returns TreeIterator<T>

ceil

Parameters

Returns T | undefined

Throws

clear

Returns void

delete

Parameters

Returns boolean

Throws

floor

Parameters

Returns T | undefined

Throws

forEach

Parameters

Returns void

get

Parameters

Returns T | undefined

Example

Throws

getOrInsert

Parameters

Returns T

Example

Throws

has

Parameters

Returns boolean

Throws

higher

Parameters

Returns T | undefined

Throws

insert

Parameters

Returns boolean

Throws

lower

Parameters

Returns T | undefined

Throws

max

Returns T | undefined

min

Returns T | undefined

popMax

Returns T | undefined

popMin

Returns T | undefined

range

Parameters

Returns TreeIterator<T>

Example

`Static`from