0:02

Hello everybody, welcome back.

Â Last time, we talked about AVL trees and

Â showed that they can perform your basic binary search tree operations.

Â But now we're going to introduce a couple of new operations and

Â talk about how to implement them.

Â So, another useful feature of binary search trees is in addition to being

Â able to search them, there's also a bunch of sort of interesting ways that you could

Â recombine them.

Â 0:39

So, let's start with merge.

Â And the idea is, in general, if you have two sorted lists and

Â want to combined them into sort of a single sorted list.

Â This is actually pretty slow, it's going to take O(n) time,

Â because you sort of need to figure out how the lists interweave with each other.

Â This is the thing you do in merge sort.

Â 0:57

However, there is a case where you can merge them a lot faster.

Â And that's the case where they're separated from each other,

Â where they're sort of, one's on one side, one's on the other side.

Â And so, this is the case that merge is going to work with.

Â So you're giving two trees, R1 and R2, or the roots of these trees.

Â And they're going to need to have the property that all the keys in R1's tree

Â are smaller than all of the keys in R2's tree.

Â 1:42

The answer is that only A can because

Â all of the elements of A are less than all of the elements of the guy above.

Â B has this problem that it's got a 9, and 9 is between 8 and

Â 10 so it can't really be separated from them.

Â And C has the problem that it has both 2, which is smaller than everything above,

Â and 12 which is bigger than everything above.

Â So, A is the only guy that actually works here.

Â Okay, so how do you do this merge operation?

Â 2:30

So, the implementation, we'll call this function MergeWithRoot,

Â is you let R1 be the left child of T, R2 be the right child of T.

Â Let T be the parents of these two.

Â If you need to do things involving restoring heights,

Â you adjust those as appropriate, and then you return T.

Â 2:52

The problem is, well, what if we're not given this extra node?

Â Then there's actually a pretty simple solution.

Â You find the largest element, of say, the left subtree.

Â You remove that, and then turn it into the root of the new guy.

Â And that works.

Â So now if we want to merge R1 and

Â R2, we're going to find the largest element of R1, call that T.

Â You're going to delete T from its subtree, and then you're going to merge with root.

Â And that works.

Â The run time's a little bit worse.

Â You have to spend O of the height time to find this node T, but

Â other than that it's pretty efficient.

Â 3:40

That's all there is to it.

Â Now if we didn't care about balance,

Â that would be all we'd have to say about this operation.

Â Unfortunately, this merge operation doesn't preserve balance properties.

Â And the problem is that, well, the two trees,

Â you didn't really touch them very much, so they stay balanced.

Â But when you stick them both together under the same root,

Â well, if one tree is much, much bigger than the other, suddenly the root is very,

Â very unbalanced, and this is a problem.

Â 4:12

So we need a way to fix this.

Â And there's actually a not very difficult way to do that.

Â The idea is that we can't merge the, say,

Â left subtree with the right subtree because the left one is way too big.

Â 4:37

And so what we're going to do is, we're going to sort of climb down the sort of

Â right edge of the bigger tree until we find a sub tree of

Â the right height that we can merge with our guy on the other side.

Â Okay, so how do we implement this?

Â AVLTreeMergeWithRoot.

Â 4:55

What we're going to do is, if the heights of the two trees differ by at most 1,

Â we can just merge with root as before.

Â We then figure out what the height of T needs to be and return it.

Â That simple.

Â Otherwise though, what happens if say R1's height is bigger than R2's height?

Â 5:14

Well, what we want to do is we want to step down to instead of merging R1 with

Â R2, we merge R1's right child with R2.

Â So, we use merge with root to merge the right child with R2 at this T,

Â and we get some new tree with root R prime.

Â R prime we set back to be the right child of R1,

Â and similarly set R1 to be the parent.

Â And then we need to rebalance this at R1 because

Â things might be off by a little bit, but it turns out not more than about one.

Â We knew how to deal with that with our old rebalance operation.

Â And than we return the root of the tree.

Â 6:01

Okay, so, let's analyze this.

Â Every step we take down the side of the tree decreases the height

Â difference by either 1 or 2.

Â So we're just going to keep decreasing the height difference until we're off by

Â at most 1.

Â Then we merge, and we soon have to go back up the chain.

Â But the amount of time this takes isn't the depth of the tree,

Â it's sort of the number of steps we need to take down the side.

Â And that's approximately the difference in the two heights.

Â And this will actualy be important in a bit.

Â 6:34

Okay, so that was the merge operation.

Â Next, we're going to talk about sort of the opposite operation, split.

Â Merge takes two trees and turns them into one.

Â Split breaks one tree into two.

Â 6:45

What you do is you pick an element, say 6, and

Â then you've got the tree consisting of all the elements less than 6, and

Â then another one from all the elements bigger than 6.

Â So split should take the root of a tree and the key x, and the output should be

Â two different trees, one with all the elements less than x in your tree, and

Â one with all of the elements bigger than x.

Â Okay now, the idea is actually not so hard.

Â What we're going to do is we're going to search for

Â x, and then the search path, well it's got a few nodes on the path.

Â And then it has a bunch of trees hanging off to the left of the path.

Â These things are all going to be smaller than x.

Â And it's going to have a bunch of trees hanging off to the right that are all

Â going to be bigger than x.

Â And so all we have to do is take these trees that are smaller than x,

Â merge them all together, take these things bigger than x,

Â merge them all together, and then we have two trees.

Â So let's see how this works.

Â So we're going to do this recursively.

Â We're going to split at R, at this point x.

Â If our root is null, if we just have the null tree,

Â we just return a pair of null vectors, whatever.

Â Next if x is less than the key at the root,

Â what that means is that everything on the right is bigger than x.

Â That's sort of all on the right.

Â But the left side of the root, we need to split that in two.

Â So we're going to recursively run split on R.Left, and

Â that gives us two trees, R1 and R2.

Â Now R1 is actually everything in the whole tree that's smaller than x.

Â That half is done, but

Â R2 needs to be combined with the whole right subtree of our original tree.

Â 8:52

Okay, so the first thing to note is that if we,

Â instead of just doing a MergeWithRoot, we used AVLMergeWithRoot.

Â This insures that the two trees we produce are both balanced, which is good.

Â 9:13

So we have to look at the difference between the biggest type and

Â the next biggest and the next biggest and the one after that and so on.

Â This sum actually telescopes, and the total run time is O of the maximum height

Â of one of these trees we're trying to merge, which is just O(log(n)).

Â And so we've got these two operation,

Â merge combines trees, split breaks them in two, and

Â both operations can be implemented in O(log(n)) time using AVL trees.

Â