Class AVLTreeIndex<T, K>

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:

Property name	Worst case
add()	O(log(n))
clear()	O(1)
equalKeys()	O(log(n))
delete()	O(log(n))
deleteAll()	O(log(n))
deleteAt()	O(log(n))
size	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.

import { AVLTreeIndex } from "scl";

const index = new AVLTreeIndex();

index.add(1);
index.add(2);
index.add(3);
Copy

Alternatively, you can pass any Iterable as the first argument. So the above is equivalent to the following:

const index = new AVLTreeIndex([
  1,
  2,
  3,
]);
Copy

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.

import { ResolveAction, AVLTreeIndex } from "scl"

interface DFAState {
  id: string;
  isFinal: boolean;
  nextStates: AVLTreeIndex<DFAStateTransition, string>;
}

interface DFAStateTransition {
  character: string;
  nextState: DFAState;
}

const nextStates = new AVLTreeIndex<DFAStateTransition, string>({
  getKey: transition => transition.character,
  compareKeys: (a, b) => a.charCodeAt(0) < b.charCodeAt(0),
  isEqual: (a, b) => a.nextState.id === b.nextState.id,
});

const s1: DFAState = {
  id: 1,
  isFinal: false,
  nextStates,
}
Copy

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.

interface Person {
  firstName: string;
  email: string;
  age: number;
}

const index = new AVLTreeIndex({
  getKey: person => person.age,
  compareKeys: (a, b) => a < b,
  onDuplicateKeys: ResolveAction.Insert,
  onDuplicateElements: ResolveAction.Ignore,
});

// OK, will be added to the index
index.add({
  firstName: 'Bob',
  email: 'thebobman@gmail.com',
  age: 34,
});

// OK, will return the existing element
const [didAdd, cursor] = index.add({
  firstName: 'Bob',
  email: 'thebobman@gmail.com',
  age: 12,
});

console.log(`Bob still is ${cursor.value.age}`)

// This will print the following result:
// - Bob (aged 17)
// - Jessie (aged 25)
// - Jack (aged 34)
// - Anna (aged 58)
for (const person of personsSortedByAge) {
  console.log(`- ${person.fullName} (aged ${person.age})`);
}
Copy

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.

import { isIterable, AVLTreeIndexOptions, AVLTreeIndex } from "scl";

class DFATransitionMap extends AVLTreeIndex<DFAStateTransition, string> {

  constructor(opts: Iterable<DFAStateTransition> | AVLTreeIndexOptions<DFAStateTransition, string>) {

    // We want to be able to pass in just a simple Iterable object, so we
    // need to add some extra logic
    if (isIterable(opts)) {
      opts = { elements: opts }
    }

    // Initialize our AVLTreeIndex with user-provided options and override
    // some options specific to DFATransitionMap
    super({
      ...opts,
      getKey: transition => transition.character,
      compareKeys: (a, b) => a.charCodeAt(0) < b.charCodeAt(0),
      isEqual: (a, b) => a.nextState.id === b.nextState.id,
    });

  }

}

const nextStates = new DFATransitionMap([
  { character: 'a', nextState: s2 }
]);
Copy