1
$\begingroup$

enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ Read a textbook. Look at the graphics. $\endgroup$ – Raphael Mar 20 '18 at 15:53
3
$\begingroup$

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.

enter image description here

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Oh so the example that I provided isn't rotatable? $\endgroup$ – user82869 Mar 21 '18 at 7:11
  • $\begingroup$ Just look at Wikipedia. It has many illustrations that describe the process. $\endgroup$ – Hendrik Jan Mar 21 '18 at 12:17
  • 1
    $\begingroup$ I downvoted this answer because it doesn't directly address the OP's problem and because you're linking to a Wikipedia page instead of attempting to provide a full explanation here, which would enrich the website. $\endgroup$ – nbro Mar 29 '18 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy