# how does rotation works in AVL trees and what is a good way to understand it?

If we consider this tree with T1 and T2 as subtrees, and we want to rotate on x (rotating the edge between T1 and x), what is the result? how does it work then? Does the x stay in its place and T1 switch with T2? I saw multiple examples online but they had too many nodes and i couldn't really understand the concept of rotating and that's why i chose this simple example so that i (hopefully) can apply it in all other situations.

• Read a textbook. Look at the graphics.
– Raphael
Mar 20 '18 at 15:53

One needs three subtrees to describe rotation, as the operation reconnects the three subtrees of a pair of nodes, one the child of the other. The operation can be seen as a associative property: $$T_1\;p\; (T_2\; q\; T_3) = (T_1\; p\; T_2)\; q\; T_3$$ of the inorder traversal of the nodes in a binary tree.

Both the left and right diagram have the inorder $$\mathrm{in}(T_1)\; p\; \mathrm{in}(T_2) \; q\; \mathrm{in}(T_3)$$, where $$\mathrm{in}(T)$$ is the inorder of subtree $$T$$.

It is pretty well explained at wikipedia Tree rotation, even with animated pictures.

• Oh so the example that I provided isn't rotatable?
– user82869
Mar 21 '18 at 7:11
• Just look at Wikipedia. It has many illustrations that describe the process. Mar 21 '18 at 12:17