Talk:Tree rotation

New Caption Doesn't Match New Illustration

First off I want to say that I like the new illustration. It's much prettier and more informative than the simple ascii art it replaced. The caption doesn't seem to fit it according to my definition, however. I would say that the right rotation is performed with 'Q' as the root and, thus, the rotation is on, or rooted at, 'Q'. The left rotation is the one rooted at 'P'. Is this a mistake or merely a convention unfamiliar to me?

--Waylonflinn 18:59, 28 August 2006 (UTC)

Uh, the ascii art was more easily understood. The new illustration is crap in comparison. As a matter of fact, now all the images on this page suffer from invalid binary trees as a starting point. They're either changing Roman/Greek alphabets or sticking with Roman but not in order or not giving nodes any value for comparison. It's difficult to understand a tree rotation, it's even more difficult when working with invalid trees.

AlwaysAngry (talk) 11:27, 3 October 2014 (UTC)

Python code hard to read

The python code is very hard to read. A simplification would be expedient in this case.

I agree, it's quite obscure to anyone not familiar with tuples. That said, the diagrams seem clear enough to enable implementation in any language. Deco 05:17, 29 July 2005 (UTC)

I'm afraid that Python code is my fault, from 2001. Here's a shorter version, but I'm not sure what makes either version harder to read:

   def right_rotation(((A, B, C), D, E)):
       return (A, B, (C, D, E))

Apparently I'm now so indoctrinated with Python that I have forgotten what it was like to not know it! How about this?

   def right_rotation(node):
       delendum = node.left_child
       new_right_child = binary_tree_node(left_child=delendum.right_child, 
           key=node.key, right_child=node.right_child)
       return binary_tree_node(left_child=delendum.left_child, 
           key=delendum.key, right_child=new_right_child)

A version with shorter variable names:

   def right_rotation(N):
       D = N.L
       R = node(L=D.R, K=N.K, R=N.R)
       return node(L=D.L, K=D.K, R=R)

My point, by the way, is not to defend Python as a notation, but to figure out what would be an improvement.

-- Kragen

• imho the python code is quite readable and i am only a bit familiar with python by having played with it for 2 days. i also think familarity with tuples can be expected from readers interested in trees. but another thing: although it is more or less obvious it would be nice to have left_rotation(treenode) also for completeness. -- wizzar 22:45, 18 December 2005 (UTC)

I think what we should shoot for is consistency between this article, Binary tree, Red-Black tree and related articles.

--Waylonflinn 20:57, 28 August 2006 (UTC)

Thanks Waylonflinn for that, and between, i agree with the change in the explanation, which slightly misleads and needs a fix. And, how about switching to C for the example rather than in python?

--Ramasamy 18:00, 01 September 2006 (IST)

Left Right confusion

I'm coming across sources which say that the direction of a rotation is not the side upon which the nodes are being shifted, as illustrated on this page, but depends on which child of the node being rotated is going to be the parent. These are 2 completely different views. Who is wrong?

Isn't the psudeo code wrong?

Another view on Rotation

At first I was a bit confused by this article, since a CS article I've read defines rotation with only one parameter:

"If x is a son of y, then rotate(x) moves x up and y down and changes a few pointers"

Maybe not the most accurate specification, but what the function actually does, is to make a left- or right-rotation of y depending on whether x is the left or right child of y. What I am getting at is that maybe this "view" could be touched in this article as well?

--Klokbaske 09:46, 7 April 2009 (UTC)

Directions, directions, ...

"direction of a rotation depends on the side which the tree nodes are shifted upon ... This article takes the approach of the side where the nodes get shifted to" upon == to? OK.

"When a subtree is rotated, the subtree side upon which it is rotated increases its height by one while the other subtree increases its height"

That doesn't match. The right subtree gets larger in a right rotation, according to the intro and the illustration above.

I think the whole article needs straightening out.

Długosz (talk) 22:18, 9 September 2009 (UTC)

I addressed the issue.82.114.35.223 (talk) 16:37, 30 September 2009 (UTC)

Possible inaccuracy

The article says: "another way to think of it is that the order that the leaves would be visited in a depth first search must be the same after the operation as before"

Correct me if I'm wrong, but I believe the order of visiting the leaves in a DFS after the rotation will change, but the in-order traversal will remain the same.

DFS traversal before right rotation: QPABC

DFS traversal after right rotation: PAQBC

In-order traversal before right rotation:APBQC

In-order traversal after right rotation:APBQC

--Explorer512 (talk) 07:01, 24 November 2012 (UTC)