Rotation Left

In this article and the next we are going to take you to the next level and here under the hood into implementations of balanced pioneer research trees. Now frankly when any great details of all balance binary research tree implementations get pretty complicated and if you really want to understand them at a fine grain level there is no substitute for reading an advanced logarithms textbook that includes coverage of the topic and/or studying open source Implementations of these data structures. I don't see the point of regurgitating all of those details here. What I do see the point in doing, is giving you the gist of some of the key ideas in these implementations. In this article  I want to focus on a key primitive, that of rotations which is common to All balanced by the of limitations. Whether is red, black trees, EVL trees, B or B+ trees, whatever all of them use rotations. In the next  article we'll talk a little bit more about the details of red, black trees in particular. So, what is the points behind these

magically rotation operations? Well the goal is to do just constant work, just re-wire a few pointers, and yet locally re-balance a search tree, without violating the search tree properties/g Property. So there are two flavors of rotations, left rotations and right rotations. In either case, when you invoke a rotation it's on a parent child pair, in a search tree. If it's a right child of the parent, then you use a left rotation. We'll discuss that on this slide. And a right rotation is, in some sense, an inverse operation which you use when you have a left child of the parent. So what's the generic picture look like when you have a node x in a search tree and it has some right child y? Well x, in general, might have some parents. x might also have some left subtree. Let's call that left subtree of x, A. It could, of course, be And then Y has it's 2 subtrees, lets call the left subtree of Y B and the right subtree C. It's going to be very important that rotations preserve the search tree property so to see why that's true lets just be clear on exactly which elements are bigger then which other elements in this picture. So first of all Y being a right child of X, Y's going to be bigger than x. Now all of the keys which line the subtree a because they're to the left of x these keys are going to be even smaller than x. By the same token anything in the subtree capital c, that's to the right of y so all that stuff's going to be even bigger than y. What about sub tree capital B? What about the nodes in there? Well, on the one hand, all of these are in x's right sub tree, right? To get to any node in B, you go through x and then you follow the right child to y. So that means everything is B is bigger than x, yet, at the same time, it's all in the left sub tree of y so these are all Things smaller than y. Summarizing all of the nodes in b have keys strictly in between x and y. So now that we're clear on how all of these search keys in the different parts of this picture relate to each other, I can describe the point of a left rotation. Fundamentally the goal is to invert the relationship. Between the nodes x and y. Currently x is the parent and y is the child. We want to rewire a few pointers so that y is now the parent and x is the child. Now what's cool is given that is our goal is pretty much a unique way to put all these pieces back together to accomplish it. So lets just follow our nose. So remember the goal Y should be the parent and X should be the child. Well, X is less then And why and there's nothing we can do about that. So if x is going to be a child of y, its got to the left child. So your first question might be well what happened that x is parent. So x use to have some parent lets call it p and x's new parent is y. Similarly y used to have parent x and there's a question what should y new parent be? Well y is just going to inherit x's old parent p. SO this change has no bearing for the search tree property. Either of this collection of nodes was P's left sub tree, in that case all these nodes were less than P, or this tree was P's right sub tree which in that case all of these are bigger than P, but P can really care less , which of X or Y is it's direct descendant. Now lets move on to thinking about how...what we should do with the sub-trees A, B and C. So, we have 3 sub-trees we need to re-assemble into this picture, and fortunately we have 3 slots available. X has both of its child pointers available and Y has its right child available. So what Can we put where? Well, a, is the sub tree of stuff which is less than both x and y. So, that should sensibly be x's left child. That's exactly as it was before. By the same token, capital C is the stuff bigger than both x and y, so that should be, y, the bigger nodes child, right child just as, As before. And what's more interesting is what happens to subtree capital B. So B used to be Y's left child but that can't happen anymore, 'cause now X is Y's left child. So, the only hope is to slot capital B into the only space we have for it, X's right child. Fortunately for us this actually works, sliding B into the only open space we have for it. X's right child does indeed preserve the switch tree property. Recall we notice that every key in capital B is strictly between X and Y, therefore it better be and X's right sub tree and it better be in Y's right sub tree, but it is, that's exactly where we put it. So that's a left rotation, but if you understand a left rotation then you understand a right rotation as well. but not now rotation for the next article.