BinarySearchTree
Defined in: packages/data/src/tree/binary-search-tree.ts:45
An unbalanced binary search tree, ordered by a caller-supplied comparator.
Time complexity: O(h) per lookup, insert and delete, where h is the tree’s
height. That is O(log n) only while the insertion order keeps it bushy —
inserting already-sorted data degenerates it into a linked list and every
operation becomes O(n). That is the caller’s problem to avoid, by choosing
AvlTree instead, which pays a little more per insert to guarantee O(log
n) worst case. This class exists for the case where the input is known to be
unordered and the rebalancing is not worth it.
Iteration is in-order, so it is sorted, and is O(n) for the whole traversal.
Extended by
Section titled “Extended by”Type Parameters
Section titled “Type Parameters”T extends DefinedValue
The element type. Anything except undefined.
Implements
Section titled “Implements”ISearchTree<T>
Constructors
Section titled “Constructors”Constructor
Section titled “Constructor”new BinarySearchTree<
T>(iterable?,options?):BinarySearchTree<T>
Defined in: packages/data/src/tree/binary-search-tree.ts:53
Parameters
Section titled “Parameters”iterable?
Section titled “iterable?”Iterable<T, any, any>
options?
Section titled “options?”Returns
Section titled “Returns”BinarySearchTree<T>
Properties
Section titled “Properties”comparator
Section titled “comparator”
readonlycomparator:Comparator<T>
Defined in: packages/data/src/tree/binary-search-tree.ts:51
Implementation of
Section titled “Implementation of”Accessors
Section titled “Accessors”Get Signature
Section titled “Get Signature”get root():
IBinaryTreeNode<T> |null
Defined in: packages/data/src/tree/binary-search-tree.ts:62
The root, or null when empty. Exposed by ISearchTree for traversal.
Returns
Section titled “Returns”IBinaryTreeNode<T> | null
Implementation of
Section titled “Implementation of”Methods
Section titled “Methods”[iterator]()
Section titled “[iterator]()”[iterator]():
Iterator<T>
Defined in: packages/data/src/tree/binary-search-tree.ts:67
In-order, so ascending under the comparator.
Returns
Section titled “Returns”Iterator<T>
Implementation of
Section titled “Implementation of”add(
value):void
Defined in: packages/data/src/tree/binary-search-tree.ts:81
O(h). A value already held is not re-added.
Parameters
Section titled “Parameters”T
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”addAll()
Section titled “addAll()”addAll(
values):void
Defined in: packages/data/src/tree/binary-search-tree.ts:119
O(m·h) in the number of values.
Parameters
Section titled “Parameters”values
Section titled “values”Iterable<T>
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”ceiling()
Section titled “ceiling()”ceiling(
query):T|undefined
Defined in: packages/data/src/tree/binary-search-tree.ts:178
The smallest element >= query. O(h).
Parameters
Section titled “Parameters”T
Returns
Section titled “Returns”T | undefined
Implementation of
Section titled “Implementation of”clear()
Section titled “clear()”clear():
void
Defined in: packages/data/src/tree/binary-search-tree.ts:75
Removes all elements from the collection.
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”count()
Section titled “count()”count():
number
Defined in: packages/data/src/tree/binary-search-tree.ts:71
The number of elements in the collection.
A method, not a getter: its async counterpart needs a round trip to the backing store, and a member must have the same shape in both.
Returns
Section titled “Returns”number
Implementation of
Section titled “Implementation of”delete()
Section titled “delete()”delete(
value):boolean
Defined in: packages/data/src/tree/binary-search-tree.ts:131
O(h).
Parameters
Section titled “Parameters”T
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”difference()
Section titled “difference()”difference(
other):ISet<T>
Defined in: packages/data/src/tree/binary-search-tree.ts:266
O((n + m) log n). Ascending.
Parameters
Section titled “Parameters”Iterable<T>
Returns
Section titled “Returns”ISet<T>
Implementation of
Section titled “Implementation of”floor()
Section titled “floor()”floor(
query):T|undefined
Defined in: packages/data/src/tree/binary-search-tree.ts:155
The largest element <= query. O(h).
Parameters
Section titled “Parameters”T
Returns
Section titled “Returns”T | undefined
Implementation of
Section titled “Implementation of”has(
value):boolean
Defined in: packages/data/src/tree/binary-search-tree.ts:126
O(h).
Parameters
Section titled “Parameters”T
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”intersection()
Section titled “intersection()”intersection(
other):ISet<T>
Defined in: packages/data/src/tree/binary-search-tree.ts:253
O(m log n). Ascending.
Parameters
Section titled “Parameters”Iterable<T>
Returns
Section titled “Returns”ISet<T>
Implementation of
Section titled “Implementation of”isDisjointFrom()
Section titled “isDisjointFrom()”isDisjointFrom(
other):boolean
Defined in: packages/data/src/tree/binary-search-tree.ts:321
O(m log n).
Parameters
Section titled “Parameters”Iterable<T>
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”isSubsetOf()
Section titled “isSubsetOf()”isSubsetOf(
other):boolean
Defined in: packages/data/src/tree/binary-search-tree.ts:296
O(n log m).
Parameters
Section titled “Parameters”Iterable<T>
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”isSupersetOf()
Section titled “isSupersetOf()”isSupersetOf(
other):boolean
Defined in: packages/data/src/tree/binary-search-tree.ts:310
O(m log n).
Parameters
Section titled “Parameters”Iterable<T>
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”max():
T|undefined
Defined in: packages/data/src/tree/binary-search-tree.ts:150
The largest element. O(h).
Returns
Section titled “Returns”T | undefined
Implementation of
Section titled “Implementation of”min():
T|undefined
Defined in: packages/data/src/tree/binary-search-tree.ts:145
The smallest element. O(h).
Returns
Section titled “Returns”T | undefined
Implementation of
Section titled “Implementation of”range()
Section titled “range()”range(
from?,to?):IterableIterator<T>
Defined in: packages/data/src/tree/binary-search-tree.ts:206
Every element in [from, to), ascending. O(h + k) in the number yielded.
Parameters
Section titled “Parameters”T
Inclusive lower bound. Unbounded when omitted.
T
Exclusive upper bound. Unbounded when omitted.
Returns
Section titled “Returns”IterableIterator<T>
Implementation of
Section titled “Implementation of”symmetricDifference()
Section titled “symmetricDifference()”symmetricDifference(
other):ISet<T>
Defined in: packages/data/src/tree/binary-search-tree.ts:279
O((n + m) log n). Ascending.
Parameters
Section titled “Parameters”Iterable<T>
Returns
Section titled “Returns”ISet<T>
Implementation of
Section titled “Implementation of”ISearchTree.symmetricDifference
union()
Section titled “union()”union(
other):ISet<T>
Defined in: packages/data/src/tree/binary-search-tree.ts:243
O((n + m) log n). Ascending.
Parameters
Section titled “Parameters”Iterable<T>
Returns
Section titled “Returns”ISet<T>