Splay Tree Set

Description

A splay tree set is a self-balancing binary search tree that does not allow duplicate elements. The value of a splay tree is in it's amortized O(log n) for all insert, delete min/max, and find min/max operations.

Usage

import { SplayTreeSet } from 'gis-tools-ts';

const tree = new SplayTreeSet<number>([], (a, b) => a - b);

// If the element already exists, the existing element will be returned otherwise
// the new element will be both added and returned
let element = tree.add(1);
tree.add(2);

console.log(tree.length); // 2
// Get first and last elements
let firstElement = tree.first(); // 1
let lastElement = tree.last(); // 2
// check if a value exists
console.log(tree.has(1)); // true
// look for a value right before one provided
console.log(tree.lastBefore(2)); // 1
// look for a value right after one provided
console.log(tree.firstAfter(1)); // 2
Copy

Links

• https://en.wikipedia.org/wiki/Splay_tree
• Splay Tree Visualizer
• Visualizer Source Code