dastal - v5.0.0 / AATree
An AA tree is a form of balanced tree used for storing and retrieving ordered data efficiently (source).
AA trees are named for Arne Andersson, their inventor. They are a variation of the red–black tree, which supports efficient addition and deletion of entries. Unlike red–black trees, additional constraints on the balancing mechanism greatly simplifies the implementation as well as maintenance operations; While a red–black tree needs to consider seven different shapes to properly balance the tree, an AA tree only needs to consider two shapes.
The performance of an AA tree is equivalent to the performance of a red–black tree. While an AA tree makes more rotations than a red-black tree, the simpler algorithms tend to be faster, which balances out to similar performance. A red-black tree is more consistent in its performance, but an AA tree tends to be flatter, which results in slightly faster search times.
| Name |
|---|
T |
- SortedTree<T>
• new AATree<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 AATree<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): AATree<T>
Inserts an element into the tree.
| Name | Type |
|---|---|
element |
T |
AATree<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