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

$ curl repovive.com/roadmaps/data-structures/link-cut-trees/rotations

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

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

$ curl repovive.com/roadmaps/data-structures/link-cut-trees/rotations

Repovive

Rotations - Link-Cut Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Rotations

Tree restructuring

Rotation moves a node up while maintaining BST property:

function rotateRight(x)
    // x becomes parent of its former parent
    p := x.parent
    x.parent := p.parent
    p.left := x.right
    if x.right then x.right.parent := p
    x.right := p
    p.parent := x
    // Update grandparent's child pointer

function rotateLeft(x)
    // Mirror of rotateRight
    p := x.parent
    x.parent := p.parent
    p.right := x.left
    if x.left then x.left.parent := p
    x.left := p
    p.parent := x

Rotations are $O(1)$ . The splay operation does $O(\log n)$ rotations amortized.