dastal - v5.0.0 / AVLTree
An AVL tree is a self-balancing binary search tree (source).
It is named after inventors Georgy Adelson-Velsky and Evgenii Landis and was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property.
Lookup, insertion, and deletion all take O(log(n)) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.
AVL trees are often compared with red–black trees as both take O(log(n)) time for the basic operations. For lookup-intensive applications, AVL trees are faster than red–black trees because they are more strictly balanced. Similar to red–black trees, AVL trees are height-balanced.
| Name |
|---|
T |
- SortedTree<T>
• new AVLTree<T>(compareFn, elements?)
Instantiate a tree.
| Name |
|---|
T |
| Name | Type | Description |
|---|---|---|
compareFn |
CompareFn<T> | The function to determine the order of elements. |
elements? |
Iterable<T> |
A set of elements to initialize the tree with. |
• new AVLTree<T>(compareFn, allowDuplicates, elements?)
Instantiate a tree.
| Name |
|---|
T |
| Name | Type | Description |
|---|---|---|
compareFn |
CompareFn<T> | The function to determine the order of elements. |
allowDuplicates |
boolean |
Whether to allow duplicates |
elements? |
Iterable<T> |
A set of elements to initialize the tree with. |
• get size(): number
The number of elements in the collection.
number
▸ [iterator](): Iterator<T, any, undefined>
Receive an iterator through the list.
Note: Unexpected behavior can occur if the collection is modified during iteration.
Iterator<T, any, undefined>
An iterator through the list
▸ add(element): AVLTree<T>
Inserts an element into the tree.
| Name | Type |
|---|---|
element |
T |
AVLTree<T>
▸ clear(): void
Removes all elements.
void
▸ comparator(): CompareFn<T>
CompareFn<T>
▸ delete(element): boolean
Delete an element from the tree.
| Name | Type |
|---|---|
element |
T |
boolean
▸ has(element): boolean
Check if an element is in the tree.
| Name | Type |
|---|---|
element |
T |
boolean
▸ max(): undefined | T
Get the maximum element.
undefined | T
▸ min(): undefined | T
Get the minimum element.
undefined | T
▸ pop(): undefined | T
Remove the maximum element.
undefined | T
▸ shift(): undefined | T
Remove the minimum element.
undefined | T
▸ sorted(): Iterable<T>
Iterate through the tree in sorted order (i.e in-order traversal).
Note: Unexpected behavior can occur if the collection is modified during iteration.
Iterable<T>
▸ update(curElement, newElement): boolean
Update a specific element.
| Name | Type |
|---|---|
curElement |
T |
newElement |
T |
boolean