Hello, everybody, welcome back. We're continuing to talk about binary search trees and today, we're going to talk about balance. In particular, we're actually going to look at sort of the basic runtime of these operations that we talked about in the last lecture and from that, we're going to notice that they'll sometimes be a little bit slow. And to combat this, we want to make sure that our trees are balanced and well, doing that's a bit tough and we're going to talk a little bit about how we're going to do this with rotations. Okay, so first off we've got this great operation, it can do local searches, but how long do these operations take? And maybe a key example is the Find operation. So we'd like to find 5 in the following tree. We compare it to 7, and it's less than 7, and it's bigger than 2, and it's bigger than 4, and it's less than 6, and it's equal to 5, and we found it. And you'll note that the amount of work that we did we sort of had to traverse all the way down the tree from the root to the node that we're searching for and we had to do a constant amount of work at every level. So the number of operations that we had to perform was O of the Depth of the tree. Now, just to sort of make sure we get this. So if we have the following tree, we could be searching for different nodes A, B, C or D, which ones are faster to search with, avoiding which others? Well, A is the fastest. It's up at the root. Then D has depth only three, B has depth four, and C has depth five, and so A is faster than D is faster than B is faster than C probably. So the runtime is the depth of the node that you're looking for. But it's unfortunate, the depth can actually be pretty bad. In this example, we have only ten nodes in the tree, but this 4 at the bottom has depth 6. In fact, if you think about it, things could be even worse. A tree on n nodes could have depth n if the nodes are just sort of strung out in some long chain. And so this is maybe sort of a problem. That maybe our searches only work in O of n time were not any better than any of these other data structures that didn't really work. On the other hand, even though depth can be very bad, it can also be much smaller. This example has the same ten nodes in it, but the depth maximum depth is only four. And so by rearranging your tree, maybe you can make the depth a lot smaller. And in particular, what you realize is well, in binary search the questions that we asked, in order for it to be efficient, we wanted to guess the thing in the middle. Because then no matter which answer we got, we cut our search space in two, and so what this means for a binary search tree is at any node you're asking that one question. You want things on the left and the things on the right. Those two subtrees should have approximately the same size. And this is what we mean by balance. And if you're balanced, suppose that you're perfectly balanced, everything is exactly the same size, then this is really good for us. Because it means that each subtree has half the size of sort of the subtree of its parent. And that means after you go down, logarithmically, many levels the subtrees have size one and you're just done. And so, if your tree is well balanced, operations should run in O(log(n)) time, which is really what we want. But there's a problem with this, that if you make insertions they can destroy your balance properties. We start with this tree, it's perfectly well balanced and just has one node I guess but we insert two and then we insert three and then we insert five and then we insert four and you'll note that suddenly we've got a very, very unbalanced tree. But all we did were updates. So, somehow we need a way to get around this. We need a way to do updates without unbalancing the tree. And the basic idea for how we're going to do this, is we're going to want to have some mechanism by which we can rearrange the trees in order to maintain balance. And there's one problem with this, which is that however we rearrange the tree, we have to maintain the sorting property. We have to make sure that it's still sorting correctly or none of our other operations will work. And well, there's a key way to do this, and this is what's known as rotation. The idea is you got two nodes, X and Y. We say X is Y's parent. And there's a way to switch them. So, that instead Y is X's parent. And the like sort of sub-trees A, B, and C that hang off of X and Y. You need to rearrange them a little bit to keep everything still sorted. But there is this sort of very local rearrangement. You can go back and forth. And it keeps the sorting structure working. And it rearranges the tree in some hopefully useful way. So just to be clear about how this works, it takes a little bit of bookkeeping. But that's about it. You let P be the parent to X. Y be its left child. B be its right child. And then what we're going to do is we just need to reassign some pointers. P is the new parent of Y and Y is its child, Y is the new parent of X and X is its right child, X is the new parent of B and B is X's new left child. And once you've sort of rearranged all those pointers then everything actually works. This is a nice constant time operation and it does some useful rearrangements. So what we really need to do though is we need to have a way to sort of use these operations to actually keep our tree balanced and we're going to start talking about how to do that next time when we discuss AVL trees.
