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.

$\endgroup$
  • $\begingroup$ Oh so the example that I provided isn't rotatable? $\endgroup$ – Does it matter 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

Not the answer you're looking for? Browse other questions tagged or ask your own question.