AvlTree

Defined in: packages/data/src/tree/avl-tree.ts:35

A self-balancing binary search tree: a BinarySearchTree that keeps every node’s two subtrees within one level of each other.

That invariant bounds the height at ~1.44 log₂(n), so every operation is O(log n) in the worst case — including the sorted-input case that degenerates a plain BinarySearchTree into a linked list. The price is a height field per node and up to O(log n) rotations per insert or delete. Prefer this unless the input is known to arrive unordered.

AVL keeps a tighter height bound than a red-black tree, so lookups are slightly faster and mutations slightly slower; pick on which dominates.

Extends

• BinarySearchTree<T>

Type Parameters

T

T extends DefinedValue

The element type. Anything except undefined.

Constructors

Constructor

new AvlTree<T>(iterable?, options?): AvlTree<T>

Defined in: packages/data/src/tree/avl-tree.ts:36

Parameters

iterable?

Iterable<T, any, any>

options?

AvlTreeOptions<T>

Returns

AvlTree<T>

Overrides

BinarySearchTree.constructor

Properties

comparator

readonly comparator: Comparator<T>

Defined in: packages/data/src/tree/binary-search-tree.ts:51

Inherited from

BinarySearchTree.comparator

Accessors

root

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

IBinaryTreeNode<T> | null

Inherited from

BinarySearchTree.root

Methods

[iterator]()

[iterator](): Iterator<T>

Defined in: packages/data/src/tree/binary-search-tree.ts:67

In-order, so ascending under the comparator.

Returns

Iterator<T>

Inherited from

BinarySearchTree.[iterator]

---

add()

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

value

T

Returns

void

Inherited from

BinarySearchTree.add

---

addAll()

addAll(values): void

Defined in: packages/data/src/tree/binary-search-tree.ts:119

O(m·h) in the number of values.

Parameters

values

Iterable<T>

Returns

void

Inherited from

BinarySearchTree.addAll

---

ceiling()

ceiling(query): T | undefined

Defined in: packages/data/src/tree/binary-search-tree.ts:178

The smallest element >= query. O(h).

Parameters

query

T

Returns

T | undefined

Inherited from

BinarySearchTree.ceiling

---

clear()

clear(): void

Defined in: packages/data/src/tree/binary-search-tree.ts:75

Removes all elements from the collection.

Returns

void

Inherited from

BinarySearchTree.clear

---

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

number

Inherited from

BinarySearchTree.count

---

delete()

delete(value): boolean

Defined in: packages/data/src/tree/binary-search-tree.ts:131

O(h).

Parameters

value

T

Returns

boolean

Inherited from

BinarySearchTree.delete

---

difference()

difference(other): ISet<T>

Defined in: packages/data/src/tree/binary-search-tree.ts:266

O((n + m) log n). Ascending.

Parameters

other

Iterable<T>

Returns

ISet<T>

Inherited from

BinarySearchTree.difference

---

floor()

floor(query): T | undefined

Defined in: packages/data/src/tree/binary-search-tree.ts:155

The largest element <= query. O(h).

Parameters

query

T

Returns

T | undefined

Inherited from

BinarySearchTree.floor

---

has()

has(value): boolean

Defined in: packages/data/src/tree/binary-search-tree.ts:126

O(h).

Parameters

value

T

Returns

boolean

Inherited from

BinarySearchTree.has

---

height()

height(): number

Defined in: packages/data/src/tree/avl-tree.ts:45

The longest root-to-leaf path, in nodes. 0 when empty. O(1).

Returns

number

---

intersection()

intersection(other): ISet<T>

Defined in: packages/data/src/tree/binary-search-tree.ts:253

O(m log n). Ascending.

Parameters

other

Iterable<T>

Returns

ISet<T>

Inherited from

BinarySearchTree.intersection

---

isDisjointFrom()

isDisjointFrom(other): boolean

Defined in: packages/data/src/tree/binary-search-tree.ts:321

O(m log n).

Parameters

other

Iterable<T>

Returns

boolean

Inherited from

BinarySearchTree.isDisjointFrom

---

isSubsetOf()

isSubsetOf(other): boolean

Defined in: packages/data/src/tree/binary-search-tree.ts:296

O(n log m).

Parameters

other

Iterable<T>

Returns

boolean

Inherited from

BinarySearchTree.isSubsetOf

---

isSupersetOf()

isSupersetOf(other): boolean

Defined in: packages/data/src/tree/binary-search-tree.ts:310

O(m log n).

Parameters

other

Iterable<T>

Returns

boolean

Inherited from

BinarySearchTree.isSupersetOf

---

max()

max(): T | undefined

Defined in: packages/data/src/tree/binary-search-tree.ts:150

The largest element. O(h).

Returns

T | undefined

Inherited from

BinarySearchTree.max

---

min()

min(): T | undefined

Defined in: packages/data/src/tree/binary-search-tree.ts:145

The smallest element. O(h).

Returns

T | undefined

Inherited from

BinarySearchTree.min

---

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

from?

T

Inclusive lower bound. Unbounded when omitted.

to?

T

Exclusive upper bound. Unbounded when omitted.

Returns

IterableIterator<T>

Inherited from

BinarySearchTree.range

---

symmetricDifference()

symmetricDifference(other): ISet<T>

Defined in: packages/data/src/tree/binary-search-tree.ts:279

O((n + m) log n). Ascending.

Parameters

other

Iterable<T>

Returns

ISet<T>

Inherited from

BinarySearchTree.symmetricDifference

---

union()

union(other): ISet<T>

Defined in: packages/data/src/tree/binary-search-tree.ts:243

O((n + m) log n). Ascending.

Parameters

other

Iterable<T>

Returns

ISet<T>

Inherited from

BinarySearchTree.union