Repository files navigation

High performance (binary) tree and sorted map implementation for JavaScript in TypeScript.

• AVL tree implementation
• AVL sorted map implementation
• AVL sorted set implementation
• Red-black tree implementation
• Red-black tree sorted map implementation
• Left-leaning Red-black tree insertion implementation
• Radix tree implementation
• Splay tree implementation
• Various utility methods for binary trees

This package implements the fastest insertion into self-balancing binary tree out of anyNPM package. Both, AVL and Red-black tree insertion implementations ofsonic-forest a fasterthan inserts injs-sdsl implementation.

However, deletions from a binary tree are faster injs-sdsl. But, deletions insonic-forestdelete exactly the node, which contains the key. Unlike, injs-sdsl and all otherbinary tree libraries, where those libraries find the in-order-sucessor or -predecessor, whichis a leaf node, and delete that instead. As such, one can keep pointers tosonic-forest AVLand Red-black tree nodes, and those pointers will stay valid even after deletions.