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.