0:03

So Leo introduced binary search trees in the previous video, and

Â what we'd like to do now is really focus in on the performance of algorithms that

Â use binary search trees,

Â because with all of these data structures that we're talking about, one of the big

Â motivations for introducing a data structure is to get better performance.

Â So let's see if we do that with binary search trees.

Â So in particular, by the end of this video,

Â you'll be able to explain the running time performance of looking for

Â a word in a binary search tree and comparing this performance with other data

Â structures that we have where we might want to search for words.

Â So, in particular, for linked lists.

Â All right, so let's think back to binary search trees and, in particular,

Â in the programming assignment that you were working through we'll be using

Â binary search trees to store dictionaries.

Â So we are storing lists of words and we like to be able to lookup and search for

Â words in this data structure.

Â So we're gonna do just a small example with these words, and

Â let's think about what binary search trees we might

Â get if we start building a tree using these words.

Â So it turns out that it's not just a single binary search tree that

Â might result.

Â We could get any of these three or others potentially.

Â Depending on the order in which we insert words into the tree.

Â And so you can follow along and each one of these trees and confirm that,

Â in fact, when you look at a node that's to the left of a node,

Â and a node that's on its right, each time you're going to get the one

Â that's on the left is alphabetically before the one that's on the right.

Â Whether it be in the green,

Â binary search tree where we all have just a single path going down or

Â in one of the bushier trees that you see on the right hand side as well.

Â All right, so we have these three different binary search trees.

Â All try to capture that same set of words that form our dictionary.

Â And that's going to be interesting when we think about performance because we

Â have to think about each of these different possible

Â binary search trees that we might be working with.

Â So let's think about the isWord method for looking up a word

Â in the binary search tree, so looking up a word in the dictionary.

Â You can think about an application where we were just building the tree and

Â we're trying to add new words to it.

Â And so every time we're looking up to see if it's already in there and

Â then perhaps adding to it.

Â Or you can think about searching through a big collection of data and

Â trying to find some particular piece that we care about.

Â In either situation what we want to do is we want to start at the root

Â of the tree, and

Â we want to compare the word that we care about to the value at the current node.

Â Now, if at the current node we actually don't have a word, if the current is null,

Â then that means that we haven't found our word that we care about.

Â It's not in the tree and so we return false.

Â On the other hand, what we want to do is we wanna compare

Â the word that we care about to the current word, and if it actually agrees with it.

Â Then we wanna return true.

Â And so if we found the word, then we're happy, and we can return true.

Â On the other hand, we have two possibilities for what happens if our node

Â isn't null and if the current word doesn't agree with the word that we want to find.

Â Either the word that we want to find is alphabetically before the current word, or

Â it's alphabetically after the current word.

Â And if it's alphabetically before the current word,

Â then we only need to look at the sub tree to the left of the current word.

Â If the word that we care about is alphabetically greater than or

Â after the word that we're looking at right now,

Â then we need to look at the right sub tree of the binary search tree.

Â All right, so, let's think about what that might look like and

Â remember when we're analyzing performance we want to think about best case and

Â worst case performance, you want to think about average case.

Â And with each situation it's useful to work through some examples and

Â see what does it mean to get lucky when we're running this method on

Â particular inputs, and what does it mean to get unlucky?

Â And also we need to think about what size of input do we,

Â what does it mean to talk about the size of the input?

Â What input do we have to this method?

Â And when you think about this isWord method,

Â what we're doing is searching through a collection.

Â And so the relevant input size, is the size of the dictionary.

Â The number of words we're looking through.

Â It's not so much the length of the current word.

Â It's not so much how many words we're looking for but,

Â it's the size of the dictionary, the number of words

Â that we're storing that we're looking through in order to find the word to find.

Â Okay, so our input size, or n, is the number of words in our dictionary.

Â And what we'd like to think about is how to relate the performance of this method

Â is word, to that size.

Â How does our performance change as the number of words in the dictionary changes?

Â So let's, for example,

Â look at what happens when we run isWord on the word east.

Â And what we have to do using our algorithm is look first at the root

Â of the binary search tree.

Â And oh yay, we're lucky, we hit our desired word, east, right away.

Â And so that means that for this particular run of the algorithm, we've got just

Â a single comparison that we make between the argument and a value of the tree.

Â And so, well that comparison might take a few operations, but

Â if we are lucky in the very first probe of the binary search tree, the very first

Â comparison we make, that's going to take a constant number of operations.

Â It's not going to depend on how big the tree was if we already

Â were successful when we looked at the root.

Â So in the best case, the case where we find our word right away,

Â the performance of this algorithm is big O(1), constant time.

Â But, we're not always lucky.

Â So, let's look at another case where the word that we're looking for

Â isn't at the root.

Â So let's think about what happens when we look for the word, a.

Â So we start at the root.

Â And we compare east and a, and we notice that a happens alphabetically before east.

Â So we have to look at that left sub-tree of the binary search tree.

Â Now we're looking at comparing a with at.

Â All right, a is still alphabetically at at.

Â It's a prefix of at so it comes earlier.

Â So we look to the left.

Â And now we're comparing a with am.

Â All right, now again a is alphabetically before am, and so

Â we have to look to the left, but we didn't find anything there.

Â The children of am are null.

Â And so what we notice is we've fallen off the tree.

Â A does not occur in our dictionary.

Â And so we can return an answer that says It is not a word in our dictionary so

Â false.

Â Now that's okay, it's okay if we don't always find the word, but

Â what we are curious about here is the performance.

Â How long did it take us to come to this conclusion?

Â And notice that we compared here our words to find a with three out of a seven words

Â in the dictionary and so we're working through examples, but we really care about

Â the general case so can we extrapolate what it means to think about three out of

Â the seven words to a general case as the dictionary gets really big.

Â Well, that seems hard.

Â So, let's think about maybe some more examples that will give us

Â insight into the general case.

Â And in particular we have to remember that our binary search tree

Â might be organized a little bit differently.

Â So let's think about the exact same input a but with a different

Â characterization of the binary search tree so a different organization of it.

Â And so if we had that linear version of the binary search tree what happens,

Â how many comparisons we need to do as we look for the word a amongst the seven

Â words in the dictionary that we populated the search tree with.

Â So again, we compare first to the root and we see that a comes before e, so

Â we go to the left.

Â We compare with the next word.

Â A is still before e and so we go to the left.

Â We compared a with e here, and we see that we still have to go left.

Â We compare a with ate, we still have to go left.

Â We compare a with at, we still have to go left.

Â We compare a with m, and we notice that now we fall off the tree, and

Â we see that a is not in there.

Â But we have to compare with every single one of the words in our dictionary

Â in order to come to this conclusion.

Â So notice that this was even worse than before

Â in terms of the number of comparisons that we had to do.

Â And so if we're doing worst case analysis,

Â then this is the kind of tree that we need to think about.

Â So, not only did we have to think about the number of elements in the dictionary,

Â so here, n was seven, we also had to think about how the tree was organized,

Â and what organization would lead us to the worst case behavior,

Â the worst possible behavior.

Â And, so, we see that in this linear tree, when we're looking for a word

Â that's not on the tree, in the worst case we have to make o of n comparisons.

Â We had to compare our word with every single one of the words in the dictionary.

Â Okay, so, that leads us to this analysis of how can we avoid the worst case?

Â So in the worse case we had this linear tree.

Â And we had to go all the way to the bottom to the first time that we fell

Â off the tree.

Â And then we're only then we'll be able to return false.

Â But maybe we can think of a modification of our data structure,

Â that will help us avoid the situation.

Â And so what we'd like to do is think about how the path that we have

Â to travel until we fall off the tree can be controlled.

Â Or if there is a property of the tree that we can impose that will make sure that we

Â don't have to go too far.

Â