#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/interval-trees/maintaining-maxhigh

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/interval-trees/maintaining-maxhigh

Repovive

Maintaining maxHigh - Interval Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Maintaining maxHigh

Update during operations

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)$ .