Neat! Pickled Muskrat!

    @tyriar/avl-tree
    TypeScript icon, indicating that this package has built-in type declarations

    2.0.6 • Public • Published

    ts-avl-tree

    Build Status Coverage Status

    A TypeScript implementation of the AVL tree data structure.

    Note that the primary purpose of this library is education but it should work in a production environment as well. It's certainly not as performant as it could be as it optimises for readability, abstraction and safety over raw performance.

    Features

    • 100% test coverage
    • Supports all common tree operations
    • Store keys with optional associated values
    • Optional custom compare function that can utilize both key and value to give full control over the order of the data

    Install

    npm install --save @tyriar/avl-tree

    Usage

    See the typings file for the full API.

    // Import npm module
    import { AvlTree } from '@tyriar/avl-tree';
    
    // Construct AvlTree
    const tree = new AvlTree<number, number>();
    
    // Insert keys
    tree.insert(1);
    tree.insert(2);
    tree.insert(3);
    tree.insert(4);
    tree.insert(5);
    console.log('size: ' + tree.size);
    console.log('contains 2: ' + tree.contains(2));
    console.log('contains 7: ' + tree.contains(7));
    // > size: 5
    // > contains 2: true
    // > contains 7: false
    
    // Delete a key
    tree.delete(2);
    console.log('size: ' + tree.size);
    console.log('contains 2: ' + tree.contains(2));
    // > size: 4
    // > contains 2: false
    
    // Construct custom compare AvlTree
    const tree2 = new AvlTree<string, string>(function (a, b) {
      return a.localeCompare(b);
    });
    tree2.insert('a');
    tree2.insert('A');
    tree2.insert('b');
    tree2.insert('B');
    
    // Delete the minimum key
    const minKey = tree2.findMinimum();
    tree2.delete(minKey);
    console.log('minKey: ' + minKey);
    console.log('new minKey: ' + tree2.findMinimum());
    // > min key: 'a'
    // > new min key: 'A'

    Operation time complexity

    Operation Complexity
    contains O(log n)
    delete O(log n)
    findMaximum O(log n)
    findMinimum O(log n)
    get O(log n)
    insert O(log n)
    isEmpty Θ(1)
    size Θ(1)

    Install

    npm i @tyriar/avl-tree

    DownloadsWeekly Downloads

    46

    Version

    2.0.6

    License

    MIT

    Unpacked Size

    39.9 kB

    Total Files

    10

    Last publish

    Collaborators

    • tyriar