Maintaining maxHigh

After any insertion or deletion, update maxHigh bottom-up:

function updateMax(node)
    if node is null then
        return
    node.maxHigh := node.interval.high
    if node.left is not null then
        node.maxHigh := max(node.maxHigh, node.left.maxHigh)
    if node.right is not null then
        node.maxHigh := max(node.maxHigh, node.right.maxHigh)

On insertion, update maxHigh along the path from new node to root.

On deletion, update maxHigh along the path from deleted node's parent to root.

This adds $O(h)$ overhead where $h$ is tree height. With a balanced BST, that's $O(\log n)$.