Tree Rotation (cont)
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}