Transcript

All right, welcome back to data structures land. Today we continue and complete our segment on binary trees. So this is part two. If you missed part one, go back and watch part one. Last time we talked about binary trees in general. Uh we had uh each node stored an item uh which and also a left pointer and a right pointer to other nodes and a parent pointer to another node. Uh this was an example of a tree. B and C are A's children. A is the parent of B and C and also the root of the entire tree. We defined the height of a node. We didn't use this too much yet, but we're going to use it a lot today.

So remember the height is as drawn in red here. Um height of the node is the length of the longest downward path counting edges. So B for example has a length two path, so we write a two here. You can also think of it as if you just live within the subtree rooted at B, B's subtree. Uh then uh what is the maximum depth of those nodes if you prefer to think about it that way. Either way is fine. Um and in particular we distinguished H, the height of the root node, as the height of the entire tree. And what we achieved last time was basically all of our operations ran in order H time. So um we had subtree insert, subtree delete, subtree first and last.

We could compute the predecessor and successor of a node. All in order H time. So as long as H was small, uh we were happy. Um and remember what does predecessor and successor mean? It's talking about an implicit order in the tree, which is what we call traversal order, which is defined recursively as recursively traverse the left subtree, then output the root, then recursively traverse the right subtree. So in this example, the traversal order is F is the If you go all the way left, that was the first in the traversal order. Uh then we have All right, make some space here. Uh then we have D. Then we have B.

Then we do the right subtree of B, which is E. Then we have the root as we finish the left subtree of the root. So that's A. And then we have C. Okay, so there's an implicit linear order encoded by this tree and the whole point of binary trees is that we can efficiently update the tree uh much faster than we could explicitly write down an order in an array or something like that. So binary trees let us quickly Now quickly is not so quick right now because everything is order H and in the worst case H is linear cuz we could have a tree like this. But today we're going to make we're going to guarantee that H is log N.

And so the goal of today is to take all of these operations that run in order H time and get them to run in order log N time just by modifying the data structure we've already seen. So we've done a lot of the hard work. Just a little bit more work we need to do today in something called AVL trees or height balance. Okay, but before we get there, I want to talk a little bit more at the very end of last lecture we talked about once you have these subtree operations, so I can insert and delete in the subtree. Um how do I actually use that to solve the problems that we care about in this class, which are sequence data structure and set data structure?

So um we talked mostly about the set data structure last time. So in general we're going to define what traversal order we maintain by a binary tree. And so for a set um cuz we're for the set interface we're interested in doing queries like find next and find previous. Given a key, if it's not there, tell me the previous one or the next one. This is something we could do with binary search. And so the the big cool thing that binary trees let us do if we let the traversal order always be uh all of the items stored in increasing key order, then we are effectively maintaining the items in order. In in the traversal order sense.

Again, we're not explicitly maintaining them in order, but up here we're maintaining a tree that represents items in key order. And so this lets us do uh a subtree find operation, which you can easily use to implement find and find previous and so on um as follows. We start at the root of the tree. So we can say node equals root initially. And then we can recursively search for a key K as follows. We check well if the item at the root has a key that's bigger than K. Let me draw a little picture. Uh So we're at some node here. All right, yeah, this is a node. And it has a left subtree and a right subtree and there's some item with some key.

So if the key we're looking for is less than the node's item, that means it's down here in the left subtree. And so we recurse on node.left. If they're equal, that means that this item is the item we're looking for. So we can just return it or the node depending on what you're looking for. And if the key in here is greater than the key we're looking for, then we'll recurse to the right. This, if you think about it a little bit, this is exactly binary search on an array. It just happens to be on a tree instead. If you think of an array 6 7 um like this. Binary What does binary search do? It first looks at the key in the middle.

I'm going to draw that as the root. Uh and then uh it recurses either on the left chunk, which I will draw recursively, or on the right chunk. And so if you happen to have a perfect binary tree like this one, it is simulating exactly uh binary search in this array. But this we're going to be able to maintain dynamically, not perfect anymore, but close. Uh whereas this we could not maintain in sorted order. Okay, so uh this is like a generalization of binary search to work on trees instead of on arrays. And for this reason set binary trees are called binary search trees because they are the tree version of binary search.

So there's many equivalent names. So binary search tree is another name for set binary tree. And the key thing that makes this algorithm work is so-called binary search tree property, which is um all the keys in the left subtree of a node are less than uh the root and all or of that node. And that key that key is less than all the keys in the right subtree. And this is true recursively all the way down. And so that's that's how you prove that this algorithm is correct by this property. Why is this true? Because uh if we can maintain traversal order to be increasing key, then that's exactly what traversal order means.

It tells you all the things in the left subtree come before the root, which come before all the things in the right subtree. So uh this property implies this one. And how do you maintain things in increasing key order? It's pretty easy. Uh if you want to insert an item, where does it belong? Well, you do this search to find where it would belong if it was there. If it's there, you can overwrite the values stored with that key. If it's not, um this search will fall off the tree at some point and that's where you insert your uh a new node in your tree. Okay, that was covered in recitation, so I don't want to dwell on it.

What I want to focus on today is the other application. How do we This is for representing a set, which is relatively easy. Uh a challenge which we sort of set ourselves up for, but we need a little more work, is to make sequence binary trees. So suppose I have a binary tree and what I would like, uh mentioned at the end of last time, is that I want the traversal order of my tree to be the sequence order. The order that I'm trying to represent that's changed by operations like insert at. And so I just like to do the same thing, but now I have to think about how do I do a search, how do I do an insert at, that sort of thing.

And here is an algorithm for what I would like to work, but it's not going to quite work yet. So suppose I give you a subtree so specified by a node. So there's all the descendants of that node. And I'd like to know what is in the traversal order of that subtree, which starts here and ends here and the root will be somewhere in the middle. Give me the ith node. So this if I ask I equals zero, I want to get this leftmost descendant. If I ask for I equals the size of the tree minus one, I want to get the rightmost descendant. That was the first and last in the subtree that we talked about, but we don't We know how to find the first and last, just walk left or walk right, but we don't know how to find the ith node in order H time.

That's the goal right now, not log N. And the idea is well it seems like size matters. Sorry if you heard otherwise. Um So in particular I can't I mentioned size when I was talking about the the last node in the sequence. That the index of that node is size of the subtree minus one. So let's define the size of a node to be uh the number of nodes in its subtree. We're calling that subtree parent node. Okay? Including the node itself. So, if I somehow knew the size, this seems important for understanding indexes. Let's just assume that I knew that magically in constant time. Okay? Uh then, I claim that the size of the left subtree, so why don't I expand this diagram a little bit.

So, we have node as before, but we have a left subtree and a right subtree. So, this node here is node.left, this node here is node.right. They might not exist, but let's ignore those exceptional cases for now. Let's suppose we knew not only the size of node, but we knew the size of node.left. So, that is the size of this tree on the left. I'm going to call that NL. So, let's suppose that there are NL nodes down here. Well, I claim that lets me do the equivalent of a binary search, cuz I'm looking for some index I. And if I is less than NL, then I know that it must be down here. For example, if I equals 0, it's going to be in the left subtree as long as NL is greater than 0.

Right? So, uh that's exactly this check. If I is less than NL, I'm going to recurse to the left. Call subtree at of node.left, {comma} I. That's what's written here. Um if I equals NL, think about it for a second. So, NL is the number of nodes here, and so that means this node has index NL. The index of this node is NL. And so, if I equals the if the one index we're looking for is that one, then we just return this node. We're done. And otherwise, I is greater than NL, and that means that the node we're looking for is in the right subtree cuz it comes after the root. Again, that's what it means.

That's what traversal order means. So, if we define it to be sequence order, uh then we know all the things that come after this node, which is index NL, must be over here. Now, when we recurse down here, our numbering system changes because out in for node, 0 is here, and then for node.right, 0 is here. So, we need to do a little bit of subtraction here, which is when we recurse to the right, we take I minus NL minus 1. Minus NL for these guys, minus 1 for the root node. Um and that will give us the index we're looking for within this subtree. Okay? So, it's My point is this algorithm is basically the same as this algorithm, but this one uses keys cuz we're dealing with a set, and in sets, we assume items have keys.

Over here, we items don't have to have keys. In fact, we're not touching the items at all. We're just asking what is the ith item in my sequence, which is the same thing as what is the ith item in my traversal order, which is the same thing as asking what is the ith node in the traversal order, and this algorithm gives it to you exactly the same way in order H time. Okay? Now, I'm not going to show you all the operations, but you can use subtree at to implement uh get at and set at. You just find the appropriate node and return the item or modify the item. Uh or you can use it to most crucially, you can use it to do insert at and delete at.

This is a new thing we've never been able to do before. Uh what do you do? Just like over here, if I'm trying to insert an item, I search for that item over here. Uh so, if I'm trying to insert at I, for example, I look for I, and then uh uh for insert at I, I want to add a new item just before that one. And conveniently, we already have I didn't mention, but we have a subtree insert we had two versions, before and after. I think we covered after, which is successor, before is predecessor. Uh but we can just call subtree insert before at that node, and boom, we will have added a new item just before it.

Um and great. So, magically, somehow, uh we have inserted in the middle of this sequence, and all of the indices update because I'm not storing indices. Instead, um to search for an item at index I, I'm using the search algorithm. But, there's a problem. What's the problem? This seems a little too good to be true. I insert in the middle of this tree, and then somehow I can magically search and still find the ith item even though all the indices to the right of that item incremented by 1. Almost true. Question answer. Yeah. Cuz we have to update the sizes, right? I didn't say how do I compute the size of the left subtree.

So, that is the next topic. We're almost done. This This will actually work. It's really quite awesome. But, uh for it to work, we need something called subtree augmentation, which I'll talk about generally, and then we'll apply it to size. So, the idea with subtree augmentation is that uh each node in our binary tree uh can store uh constant number of extra fields. Why not? And in particular, if these fields are of a particular type, uh maybe I'll call them properties. I'm going to define a subtree property uh to be something that can be computed from the properties of the node's children. So, I should say this is of a node.

So, children are node.left and node.right. Uh you can also access constant amount of other stuff, for example, the node itself. Uh but the point of a subtree property is it's downward-looking. If I have a node here, and I want to compute some property about it, call it uh we want to store P of the node. And suppose we already know P over here, the property computed for the left subtree or for the left node, and we already know the property for the right node, then uh what I'd like is for this to be computable in constant time. So, I can compute P of this node given P of the left node and P of the right node.

That's a subtree property. Now, in particular, size is a subtree property. Why? Because I can write this kind of recurrence. Uh node.size equals node.left.size. Very tedious to write. Plus node.right.size. Plus 1. Thank you. Size of the sub- of the entire subtree here, called node, um is the size of left subtree plus size of the right subtree plus 1 for that node itself. Okay? So, this is an update rule. Takes constant time to evaluate. It's two additions. Sorry, my T's look kind of like plus signs. Make the pluses a little bigger. Okay? So, we're summing those three things. Boom, we can get node.size.

So, I claim that uh if as long as my property has this feature, I can maintain it dynamically as I'm changing the tree. Okay? Now, this is a little bit of a forward reference cuz we haven't said exactly how we're going to change the tree yet. But, uh question? If node.size is recursive, Yeah. how is it happening in constant time? Wouldn't it have to be in linear time? Uh okay. Why is this Okay, good question. So, one natural way you can think of this as a recursion, which gives you a recursive algorithm. Uh so, I wrote but I didn't write it, but I could have written size of node equals this, size of node.left plus, and that would give you a linear time algorithm to count the size.

And if you don't have any information, that is what you would do, and that would be very painful. So, that would make this algorithm really slow. If I'm calling size as a recursive function, it's bad. Uh what I'm instead doing is storing the sizes on every single node. Okay? And precomputing this. So, in fact, I'm going to define uh size of node in So, this is the definition mathematically, but the algorithm for this function is just going to be return node.size. Okay, so that's constant time. So I the challenge now is I have to keep these sizes up-to-date no matter what I do to the tree. And you could look back at last lecture and see, okay, what were all the changes that I did in a tree?

Uh we only did changes during insert and delete. And I will just claim to you, when we did uh insert and delete, what they ended up doing uh in the end, they add or remove a leaf of the tree. Remember leaf was a node with no children. Um So, let's just think about if I add a new leaf in a tree, here's a tree, suppose I add a leaf here, which subtrees change? Well, which subtrees contain that node? The it it is its own new subtree, then its parent's it's in it's in its parent's subtree and its grandparent's subtree and the overall subtree. Okay, in general, these nodes are called the ancestors of this node that we added.

And those are the ones that update. This subtree over here didn't change. It didn't change size and because it's a subtree property, no subtree property will change over here cuz the subtree was untouched. Okay, so um when I touch this guy, I just have to update the subtree property here, update the subtree property here, update the subtree property here. How many of these are there? Yeah. H. I'll say order H to be safe, but I think it's exactly H. Um So, also when I remove a leaf, the same thing. If I remove this leaf, then the the subtrees that change are exactly its former ancestors. Uh Cool.

So, um we're going to update those order H uh ancestors um in order up the tree. So, what do I mean by update? I mean apply this rule. For sub- for size, it's this rule, but for in general, the subtree property gives me an update rule that takes constant time. And so, I'm going to apply that update rule to this node, which will fix whatever property is stored in there. Maybe there's more than one property. And then I'll apply it to this node and because this is already correct by induction and this is already correct because I didn't touch this subtree, it's unchanged, then I can update the value at this node, the property at this node in constant time.

Then I update this one. And because this one is already correct by induction and this one is already correct cuz this subtree is unchanged, I can update the property correctly here in constant time. Okay, so when I make a change in order H time, cuz I'm making H calls to this constant time algorithm, I can update a constant number of subtree properties. This is very powerful. Data structure augmentation is super useful. You will use it on your problem set. We will use it again today. Let me give you some examples of subtree properties. They could be uh common ones are like the sum or the product or the min or the max or sum of squares or all sorts of things of some feature of every node in subtree.

Okay, in fact, uh subtree size is an example of such a thing. It is the sum over all nodes in the subtree of the value one. Okay, that's another way to say count the number of nodes. Okay, but you could also say, what's the sum of the keys in these nodes? Or you could say, what's the maximum key in these nodes? Or you could say, uh um what is the maximum value in these nodes? You can take any property, it doesn't have to be key, it doesn't have to be anything in particular. This is very powerful. You can take all sums, products and maintain them as long as they're downward looking, as long as you're only thinking about the subtree.

Okay, uh some examples of things you cannot maintain are not a node's index. So, if you get a little bit too excited about augmentation, you might think, oh, I can do everything. Right? I needed to support subtree at or let's just say uh get at globally. I want us to know, what is the ith node in my tree? Well, I'll just use data structure augmentation and store in every node what is its index, zero through n minus one. I can't maintain that efficiently because if I insert at the beginning of my traversal order, then all the indices change. Right? So, that that's an example of a of a edit. So, if I insert a new node over here, so this guy's index was zero, now it's one.

This guy's index was one, now it's two. This was two, now it's three and so on. Every node changes its index. Index is not a subtree property and that's why we can't maintain it. Because it depends on all of the nodes in the tree or it depends on all the nodes to its left, all the predecessors. So, for example, this guy's index depends on how many nodes are over here on the left, which is not in the subtree of that node. So, that's where you have to be careful. Don't use global properties of the tree. You can only use subtree subtree properties. Okay, another example is uh depth. Depth is annoying to maintain, uh but it's not obvious why yet.

We will see that in a moment. Okay. The rest of today is about going from order H to order log n, which is what this slide is showing us. So, at this point, you should believe that we can do all of the sequence data structure operations in order H time, except for build and iterate, which take linear time. Uh and that we can do all of the set operations in order H time, except build and iterate, which take n log n and n respectively. And our goal is to now bound uh H by log n. We know it's possible at some level because there are trees that have logarithmic height. That's like this perfect tree here.

But we also know we have to be careful because there are some bad trees, like this chain. So, um if H equals log n, we call this a balanced binary tree. There are many balanced binary trees in the world, maybe a dozen or two. A lot of different data structures. Question. Hi, so you you said like not to think about things on a global level, but to think of them at a subtree level. Can you explain what that means to Okay, what does it mean for a property to be uh local to a subtree versus global? The best answer is this definition. But that's maybe not the most intuitive definition. This is what I mean, something that can be computed just knowing information about your left and right children.

That is the meaning of subtree property and those are the only things you're allowed to maintain. Cuz those are the only things uh that are easy to update by walking up this path. And the contrast is it a global property like index, I it's global in particular because I can do one change, add one known at node and all of the nodes' properties change. So, that's an extreme example of global. We want this very particular notion of local. Uh because that's what we can actually afford to recompute. Hopefully that clarifies. Yeah. The size doesn't size know log of that. It doesn't have a parent. That's not within the subtree.

You're right that if we added Oh, no, let's Okay, let's think about that. If we added a new parent to the tree, this is not something that we've ever done. Um but even if we did that, which subtrees change? Only this one. Right? This node, it's it's a new totally new subtree, but the subtree of this node is completely unchanged. Cuz subtrees are always downward looking. If I added a new root, um I didn't change any subtrees except for one. So, size is a subtree property. Now, there are I mean, I can completely redraw the tree and that's an operation that requires everything to be recomputed. Okay, so it is limited exactly what I'm allowed to do in the tree.

But I claim everything we'll do last class and today, uh we can afford this augmentation. So, it's a feature, not of all binary trees necessarily, but of the ones that we will cover. Yeah. What is a min? The min doctrine. Binary tree. Yeah. Okay, let's uh this will make a little more sense in a moment when I say what we're actually going to do with trees. We uh we need a new tool for manipulating a tree. What we've done so far, we've done some swapping of items and we did adding and removing a leaf. That's not enough. We're going to need something else to let us guarantee logarithmic height. And that something else is called a rotation.

What does this something else need to do? This is just a tool for rebalancing the tree. So, it should not change the data that's represented by the tree. What is the data represented by the tree? Traversal order. Traversal order is sacrosanct. We're not allowed to touch it. It's already defined two different ways depending on whether you're using a set or sequence. So, we want to modify the tree in a way that doesn't modify the traversal order. So, this we're exploiting redundancy. If you wrote down the traversal order in an array, there's exactly one representation of a given order. But in a tree, there's many representations.

It could be a long line. It could be a balanced thing. They could represent the exact same order on the nodes if you label them right. Okay, in fact, there are exponentially many different representations of the same thing and we're going to exploit that the same order. And define This is just a thing you need to know. We label A X B Y C. You can tell I've drawn this diagram before many, many times. This is a very powerful tool in all tree data structures, which are most of data structures, uh and they are called right rotate of Y and left rotate of X. Uh so, if I have this tree, which I'm just black-boxing some of the subtrees into little triangles, if I have a node and it it has a left child, then I'm allowed to right rotate this edge, which means take this edge and go like this, 90° kind of, uh or you could just think of it as rewriting it this way.

Now, you might also keep in track of the parent pointer. Parent pointer uh moves around. Before this was the parent of Y, now it's the parent of X. Okay? So, we X and Y are switching places, but if we we couldn't just swap these items around because that would change traversal order. In this picture, X comes before Y because X is in the left subtree of Y in traversal order. And over here, now Y is in the right subtree of X, so it comes after X. So, in both cases, X comes before Y. And indeed, in all of these pictures, uh the traversal order I mean, not just for X and Y, but also for A, B, and C, the traversal order is consistent.

It is A uh X B Y C. Where when I write a triangle, I mean recursively the traversal order of all the things in the triangle. So, if you just apply the traversal order algorithm here versus here, you get the same output, which means this these operations preserve traversal order. Great. So, this is a thing that we can do in a tree that won't affect any of the stuff we've done so far. It's a tool that we can use to rebalance. Notice um you know, how deep things are in the tree changes. Our problem with this linear tree is that there's some nodes of linear depth. We want to get rid of those. How?

We could take these edges and start rotating them up. If you look at depths, uh you know, in this picture, A and B are deeper than C. And in this picture, uh B and C are deeper than A. So, you know, there's a trade-off. This one moved up, this one moved down, this one stayed at the same depth. So, hopefully, if if A is too deep and C is too shallow, uh they can trade off like this. Okay, it may sound difficult, but in fact, there's a pretty simple way uh which are called AVL trees uh that maintain balance in a particular way called height balance. This is uh if we take the height of node.left Uh actually, I'd prefer to node.right minus height of node.left So, this thing is called um skew of the node.

I want this to always be -1, 0, or +1. Okay, so this is saying that if I have any node and I look if it's left subtree and its right subtree, I measure their heights. Remember, that's downward distance to maximum distance to a leaf. I measure the height of this tree, maximum height, and I measure the maximum height of this subtree. I want these to be within one of each other. May- Ideally, they're equal. That would be the perfect case, but let's let them differ by one. So, maybe this is K and this is K + 1 or maybe this is K and this is K - 1. What's the height In this picture, what is the height of this node?

It's good practice. K + 2. Good. What's the longest path from this node to a leaf? Well, it could go through this subtree and that would be length K + 1 cuz it's K in here plus one for this edge. Or it could be through here and that's K + 1 + 1. So, the biggest is to go to the right. So, the height If I told you the height of these subtrees, we can derive the height of this node. We're going to use that a lot in a moment. So, first claim is that if I can maintain height balance, then I can uh I will guarantee that H equals log N. So, in other words, height balance implies balance. So, let's prove that first quickly and then the interesting part is how do we actually prove or how do we actually maintain the balance property?

We're going to do that using rotations, but how is a big question. Okay, so why does height balance imply balance? So, uh what this is saying is that all height balanced trees have logarithmic height. So, what I'd like to think about is sort of the least balanced height balanced tree. Uh the least balanced one is going to have every node a mismatch. The the left Let's say the left subtree is shallower than the right subtree by one. And recursively all the way down. So, every node has a a gap here. A uh What do I call it? Uh a skew of one. Okay, which I'm going to write I'm going to introduce some notation.

I'll write a descending rightward arrow if this one is is higher than the left subtree. Uh so, the easy way to think about this is this is sort of the our worst case. This is going to be the the fewest nodes for the maximum depth. Let's just count how many nodes are in this tree. I'm going to write that as a recurrence, um which is the number of nodes in a tree of height H. So, if this whole tree has height H, uh as we said in this picture, if I just subtract two from all these numbers, then this one has height uh H minus two two and this one has height H minus one. Okay, so how many nodes are in here?

Well, this is a recurrence I'm going to write, so this will be N sub H minus two. This will be N sub H minus one. And then I just count how many nodes are in this picture. It is N sub H minus one plus N sub H minus two plus one for this node. Now, you might ask what is N H a recurrence for, uh but it is the number of nodes in this sort of worst case uh for if the worst case has total height H. So, you can also think of it as what is the minimum number of nodes I can have in an AVL tree, which is a height balanced tree, uh that has height H. And a height balanced tree. Okay, so now I just need to solve this recurrence.

This this recurrence look familiar? Ish. It's like Fibonacci numbers. If I remove the plus one, it's Fibonacci. And if you happen to know the Fibonacci numbers grow as like a golden ratio to the end, then we know that this is exponential, which is what we want because if n of h is exponential in h, that means h is logarithmic in n cuz log is inverse of exponential. Okay, but maybe you don't know about Fibonacci numbers and uh so we can still uh easily show that this is exponential as follows. Uh I want to prove that it's at least an exponential because that gives me that h is at most logarithmic.

Um so we need a lower bound. And so we have these two terms which are hard to compare, n sub h minus one and n sub h minus two. It's kind of ugly. Uh but if we're allowed to be sloppy, and we'll see if we're not too sloppy and still get an exponential answer, um let's just make them equal. Uh like so. Um So this is a true statement, in fact strictly greater than. Uh why? Because so I removed the plus one, that should only make something smaller. And um I replaced n sub h minus one with n sub h minus two. Here I'm implicitly using a fact which is obvious by induction that uh this tree on height if I take this tree versus this tree, this one has more nodes than this one.

Right? If I have larger height, this construction is going to build a bigger tree. At least as big. Doesn't need to even need to be strictly bigger. So certainly n sub h minus one is greater than or equal to n sub h minus two. Now this is two times n sub h minus two. And this is an easy recurrence. This is just powers of two, right? I keep multiplying by two and subtracting two from h. So this solves to two to the h over two, maybe with floor or something. Okay, but uh it is I I'm using a base case here which is n sub zero equals one. Uh maybe it's a ceiling then. But the point is this is exponential.

So this implies that the height is always at most two times log n. Uh this two corresponds to this two. If you just invert this formula, this was number of nodes is going to be at least uh two to the h over two. And so h is at most two log n. So it's not log n, that would be perfect, but it's within a factor of two of log n. So AVL trees are always quite balanced. Number of levels is at most double what you need to store n nodes. Great. We're left with the main magic. Not domain magic, that's different. Uh And let's see, we're going to use subtree augmentation. Keep that. Big remaining challenge is how do we maintain this height balance property using rotations?

We have all the ingredients lined up for us. We have subtree augmentation. What does that let me do? It's relevant to AVL trees. Well, it lets me store height. Right? I I need to be able to compute the height of a node. That in general it takes linear time cuz I have to look at all the downward paths, all the leaves within that subtree. But height is a subtree property. So uh yes, height. Why? Because uh let me just write it here. node.height equals one plus max of node.left.height and node.right.height. end of max. Put this in a box. This equation, or I guess it's an assignment operation. This is a one.

Is the thing we've been doing over and over? When I said what is the height of this node, you just figured that out, right? You took the height of the left subtree, maxed with the height of the right subtree, and added one for to account for these edges. Okay, so this is a general update rule. It matches this subtree property pattern. If I have the property of left and right, I can compute it for a node. And this takes constant time to do, and so it's a subtree property and so I can maintain through all the things I'm doing the height of every node. Oh, by the way, whenever I do a rotation, I'm also going to have to update my subtree properties.

When I rotate this edge, A does not change, B does not change, C does not change, so that's good. But X's subtree changes. It now has Y, it didn't before. So we're going to have to also uh update the augmentation here. Why? And we're going to have to update the augmentation in X. Uh and we're going to have to update the augmentation of all of the ancestors of X eventually. Um So rotation is locally just changing a constant number of pointers, so I usually think of rotations as taking constant time. Uh but eventually we will have to do This is constant time locally. Um but we will need to update uh h ancestors in order to store all of keep all of our augmentations up to date.

Okay, we'll worry about that later. All right, so great. Now we have the height of all the nodes, we can compute the skew skew of all the nodes. Cool. Um we have this rotation operation, and we want to maintain uh this height balance property. Height of left node left and right of every node is within is plus or minus one or zero. Um cool. So uh I said over here somewhere whenever we So the only things that change the tree are when we insert or delete a new node. And it and the way that we implemented those so far is to add or remove a leaf. So we should still be thinking about adding or removing a leaf.

The problem is when I add a new leaf, now maybe this tree is higher than it used to be. So um some node here may no longer be height balanced. But because height is a subtree property, the only nodes we need to check are the ones up this ancestor path. So and there's only log n of them because now height is log n. That's what we just proved. As long as we have this property. Now we right now don't have it for like maybe these few nodes, but it will be it was log n before, it's at most log n two log n plus one right now cuz we just added a node. So what I want to do is check all of these ancestor nodes in sequence from bottom up and find one that's out of balance.

So let's take the um lowest uh out of balance node. And I'm going to call that X. Now because we just inserted or deleted a single leaf, it's only out of balance by one. Right? Cuz we only changed height at one height went up by one or one height went down by one. And before all of our skews were plus or minus one or zero, so now it's going the bad case is when it's plus or minus two. If it happens to still be in this range for all the nodes, we're happy. But if it's outside this range, it's only going to be out by one. Uh so this means the skew is in plus two or minus two. And let's say that it's two by symmetry.

So um my picture is I'm going to draw double right arrow to say that this subtree is two higher than this subtree. Okay, so that's bad and we want to fix it. The obvious thing to do is to rotate this edge cuz that'll make this uh this is two ha this is too high and this is too low. So if we rotate, this should go down by one and this should go up by one. And that works most of the time. So case one is that skew of Y. What is Y? I want Y to be the right child of X. Because we have positive skew, we know there is a right child. Now uh because this was the lowest bad node, we know that Y is actually good.

It's either right heavy or even the two subtrees have the same height or left heavy. The easy cases uh are when skew of Y is either one or zero. Which I will draw. All right, uh so double right arrow, let's say single right arrow. So, this uh I'm just going to add some labels here to make this picture consistent. Uh K + 1 K + 2. I'm writing the heights. So, this is an example where C is high is taller than B. Uh B A is and B are the same height. And then if you compute the heights up here, indeed uh this one is right leaning, this one is doubly right leaning. Cuz this one has height K + 1, this one has height K - 1.

That's bad. But if we do this right rotation on X, we get exactly what we want. So, I'm just going to copy the labels on ABC. We have K - 1, K - 1, and K. And then we compute. That means this guy has height K. This one has height K + 1. And now all the nodes in this picture that I've highlighted, A, B, and C haven't changed. They were height balanced before, they still are. Um but now X and Y X wasn't height balanced before, Y was. Now both X and Y are height balanced. Okay? That's case one. In case two, the skew of Y is flat, which means that this is a K, and this is a K, and this is a K + 1, and this is a K + 2.

Okay? But still all the nodes are balanced. Height balanced. They're still plus or minus one. So, those are the easy cases. Unfortunately, there is a hard case, case three, but there's only one. And it's not that much harder. So, it's when skew of Y is minus one. In this case, we need to look at the left child of Y. Uh Okay, and to be alphabetical, I'm going to rename this to Z. Sorry. So, this one again is double right arrow. This one is now left arrow. And this is letter Y. And so we have A, B, C, and D potential subtrees hanging off of them. And I'm going to label the heights of these things.

These are each K - 1 or K - 2. This one's K - 1. And now compute the inside. So, this is going to be height K for this to be uh left leaning. So, this is K + 1. And this is K + 2. Okay, but the problem is this is two higher than this. The height of Z is two higher than the height of A. In this case, if I do this rotation, things get worse actually. I'll just tell you the right thing to do is This is the one thing you need to memorize. And let me draw the result. You can also just think of it as redrawing the tree like this. Uh but it's easier from an analysis perspective to think about it as two rotations.

Then we can just reduce As long as we know rotations work, then we know that this thing works. Works meaning it preserves traversal order, and we can maintain all the augmentations. So, now if I copy over these labels, the height labels, I have K - 1. I have for these two guys K - 1 or K - 2. Biggest one is K - 1. This is K - 1. And so this will be K. This will be K. This will be K + 1. And lo and behold, we have a nice height balanced tree in all three cases for this one node. Now, this was the lowest node. Once we update this one, it could be that um we change the height of the root. Before it was K + 2, now it's K + 1, or sometimes we keep it the same like over in this case.

Uh and so now we have to check the parent. Maybe the parent is out of balance. We just keep walking up the node and also maintain all the augmentations as we go, then we'll keep track of height and subtree size if we want them or any other augmentations. And after order H operations, we will have restored the height balance property, which means all the way through H equals order log N, and so all of our operations now are magically order log N.

Seek backward 5s ←
Longer seek (10s) Shift ←
Play Space Seek forward 5s →
Longer seek (10s) Shift →
0:00 Auto-scroll A Copy link at current time S

7. Binary Trees, Part 2: AVL