AlgoScope

Left-Right and Right-Left Rotations

A zig-zag needs two rotations. Straighten the child first, then rotate the node.

Tree algorithms, algorithm, advanced
Node 30 has balance 1. It is fine.1030current
Node 30 has balance 1. It is fine.1030current

AVL Tree: Left-right needs two rotations

Decision, step 6 of 13

At 30: left height 1, right height 0, balance 1. Within one, so it stays.

How avl tree works

Cost

Best
O(1)
Average
O(1)
Worst
O(1)
Space
O(1)

Before this

Variants

  • Left-Right RotationLeft rotate the left child
  • Right-Left RotationRight rotate the right child

Leads to

Topics that need this one first.

Taught by the same lesson

AVL Tree covers these too, in the same run.