As a example I have use RIGHT-ROTATE to present the steps of the rotations. LEFT-ROTATE is also semantic.

RIGHT-ROTATE(T, x)

- y = x.left // set y
- x.left = y.right // turn y’s right sub tree into x’s left sub tree
- if y.right ≠ NULL
- y.right.parent = x
- y.parent = x.parent // link x’s parent to y
- if x.parent == NULL
- T.root = y
- else if x == x.parent.left
- x.parent.left = y
- else
- x.parent.right = y
- y.right = x // put x on y’s right
- x.parent = y

Assumptions

- Assume that the n items are distinct.

### Like this:

Like Loading...

*Related*

where is explanation