The type of element that will be stored
The type of key used to index
Construct a new AVL tree index by providing a list of elements that should be stored inside the index or a more complex object detailing e.g. how the keys of the elements should be extracted and how to comare individual elements.
See the examples on the top of this page for more information on how to construct a new index of this type.
Add a new element to the index. Whether the element is ignored, replaced or whether an error is thrown depends on the value passed to onDuplicateKeys and onDuplicateElements.
This operation takes O(log(n))
time.
The function will first attempt to apply onDuplicateElements and if that didn't do anything special it will continue with onDuplicateKeys.
The return value of the function depends on whether element
was added,
ignored or replaced:
true
with a
cursor pointing to the newly added element.true
with a cursor
pointing to the location where the element was replaced.false
with a cursor
pointing to the location of the element in the index that forced this
element to be ignored.A transparent object obtained with AVLTreeIndex.getAddHint that can speed up the insertion process.
Make a shallow copy of this tree so that the new tree contains the exact same elements but inserting and removing elements will not change the original tree.
import { AVLTreeIndex } from "scl";
const index = new AVLTreeIndex<number>([1, 2, 3]);
const cloned = index.clone();
cloned.delete(2);
assert(cloned.size === 2);
assert(index.size === 3);
This method currently takes O(n.log(n))
time.
Delete an element from the tree by providing its location in the tree with an AVLTreeIndexCursor.
This method takes O(log(n))
time. It is slightly faster than deleting
the element by key due to the fact that a search for the node has already
been done.
Get a range of elements that contain the given key. The range may be empty if no elements with the requested key were found.
const aged32 = personsSortedByAge.equalKeys(32);
// There are no people who are exactly 32 years old
assert(aged32.size === 0);
for (const person of personsSortedByAge.equalKeys(17)) {
console.log(`${person.firstName} is 17 years old.`);
}
The key that should be searched for
A range of elements that contain the given key
This method always returns the topmost node that contains the given key, which means that calling next() on the result will always return a node with the same key if there is any.
This method takes O(log(n))
time.
The key to search for.
Find the element whose key is at most equal to the given key. If no key is equal to the requested key, the element with a key just slighly lower than the requested key is returned.
const jack = personsSortedByAge.findKey(34);
// The following will return Jessie (aged 25)
const oldestPersonYoungerThan30 = personsSortedByAge.lowerKey(30)
Generated using TypeDoc
A tree-like data structure that implements the Adelson-Velsky and Landis algorithm for inserting and deleting nodes. The tree will always be almost completely balanced and is very performant when there are frequent lookups but not as much mutations.
You can use trees as an alternative to hashing. Binary search trees have the added bonus that their elements are sorted, so if you add 1, 4, 3, 2 into an AVL tree in that order the elements will be returned as 1, 2, 3, 4.
⚠️ If you don't require the elements to be sorted hashing might be faster.
The following table lists the performance characteristics of the most commonly used methods of an AVL tree:
O(log(n))
O(1)
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(1)
Examples
Constructing AVL trees and adding elements
You create a new AVL tree by using the
new
keyword. Use add to insert elements into the tree.Alternatively, you can pass any Iterable as the first argument. So the above is equivalent to the following:
Choosing the key and determining how to detect duplicates
Deterministic finite automatons are frequently used in computer science to model all kinds of computations. In this example, we store the mapping from one state of the automaton to another. For the sake of this example, we want the transitions to be sorted on the character is accepted. By definition, multiple transitions with the same character are not allowed.
Allowing multiple elements with the same key
In this example, we index people based on their age. However, many people may have the same age, so we have to allow duplicate keys in order to remedy this. For the sake of the example, we simply ignore people that have already been added.
Subclassing AVLTreeIndex
In the second example, it might become cumbersome to create many of the same type of indices. Therefore, we have made it possible to subclass the AVL tree and initialize it with your own configuration each time a new tree is constructed.