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.