Implement a BST ordered set with comparator and ceiling lookups
A calendar app needs to answer questions like “what is the next free slot at or after 14:30?” and “what was the last booking before noon?” while bookings are added and cancelled all day. An ordered set backed by a binary search tree answers both in time proportional to the tree’s height.
Implement a class BinarySearchTree that stores unique values in sorted order.
const tree = new BinarySearchTree(compare?);
tree.insert(value) // => true if added, false if an equal value already exists
tree.has(value) // => boolean
tree.delete(value) // => true if removed, false if not found
tree.size() // => number of stored values
tree.min() // => smallest value, or undefined when empty
tree.max() // => largest value, or undefined when empty
tree.floor(value) // => largest stored value <= value, or undefined
tree.ceiling(value) // => smallest stored value >= value, or undefined
tree.toArray() // => new array of all values in ascending order
tree.height() // => number of nodes on the longest root-to-leaf path (0 when empty)
compare(a, b) returns a negative number when a comes first, a positive number when b comes first, and 0 when they are equal. “Smaller”, “larger”, and “ascending” all follow this order.a < b ? -1 : a > b ? 1 : 0. Numbers therefore sort numerically (9 < 10 < 100), and strings sort by code unit.compare returns 0, even if they are different objects. has, delete, floor, and ceiling use the comparator, not ===.height() depends on insertion order.toArray() returns a new array each time. Changing it does not affect the tree.const slots = new BinarySearchTree();
[900, 1430, 1100, 1600, 1000].forEach((time) => slots.insert(time));
slots.insert(1100); // => false (already booked)
slots.toArray(); // => [900, 1000, 1100, 1430, 1600]
slots.ceiling(1200); // => 1430
slots.floor(1200); // => 1100
slots.floor(800); // => undefined
slots.height(); // => 4 (see the tree below)
slots.delete(1430); // => true (two children: replaced by 1600)
slots.toArray(); // => [900, 1000, 1100, 1600]
slots.size(); // => 4
For the example above, the tree after the five inserts is:
900
\
1430
/ \
1100 1600
/
1000
The longest path is 900 → 1430 → 1100 → 1000, so height() returns 4.