Data Structures19 sections · 729 units
Open in Course

Rotate with Update

Maintaining aggregates

Update aggregates after rotation:

function rotate(x)
    p := x.parent
    g := p.parent

    if x = p.left then
        p.left := x.right
        if x.right then x.right.parent := p
        x.right := p
    else
        p.right := x.left
        if x.left then x.left.parent := p
        x.left := p

    p.parent := x
    x.parent := g

    if g is not null then
        if p = g.left then g.left := x
        else if p = g.right then g.right := x
        // else: p was root of aux tree, x inherits path-parent

    pushUp(p)
    pushUp(x)

function pushUp(x)
    x.subtreeSum := x.value
    x.subtreeSize := 1
    if x.left then
        x.subtreeSum := x.subtreeSum + x.left.subtreeSum
        x.subtreeSize := x.subtreeSize + x.left.subtreeSize
    if x.right then
        x.subtreeSum := x.subtreeSum + x.right.subtreeSum
        x.subtreeSize := x.subtreeSize + x.right.subtreeSize