Balanced Trees and Ordered Sets

// Lift node's left child into its place and return it: its right subtree moves across.
TreeNode* rotateRight(TreeNode* node) {
    TreeNode* top = node->left;
    node->left = top->right;                 // between top and node, so it stays between them
    top->right = node;
    return top;
}

// The mirror: lift node's right child.
TreeNode* rotateLeft(TreeNode* node) {
    TreeNode* top = node->right;
    node->right = top->left;
    top->left = node;
    return top;
}

def rotate_right(node):
    """Lift node's left child into its place and return it: its right subtree moves across."""
    top = node.left
    node.left = top.right                    # between top and node, so it stays between them
    top.right = node
    return top


def rotate_left(node):
    """The mirror: lift node's right child."""
    top = node.right
    node.right = top.left
    top.left = node
    return top

// Lift node's left child into its place and return it: its right subtree moves across.
static TreeNode rotateRight(TreeNode node) {
    TreeNode top = node.left;
    node.left = top.right;                   // between top and node, so it stays between them
    top.right = node;
    return top;
}

// The mirror: lift node's right child.
static TreeNode rotateLeft(TreeNode node) {
    TreeNode top = node.right;
    node.right = top.left;
    top.left = node;
    return top;
}

// Lift node's left child into its place and return it: its right subtree moves across.
function rotateRight(node) {
    const top = node.left;
    node.left = top.right;                   // between top and node, so it stays between them
    top.right = node;
    return top;
}

// The mirror: lift node's right child.
function rotateLeft(node) {
    const top = node.right;
    node.right = top.left;
    top.left = node;
    return top;
}

Inserting 1 to 7 into an AVL tree — Indigo is the value just inserted and orange the node out of balance; in a rotation, green rises over amber.

// The largest key at or below x, or "none": the one just before the first key above x.
string floorOf(const set<int>& keys, int x) {
    auto it = keys.upper_bound(x);           // the first key bigger than x
    return it == keys.begin() ? "none" : to_string(*prev(it));
}

// The smallest key at or above x, or "none".
string ceilingOf(const set<int>& keys, int x) {
    auto it = keys.lower_bound(x);           // the first key not below x
    return it == keys.end() ? "none" : to_string(*it);
}

from bisect import bisect_left, bisect_right


def floor_of(keys, x):
    """The largest of the sorted keys at or below x, or None."""
    i = bisect_right(keys, x)                # keys[:i] are all at or below x
    return keys[i - 1] if i else None


def ceiling_of(keys, x):
    """The smallest of the sorted keys at or above x, or None."""
    i = bisect_left(keys, x)                 # keys[i:] are all at or above x
    return keys[i] if i < len(keys) else None

// TreeSet answers both directly; each returns null when there is no such key.
static String floorOf(TreeSet<Integer> keys, int x) {
    Integer f = keys.floor(x);
    return f == null ? "none" : f.toString();
}

static String ceilingOf(TreeSet<Integer> keys, int x) {
    Integer c = keys.ceiling(x);
    return c == null ? "none" : c.toString();
}

// No sorted set is built in, so binary-search a sorted array. lo ends at the first key above x.
function floorOf(keys, x) {
    let lo = 0, hi = keys.length;
    while (lo < hi) {
        const mid = (lo + hi) >> 1;
        if (keys[mid] <= x) lo = mid + 1; else hi = mid;
    }
    return lo > 0 ? keys[lo - 1] : "none";
}

// Here lo ends at the first key at or above x.
function ceilingOf(keys, x) {
    let lo = 0, hi = keys.length;
    while (lo < hi) {
        const mid = (lo + hi) >> 1;
        if (keys[mid] < x) lo = mid + 1; else hi = mid;
    }
    return lo < keys.length ? keys[lo] : "none";
}

class MyCalendar {
    map<int, int> booked;                    // start → end, sorted by start
public:
    MyCalendar() {}

    bool book(int start, int end) {
        auto after = booked.upper_bound(start);                           // the first booking starting after start
        if (after != booked.end() && after->first < end) return false;
        if (after != booked.begin() && prev(after)->second > start) return false;   // the last one at or before start
        booked[start] = end;
        return true;
    }
};

from bisect import bisect_right

class MyCalendar:
    def __init__(self):
        self.starts = []                     # the bookings' starts, sorted
        self.ends = []                       # each start's end, at the same index

    def book(self, start: int, end: int) -> bool:
        i = bisect_right(self.starts, start)          # the bookings before i start at or before start
        if i > 0 and self.ends[i - 1] > start:        # the floor still runs at start
            return False
        if i < len(self.starts) and self.starts[i] < end:   # the ceiling begins before end
            return False
        self.starts.insert(i, start)                  # O(n): the list shifts
        self.ends.insert(i, end)
        return True

class MyCalendar {
    private final TreeMap<Integer, Integer> booked = new TreeMap<>();    // start → end, sorted by start

    public MyCalendar() {}

    public boolean book(int start, int end) {
        Map.Entry<Integer, Integer> floor = booked.floorEntry(start);     // the last booking starting at or before start
        if (floor != null && floor.getValue() > start) return false;
        Integer ceiling = booked.ceilingKey(start);                       // the first booking starting at or after start
        if (ceiling != null && ceiling < end) return false;
        booked.put(start, end);
        return true;
    }
}

var MyCalendar = function() {
    this.starts = [];                        // the bookings' starts, sorted
    this.ends = [];                          // each start's end, at the same index
};

MyCalendar.prototype.book = function(start, end) {
    let lo = 0, hi = this.starts.length;     // the first booking that starts after start
    while (lo < hi) {
        const mid = (lo + hi) >> 1;
        if (this.starts[mid] <= start) lo = mid + 1; else hi = mid;
    }
    if (lo > 0 && this.ends[lo - 1] > start) return false;                 // the floor still runs at start
    if (lo < this.starts.length && this.starts[lo] < end) return false;    // the ceiling begins before end
    this.starts.splice(lo, 0, start);        // O(n): the array shifts
    this.ends.splice(lo, 0, end);
    return true;
};

static int floorOf(TreeSet<Integer> keys, int x) {
    int f = keys.floor(x);                   // null when nothing is at or below x
    return f;
}

int floorOf(const set<int>& keys, int x) {
    return *keys.lower_bound(x);             // the first key NOT BELOW x: that's the ceiling
}

from bisect import bisect_left

def floor_of(keys, x):
    i = bisect_left(keys, x)                 # stops before a key equal to x
    return keys[i - 1] if i else None

const keys = [10, 9, 100, 25];
keys.sort();                                 // compares them as strings
console.log(keys.join(" "));