0
$\begingroup$

I might be asking this question because I lack the basic knowledge of rotations. If that is the case, could you suggest any resources for learning it. But I don't think that I am. Every source that I have checked for tree rotation seems to very hand wave and no proper definition is provided for what it means to rotate a tree.

How do we define a right of left rotation of a binary search tree. I understand how to rotate a binary search tree that was made by adding the nodes as 3, 2, 1. But I don't understand how to rotate a tree which was made by adding nodes as 5, 3, 4.

Is there a formal definition of what a tree rotation is?

asked Aug 31, 2024 at 3:55
$\endgroup$
3
  • 1
    $\begingroup$ What about "a bijection of tree nodes with finite recursion depth"? This paper discusses these transformations in great depth. (No pun intended!) It also includes a rigorous definition of "finite recursion depth". $\endgroup$ Commented Aug 31, 2024 at 4:50
  • $\begingroup$ @Trebor I like that defintion. Thank you! $\endgroup$ Commented Aug 31, 2024 at 5:34
  • $\begingroup$ Is there a problem with the explanation given at wikipedia? There it is explained how a node, its child, and their three subtrees are rearranged. $\endgroup$ Commented Sep 1, 2024 at 10:31

0

Know someone who can answer? Share a link to this question via email, Twitter, or Facebook.

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.