Class AvlTree<T>

Implements the AVL Tree data structure for fast insertion and sorting.

license: Copyright Daniel Imms http://www.growingwiththeweb.com. Modified by the Miratope authors. Released under the MIT license. See LICENSE in the project root for details.

Type parameters

T

Hierarchy

AvlTree

Index

Constructors

constructor

Properties

Methods

Constructors

constructor

new AvlTree(customCompare: ((a: T, b: T) => number) | null): AvlTree

- Defined in src/ts/Data structures/avl-tree.ts:45
Class constructor.
Parameters
- customCompare: ((a: T, b: T) => number) | null
  An optional custom compare function. Overrides compare, and has to work analogously.
Returns AvlTree

Properties

Private insertedNode

insertedNode: AvlNode<T> | null

Temporary variable for insert. Stores the new inserted node.

Private root

root: AvlNode<T> | null

The root of the AVL tree.

Private size

size: number

The element count of the AVL tree.

Methods

Private _delete

_delete(key: T, root: AvlNode<T> | null): AvlNode<T> | null

- Defined in src/ts/Data structures/avl-tree.ts:198
Deletes a node with a specific key from the tree.
Parameters
- key: T
  The key being deleted.
- root: AvlNode<T> | null
  The root of the tree to delete from.
Returns AvlNode<T> | null
The new tree root.

Private _insert

_insert(key: T, root: AvlNode<T> | null): AvlNode<T>

- Defined in src/ts/Data structures/avl-tree.ts:96
Inserts a new node with a specific key into the tree.
Parameters
- key: T
  The key being inserted.
- root: AvlNode<T> | null
  The root of the tree to insert in.
Returns AvlNode<T>
The new tree root.

Private compare

compare(a: T, b: T): number

- Defined in src/ts/Data structures/avl-tree.ts:69
The default compare function. Can be overwritten in the constructor.
Parameters
- a: T
  The first key to compare.
- b: T
  The second key to compare.
Returns number
-1, 0 or 1 depending on whether a is smaller, equal or larger than b, respectively.

contains

contains(key: T): boolean

- Defined in src/ts/Data structures/avl-tree.ts:323
Gets whether a node with a specific key is within the tree.
Parameters
- key: T
  The key being searched for.
Returns boolean
Whether a node with the key exists.

delete

delete(key: T): void

- Defined in src/ts/Data structures/avl-tree.ts:186
Deletes a node with a specific key from the tree.
Parameters
- key: T
  The key being deleted.
Returns void

findMaximum

findMaximum(): T | null

- Defined in src/ts/Data structures/avl-tree.ts:359
Returns T | null
The maximum key in the tree.

findMaximumNode

findMaximumNode(): AvlNode<T> | null

- Defined in src/ts/Data structures/avl-tree.ts:367
Returns AvlNode<T> | null
The maximum node in the tree.

findMinimum

findMinimum(): T | null

- Defined in src/ts/Data structures/avl-tree.ts:331
Returns T | null
The minimum key in the tree.

findMinimumNode

findMinimumNode(): AvlNode<T> | null

- Defined in src/ts/Data structures/avl-tree.ts:339
Returns AvlNode<T> | null
The minimum node in the tree.

Private get

get(key: T, root: AvlNode<T>): AvlNode<T> | null

- Defined in src/ts/Data structures/avl-tree.ts:303
Gets a node within the tree with a specific key.
Parameters
- key: T
  The key being searched for.
- root: AvlNode<T>
  The root of the tree to search in.
Returns AvlNode<T> | null
The node or null if it doesn't exist.

getNode

getNode(key: T): AvlNode<T> | null

- Defined in src/ts/Data structures/avl-tree.ts:290
Gets the node within the tree with a specific key.
Parameters
- key: T
  The key being searched for.
Returns AvlNode<T> | null
The node or null if it doesn't exist.

getSize

getSize(): number

- Defined in src/ts/Data structures/avl-tree.ts:387
Returns number
The size of the tree.

insert

insert(key: T): AvlNode<T>

- Defined in src/ts/Data structures/avl-tree.ts:81
Inserts a new node with a specific key into the tree.
Parameters
- key: T
  The key being inserted.
Returns AvlNode<T>
The inserted node.

isEmpty

isEmpty(): boolean

- Defined in src/ts/Data structures/avl-tree.ts:394
Returns boolean
Whether the tree is empty.

next

next(node: AvlNode<T>): AvlNode<T> | null

- Defined in src/ts/Data structures/avl-tree.ts:147
Finds the next node in the tree.
Parameters
- node: AvlNode<T>
  The current node in the tree.
Returns AvlNode<T> | null
The next node in the tree.

prev

prev(node: AvlNode<T>): AvlNode<T> | null

- Defined in src/ts/Data structures/avl-tree.ts:167
Finds the previous node in the tree.
Parameters
- node: AvlNode<T>
  The current node in the tree.
Returns AvlNode<T> | null
The previous node in the tree.

Static getBalanceState

getBalanceState<U>(node: AvlNode<U>): BalanceState

- Defined in src/ts/Data structures/avl-tree.ts:449
Gets the balance state of a node, indicating whether the left or right sub-trees are unbalanced.
Type parameters
- U
Parameters
- node: AvlNode<U>
  The node to get the difference from.
Returns BalanceState
The BalanceState of the node.

Static Private maxValueNode

maxValueNode<U>(root: AvlNode<U>): AvlNode<U>

- Defined in src/ts/Data structures/avl-tree.ts:378
Gets the maximum value node, rooted in a particular node.
Type parameters
- U
Parameters
- root: AvlNode<U>
  The node to search.
Returns AvlNode<U>
The node with the maximum key in the tree.

Static Private minValueNode

minValueNode<U>(root: AvlNode<U>): AvlNode<U>

- Defined in src/ts/Data structures/avl-tree.ts:350
Gets the minimum value node, rooted in a particular node.
Type parameters
- U
Parameters
- root: AvlNode<U>
  The node to search.
Returns AvlNode<U>
The node with the minimum key in the tree.

Generated using TypeDoc, the 1/31/2021 at 6:18:55 AM