0:00

In this video 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 first video I want to focus on a

Â key primitive, that of rotations which is common to All balanced by the [INAUDIBLE]

Â of limitations. Whether is red, black trees, EVL trees, B

Â or B+ trees, whatever all of them use rotations.

Â In the next video 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.

Â 2:25

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.

Â 3:39

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 sub 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.

Â 5:08

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.

Â 6:00

So that's a left rotation, but if you understand a left rotation then you

Â understand a right rotation as well. because a right rotation is just the

Â inverse operation. So that's when you take a parent child

Â pair, where the child is the left child of the parent, and now you again want to

Â invert the relationship. You want to make the old child the new

Â parent and the old parent the new child. And once again given this goal there's

Â really a unique way to reassemble the components of this picture so that the

Â goal's accomplished, so that y is now the parent of x.

Â So what are the laudable properties of rotations? Well first of all I hope it's

Â clear that they can be implemented. In a constant time or you were doing a

Â rewiring a constant number of pointers. Further more as have discussed they

Â preserve the search tree property. So these nice properties are what make

Â rotations the ubiquitous primitive common to all balanced search tree

Â implementations. So this of course, is not the whole

Â story. In a complete specification of a balanced

Â search tree implementation, you have to say exactly when and how you deploy these

Â rotations. You'll get a small taste of that in the

Â next video but if you really want to understand it in more depth, I again

Â encourage you to check out either a comprehensive Data structures textbook.

Â Check out a number of balance search tree demonstrations, which are readily

Â available on the web. Or have a peek at an open source

Â implementation of one of these data structures.

Â