Operation for Rebalancing: Tree Rotation
In tree below: t1 < n2 < t2 < n1 < t3
![[Diagram:Pic/left-right-rotation.png]](Pic/left-right-rotation.png)
Method for rotating tree T right:
- N1 is current root; N2 is root of N1's left subtree
- N1 gets new left subtree, which is N2's right subtree
- N1 becomes root of N2's new right subtree
- N2 becomes new root
Left rotation: swap left/right in the above.
Cost of tree rotation: O(1)
| ![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}