@b08/aa-tree, seeded from @b08/library-seed, library type: feature

implementation of self balancing tree using aa-tree algorithm

StackTree

Class that allows tree-style insertion, and stack-style retrieval, or queue-style. Objects inserted into the tree should have a key to be sorted by. Constructor receives lambda parameter to retrieve a key of an object.

const tree = new StackTree((item: MyType) => item.key);

Tree allows to insert several items by the same key.

tree.add({ key: 1, value: "a1" });
tree.add({ key: 2, value: "a2" });
tree.add({ key: 1, value: "a3" });

Items can be retrieved by maximum key using method pop or by minimum key using method shift.

const result1 = tree.pop(); // { key: 2, value: "a2" }
const result2 = tree.pop(); // { key: 1, value: "a3" }
const result3 = tree.pop(); // { key: 1, value: "a1" }

There are also methods to retrieve all items having minimum or maximum key

const results = tree.shiftGroup(); 
// [{ key: 1, value: "a1" }, { key: 1, value: "a3" }]

If tree is empty, all of those methods will return null