Balanced BSTs (cont)
To assist with rebalancing, we consider new operations:
Left rotation
- move right child to root; rearrange links to retain order
Right rotation
- move left child to root; rearrange links to retain order
Insertion at root
- each new item is added as the new root node
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}