PK o!iAZ^_n , Programming_Practice_-_Trees/01-Trees.en.srt1
00:00:00,000 --> 00:00:05,000
Welcome once again to another chance to practice your programming skills.
2
00:00:05,000 --> 00:00:10,000
Today we're going to take a look at a problem that's important for physical devices
3
00:00:10,000 --> 00:00:16,000
like yearbooks in a school or phone books or really any sorted index.
4
00:00:16,000 --> 00:00:20,000
The problem we're going to cover this time is how to organize
5
00:00:20,000 --> 00:00:23,000
and search through sorted information.
6
00:00:23,000 --> 00:00:26,000
The approach I want to take is to use a tree.
7
00:00:26,000 --> 00:00:29,000
We've seen trees before in some computer science programming.
8
00:00:29,000 --> 00:00:31,000
The particular kind of tree I'm going to focus on
9
00:00:31,000 --> 00:00:35,000
is one that has 2 branches at every level.
10
00:00:35,000 --> 00:00:39,000
Suppose I have a number of friends that I want to keep track of in my yearbook
11
00:00:39,000 --> 00:00:41,000
or in a telephone book.
12
00:00:41,000 --> 00:00:47,000
I could use a Python list to include all 4 of their names or all 4 of those elements.
13
00:00:47,000 --> 00:00:53,000
And I can check to see if an element is in a list in Python just by using the keyword "in"--
14
00:00:53,000 --> 00:00:56,000
putting the element on the left and the list on the right.
15
00:00:56,000 --> 00:00:59,000
But we might wonder, "What is Python doing behind the scenes?"
16
00:00:59,000 --> 00:01:01,000
"How is this implemented in practice?"
17
00:01:01,000 --> 00:01:04,000
One way to do it--and the way we'll explore today--
18
00:01:04,000 --> 00:01:09,000
is to build up a special kind of tree holding all of the information that I want to see.
19
00:01:09,000 --> 00:01:12,000
I'm going to start with the first element of my list
20
00:01:12,000 --> 00:01:14,000
and make it the root or the top of the tree.
21
00:01:14,000 --> 00:01:17,000
Let me sketch out the rest so the tree is easier to see.
22
00:01:17,000 --> 00:01:22,000
I've added the elements from my list--1, 2, 3 and 4--to this tree,
23
00:01:22,000 --> 00:01:27,000
and I've put them in a special order corresponding to how they'd fall
24
00:01:27,000 --> 00:01:29,000
in English alphabetical order.
25
00:01:29,000 --> 00:01:33,000
So since the J in Jacob comes before the M in Margaret,
26
00:01:33,000 --> 00:01:36,000
I've made Jacob the left child in Margaret.
27
00:01:36,000 --> 00:01:43,000
Since the N in Nelson comes after the M in Margaret--j, k, l, m, n, o, p;
28
00:01:43,000 --> 00:01:46,000
yes, I can remember the English alphabet--I've made it the right child.
29
00:01:46,000 --> 00:01:49,000
And the A in Alice follows all the way down here to the left.
30
00:01:49,000 --> 00:01:54,000
I'm going to construct a special tree to store information like this
31
00:01:54,000 --> 00:01:56,000
that has a number of properties.
32
00:01:56,000 --> 00:02:02,000
The first 2 just summarize or formalize this ordering intuition we had above.
33
00:02:02,000 --> 00:02:07,000
Everything to the left of Margaret and all the way down
34
00:02:07,000 --> 00:02:11,000
is less than or equal to--comes before in the alphabet,
35
00:02:11,000 --> 00:02:14,000
is a smaller number than if I'm storing phone numbers instead--
36
00:02:14,000 --> 00:02:17,000
the information stored at Margaret's node.
37
00:02:17,000 --> 00:02:21,000
Jacob and Alice both come before Margaret in the alphabet, so they're both on the left.
38
00:02:21,000 --> 00:02:27,000
And similarly, right subtrees contain only information that's greater than or equal to--
39
00:02:27,000 --> 00:02:29,000
larger, later in the alphabet.
40
00:02:29,000 --> 00:02:33,000
Nelson comes after Margaret, so it's here on the right.
41
00:02:33,000 --> 00:02:35,000
And then finally--and this is really important--
42
00:02:35,000 --> 00:02:41,000
both the left and the right subtrees also follow rules I, II, and III.
43
00:02:41,000 --> 00:02:44,000
It is turtles all the way down.
44
00:02:44,000 --> 00:02:47,000
That makes this tree something special in computer science:
45
00:02:47,000 --> 00:02:49,000
a recursive data structure.
46
00:02:49,000 --> 00:02:53,000
We've already seen recursive functions that are defined in terms of themselves.
47
00:02:53,000 --> 99:59:59,000
Now I'm talking about a recursive way to lay out data that's defined in terms of itself.
PK p!iAs>t 4 Programming_Practice_-_Trees/02-Drawing_Trees.en.srt1
00:00:00,000 --> 00:00:04,000
I'm going to draw a tree that's already mostly filled out.
2
00:00:04,000 --> 00:00:10,000
This tree uses numbers like 5 and 3 and 1, 6 and 8 and 13,
3
00:00:10,000 --> 00:00:13,000
but it follows the same principle we talked about before.
4
00:00:13,000 --> 00:00:19,000
For any particular node like 5, all of the children I can reach on the left are less than 5,
5
00:00:19,000 --> 00:00:24,000
and all of the children I can reach on the right--6, 8, and 13--are greater than 5.
6
00:00:24,000 --> 00:00:26,000
Now I want to add 7 to this tree,
7
00:00:26,000 --> 00:00:30,000
and you're going to help me out by telling me where it might go.
8
00:00:30,000 --> 00:00:34,000
I've drawn 7 boxes with sort of dotted edges,
9
00:00:34,000 --> 00:00:38,000
and these represent possible new nodes that I could add.
10
00:00:38,000 --> 00:00:45,000
What I'd like you to do is check all of the boxes where I could legitimately add a node for 7
11
00:00:45,000 --> 00:00:48,000
to the sorts of trees that we've been talking about.
12
00:00:48,000 --> 99:59:59,000
Check all the boxes that apply.
PK q!iA;ј = Programming_Practice_-_Trees/03-Drawing_Trees_Solution.en.srt1
00:00:00,000 --> 00:00:02,000
Let's answer this together.
2
00:00:02,000 --> 00:00:07,000
To answer it, I'm just going to review the 3 rules that talk about these trees.
3
00:00:07,000 --> 00:00:10,000
All of the left children of a node are less than or equal to it,
4
00:00:10,000 --> 00:00:13,000
all of the right children of a node are greater than or equal to it,
5
00:00:13,000 --> 00:00:17,000
and both of the children should follow rules I through III as well.
6
00:00:17,000 --> 00:00:19,000
This is a recursive data structure.
7
00:00:19,000 --> 00:00:22,000
Let's take a look at this first option here on the left. What could go in this box?
8
00:00:22,000 --> 00:00:26,000
Well, since it's a right child of this node labeled 1, by rule number II
9
00:00:26,000 --> 00:00:29,000
we know that it has to be greater than or equal to 1.
10
00:00:29,000 --> 00:00:34,000
And since it's eventually reachable on the left from 3,
11
00:00:34,000 --> 00:00:36,000
we know that it's less than or equal to 3.
12
00:00:36,000 --> 00:00:42,000
So the only things I could put in this box are 1, 2, or 3--not 7.
13
00:00:42,000 --> 00:00:46,000
It can't hold 7 because it has to be less than or equal to 3.
14
00:00:46,000 --> 00:00:48,000
So this one won't work out for us.
15
00:00:48,000 --> 00:00:51,000
By this same sort of reasoning--let's take a look at this box--
16
00:00:51,000 --> 00:00:56,000
we know it has to be greater than or equal to 3 because it's to the right of this 3 node
17
00:00:56,000 --> 00:00:59,000
but less than or equal to 5.
18
00:00:59,000 --> 00:01:03,000
So 4 would be a great thing to put there, but 7 doesn't fit.
19
00:01:03,000 --> 00:01:06,000
Down here we're getting a little bit closer.
20
00:01:06,000 --> 00:01:09,000
This node has to be less than or equal to 6
21
00:01:09,000 --> 00:01:12,000
but also greater than or equal to 5.
22
00:01:12,000 --> 00:01:14,000
This is a little harder to see in the picture,
23
00:01:14,000 --> 00:01:18,000
but starting from 5's right child I can eventually get down here.
24
00:01:18,000 --> 00:01:20,000
This is greater than or equal to 5.
25
00:01:20,000 --> 00:01:24,000
So maybe 5.5 could go in there but not 7.
26
00:01:24,000 --> 00:01:26,000
Over here--oh, I'm getting excited now--
27
00:01:26,000 --> 00:01:29,000
since I can reach it going to the left of 8,
28
00:01:29,000 --> 00:01:34,000
I need something less than or equal to 8 and something greater than or equal to 6.
29
00:01:34,000 --> 00:01:40,000
7 seems like a perfect thing to put here, so I could definitely add 7 to this part of my tree.
30
00:01:40,000 --> 00:01:43,000
Both of these would have to be greater than or equal to 8,
31
00:01:43,000 --> 00:01:45,000
so they're not good answers for 7.
32
00:01:45,000 --> 00:01:48,000
Now let's take a look at this evil box up here at the top.
33
00:01:48,000 --> 00:01:52,000
We've been describing trees with exactly 2 branches.
34
00:01:52,000 --> 00:01:55,000
We've been talking about the left child and the right child.
35
00:01:55,000 --> 00:01:58,000
I drew this mysterious third branch coming off of 5,
36
00:01:58,000 --> 00:02:03,000
and I drew it in the picture to the right, so you might be tempted to think,
37
00:02:03,000 --> 00:02:09,000
"Oh, this has to be a little better than 5 and a little less than 8, so 7 would be perfect."
38
00:02:09,000 --> 00:02:14,000
But in fact, the sort of recursive data structure we're describing
39
00:02:14,000 --> 00:02:18,000
allows exactly or up to 2 children.
40
00:02:18,000 --> 00:02:20,000
So it would be very tempting to put a 7 there,
41
00:02:20,000 --> 00:02:23,000
but that's not the kind of data structure we're describing.
42
00:02:23,000 --> 00:02:26,000
Now, don't feel bad if this one seemed very tempting to you.
43
00:02:26,000 --> 00:02:30,000
It's entirely possible to make trees like this that have 3 children every time
44
00:02:30,000 --> 00:02:32,000
or a variable number of children every time.
45
00:02:32,000 --> 00:02:35,000
But the practice problems I'm going to be going over
46
00:02:35,000 --> 99:59:59,000
require 1, 0, or 2.
PK r!iA/rG G 9 Programming_Practice_-_Trees/04-Representing_Trees.en.srt1
00:00:00,000 --> 00:00:04,000
So now that we understand how these trees should work in theory,
2
00:00:04,000 --> 00:00:07,000
let's talk about how we might implement them in Python.
3
00:00:07,000 --> 00:00:12,000
Looking just at the top node of this tree, it has 3 important parts:
4
00:00:12,000 --> 00:00:15,000
the content--the number or name that I'm storing there--
5
00:00:15,000 --> 00:00:19,000
and then the left and the right children coming out.
6
00:00:19,000 --> 00:00:23,000
However, we can also see that some nodes have no children,
7
00:00:23,000 --> 00:00:25,000
may not have a left or a right child.
8
00:00:25,000 --> 00:00:29,000
Let's use a very simple and direct approach for encoding these trees
9
00:00:29,000 --> 00:00:31,000
or representing them in Python.
10
00:00:31,000 --> 00:00:33,000
We'll use tuples.
11
00:00:33,000 --> 00:00:39,000
We'll have a 3 tuple where the 3 parts correspond exactly to my value--
12
00:00:39,000 --> 00:00:43,000
the current content--the left child, and the right child.
13
00:00:43,000 --> 00:00:45,000
Some nodes have no children.
14
00:00:45,000 --> 00:00:49,000
We'll use None in Python to represent that.
15
00:00:49,000 --> 00:00:55,000
So this 7 node would look like this--a 7 with no left child and no right child--
16
00:00:55,000 --> 00:00:59,000
and this complete tree will be a much bigger nested tuple.
17
00:00:59,000 --> 00:01:03,000
At the top level it's 1 tuple with 3 parts:
18
00:01:03,000 --> 00:01:08,000
a big left child, 5--my current value--and a big right child.
19
00:01:08,000 --> 00:01:13,000
And the left child and the right child also follow exactly the same layout.
20
00:01:13,000 --> 00:01:15,000
We had suggested earlier that in computer science
21
00:01:15,000 --> 00:01:18,000
this is often called a recursive data structure.
22
00:01:18,000 --> 00:01:26,000
My tree, this 5, is made up of or contains smaller instances of itself--
23
00:01:26,000 --> 00:01:29,000
smaller instances that follow the same sort of pattern.
24
00:01:29,000 --> 00:01:32,000
So now let's get some concrete practice coding this up in Python.
25
00:01:32,000 --> 00:01:39,000
Let's try to write a procedure insert that takes 1 of these trees and a new element
26
00:01:39,000 --> 00:01:41,000
and returns a new tree including that element,
27
00:01:41,000 --> 00:01:43,000
just like you did in the quiz.
28
00:01:43,000 --> 00:01:46,000
I'll just set things up. Insert takes a tree and an element.
29
00:01:46,000 --> 00:01:50,000
This is going to be a recursive procedure. All the cool procedures are recursive.
30
00:01:50,000 --> 00:01:54,000
The base case is actually inserting into the empty tree.
31
00:01:54,000 --> 00:01:56,000
If you don't give me anything to work with,
32
00:01:56,000 --> 00:02:01,000
I'll just make a new singleton tree containing only this element. And that looks like this.
33
00:02:01,000 --> 00:02:06,000
A singleton tree, just a single branch, has no left child, no right child,
34
00:02:06,000 --> 00:02:08,000
and the element right in the center.
35
00:02:08,000 --> 00:02:14,000
If the tree is not None, then it has a left child, a current element, and a right child.
36
00:02:14,000 --> 00:02:17,000
And what we want to do is compare the element to be inserted
37
00:02:17,000 --> 00:02:19,000
against the element we found here,
38
00:02:19,000 --> 00:02:25,000
and that will tell us whether we should insert into the left or insert into the right.
39
00:02:25,000 --> 00:02:27,000
I'm going to do this in 2 steps.
40
00:02:27,000 --> 00:02:31,000
If the element to be inserted is less than or equal to what we're currently looking at,
41
00:02:31,000 --> 00:02:35,000
then we're going to call ourselves recursively going down and to the left.
42
00:02:35,000 --> 00:02:40,000
So I'm going to call insert on the left child and try to insert the same element into it.
43
00:02:40,000 --> 00:02:45,000
And that's going to return a new tree, a new--minor typo--left child.
44
00:02:45,000 --> 00:02:50,000
I'll just build up a new tree that has the new left child,
45
00:02:50,000 --> 00:02:54,000
this same element that was here already, and the old right child unchanged.
46
00:02:54,000 --> 00:02:56,000
We never even have to look in the right child.
47
00:02:56,000 --> 00:02:58,000
We can ignore that half of the tree.
48
00:02:58,000 --> 00:03:01,000
That's a phenomenal cosmic boost to speed.
49
00:03:01,000 --> 00:03:03,000
This is an efficient data structure when done well.
50
00:03:03,000 --> 00:03:05,000
Otherwise, we're going to do mostly the same thing on the right.
51
00:03:05,000 --> 99:59:59,000
So here's a quiz for you. What should go in this blank?
PK s!iA
B Programming_Practice_-_Trees/05-Representing_Trees_Solution.en.srt1
00:00:00,000 --> 00:00:03,000
This time we're going to leave the left child unchanged
2
00:00:03,000 --> 00:00:05,000
and build up a new tree based on this new right child.
3
00:00:05,000 --> 00:00:07,000
So now let's test it.
4
00:00:07,000 --> 00:00:10,000
I'm going to make a very simple tree that has midpoint right at the root,
5
00:00:10,000 --> 00:00:15,000
and let's say that I insert atwood, margaret into this tree.
6
00:00:15,000 --> 00:00:19,000
We think it should go on the left because atwood is less than midpoint.
7
00:00:19,000 --> 00:00:21,000
A comes before M. So let's try it out.
8
00:00:21,000 --> 00:00:24,000
And in fact, it did. Here's our answer.
9
00:00:24,000 --> 00:00:29,000
Here's our answer down here in Python tuple form, and here's the tree it corresponds to.
10
00:00:29,000 --> 00:00:33,000
Midpoint at the top with atwood, margaret as the left child.
11
00:00:33,000 --> 00:00:37,000
Midpoint at the top with atwood, margaret as the left child.
12
00:00:37,000 --> 00:00:41,000
No right child for midpoint, no children at all for atwood, margaret.
13
00:00:41,000 --> 00:00:44,000
Now let's try inserting zuma, jacob into this tree.
14
00:00:44,000 --> 00:00:47,000
Here is a pictorial representation of what we want to get out.
15
00:00:47,000 --> 00:00:53,000
Midpoint has only a right child. That right child is zuma, jacob--jacob, which I can't spell.
16
00:00:53,000 --> 00:00:56,000
Down here is the Python nested tuple interpretation.
17
00:00:56,000 --> 00:01:01,000
Midpoint has no left child, but it does have a right child: zuma, jacob.
18
00:01:01,000 --> 00:01:04,000
But reading this Python tuple stuff, that's really hard,
19
00:01:04,000 --> 00:01:08,000
so let's write a procedure to walk down one of these trees and print out everything in order.
20
00:01:08,000 --> 00:01:10,000
Again, this is a recursive procedure.
21
00:01:10,000 --> 00:01:12,000
If we've reached the end of the line, we don't do anything,
22
00:01:12,000 --> 00:01:15,000
but otherwise, here's what I'm going to do.
23
00:01:15,000 --> 00:01:17,000
Remember our rule for these trees.
24
00:01:17,000 --> 00:01:19,000
All of my left children are less than or equal to me.
25
00:01:19,000 --> 00:01:21,000
So I'll print them out first with a recursive call,
26
00:01:21,000 --> 00:01:25,000
then I'll print out myself, and then because all of my right children are greater than
27
00:01:25,000 --> 00:01:27,000
or equal to me, I'll print them out last.
28
00:01:27,000 --> 00:01:30,000
Now let's try this out with a little more complicated test case.
29
00:01:30,000 --> 00:01:34,000
I have taken a tree that has a midpoint, and then I'm inserting both Jacob Zuma
30
00:01:34,000 --> 00:01:36,000
and also Margaret Atwood into it.
31
00:01:36,000 --> 00:01:40,000
It would be a rare tree that would contain both the author of The Blind Assassin
32
00:01:40,000 --> 00:01:44,000
and also a South African president in 2009, but you never know.
33
00:01:44,000 --> 00:01:48,000
And now when we print out the tree, we get all of the elements in alphabetical order.
34
00:01:48,000 --> 00:01:52,000
Huh. Actually, if we didn't know any other way to sort things,
35
00:01:52,000 --> 99:59:59,000
this tree could be a way to put any arbitrary elements in ascending order.
PK t!iA+GM / Programming_Practice_-_Trees/06-Contains.en.srt1
00:00:00,000 --> 00:00:04,000
Now let's write one last procedure for these trees: contains.
2
00:00:04,000 --> 00:00:07,000
We want to see if a given tree contains an element.
3
00:00:07,000 --> 00:00:10,000
And the real trick with contains is that I don't have to look at the whole tree.
4
00:00:10,000 --> 00:00:14,000
If I'm given a very small element, I'll just go down the left path
5
00:00:14,000 --> 00:00:16,000
because I know it's not in the right path.
6
00:00:16,000 --> 00:00:18,000
Similarly, if I'm given a really huge element,
7
00:00:18,000 --> 00:00:21,000
I'll only go down the right path because I know it's not on the left.
8
00:00:21,000 --> 00:00:24,000
This is a recursive procedure, so it has a base case.
9
00:00:24,000 --> 00:00:27,000
If we're at the bottom of the tree and we haven't found it, then we return False.
10
00:00:27,000 --> 00:00:32,000
And now if this element is exactly the element we want, we found it.
11
00:00:32,000 --> 00:00:34,000
And then based on the dictionary ordering,
12
00:00:34,000 --> 00:00:38,000
we'll either call ourselves recursively on the left child only or on the right child only.
13
00:00:38,000 --> 00:00:44,000
Let's see if our third tree contains midpoint. It should. That's right at the top.
14
00:00:44,000 --> 00:00:48,000
Oh! Silly Python error.
15
00:00:48,000 --> 00:00:53,000
Else if is invalid syntax. Yep. They're exactly right and I'm wrong.
16
00:00:53,000 --> 00:00:56,000
I always get this wrong in Python.
17
00:00:56,000 --> 00:01:00,000
In Python, else if is written elif. Now let's try again.
18
00:01:00,000 --> 00:01:02,000
True. It does contain midpoint. Excellent.
19
00:01:02,000 --> 00:01:05,000
Let's see if it contains should not be there.
20
00:01:05,000 --> 00:01:07,000
Hint: The expected answer is False.
21
00:01:07,000 --> 00:01:09,000
And look, it is False.
22
00:01:09,000 --> 00:01:12,000
Unfortunately, there's actually a bug in our code.
23
00:01:12,000 --> 00:01:14,000
Let's see if we can find Jacob Zuma.
24
00:01:14,000 --> 00:01:16,000
He should totally be there but he's not.
25
00:01:16,000 --> 00:01:18,000
We still get False.
26
00:01:18,000 --> 00:01:21,000
Well, if there's a bug in our code, we have to find a test case that shows it.
27
00:01:21,000 --> 00:01:23,000
This is a test case that shows it.
28
00:01:23,000 --> 00:01:26,000
We tried a simpler one just looking for midpoint and that worked,
29
00:01:26,000 --> 00:01:28,000
so we'll just stick with this one for now.
30
00:01:28,000 --> 00:01:33,000
Our next step is to add print statement debugging until we've localized the fault.
31
00:01:33,000 --> 00:01:35,000
So here at the top of contains I'm just printing out the current tree
32
00:01:35,000 --> 00:01:37,000
and the element we're looking for.
33
00:01:37,000 --> 00:01:40,000
Let's go see what happens when we look for Jacob Zuma.
34
00:01:40,000 --> 00:01:44,000
First the tree is the entire huge tree with atwood, margaret,
35
00:01:44,000 --> 00:01:46,000
the midpoint, and then zuma, jacob,
36
00:01:46,000 --> 00:01:48,000
and the element we're looking for is zuma, jacob.
37
00:01:48,000 --> 00:01:50,000
So that's looking good so far.
38
00:01:50,000 --> 00:01:54,000
Then we call ourselves recursively and suddenly we're looking at the left child.
39
00:01:54,000 --> 00:01:58,000
Now we're looking inside the Margaret Atwood tree for zuma, jacob.
40
00:01:58,000 --> 00:02:00,000
That is not going to work.
41
00:02:00,000 --> 00:02:04,000
What this tells me is that we went left when we should have gone right.
42
00:02:04,000 --> 00:02:10,000
So somewhere up here there was some mistake involving one of these recursive calls.
43
00:02:10,000 --> 00:02:13,000
We went left but we should have gone right.
44
00:02:13,000 --> 00:02:15,000
Well, what's controlling this decision?
45
00:02:15,000 --> 00:02:18,000
It's the comparison between thiselement and element.
46
00:02:18,000 --> 00:02:20,000
Here's another quiz for you.
47
00:02:20,000 --> 99:59:59,000
Fill in this blank with code that will make this work.
PK u!iAw
8 Programming_Practice_-_Trees/07-Contains_Solution.en.srt1
00:00:00,000 --> 00:00:03,000
The basic trick was that we had it reversed last time.
2
00:00:03,000 --> 00:00:06,000
We want to check and see if element is less than or equal to thiselement,
3
00:00:06,000 --> 00:00:08,000
not the other way around.
4
00:00:08,000 --> 00:00:11,000
And now when we run it, we find the right answer.
5
00:00:11,000 --> 00:00:15,000
Here I'm making a significantly bigger tree as a kind of a final test case.
6
00:00:15,000 --> 00:00:20,000
We start out with an empty tree, but then we add 8, 6, 7, 5, 3, 0, 9
7
00:00:20,000 --> 00:00:26,000
and then also pi, 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5.
8
00:00:26,000 --> 00:00:30,000
And for each one of those we insert it into t1 and assign the result back to t1.
9
00:00:30,000 --> 00:00:32,000
So at the end of the day, t1 should have all of these.
10
00:00:32,000 --> 00:00:37,000
When we go print it out, they should be in order if our tree is working correctly.
11
00:00:37,000 --> 00:00:39,000
We should have gotten each one, and they should be in order.
12
00:00:39,000 --> 00:00:41,000
Let's go see if that works.
13
00:00:41,000 --> 00:00:46,000
Ah! 0, 1, 1, 2, 3, 4, 5, 6, 6, 7, 8, 9. Excellent.
14
00:00:46,000 --> 00:00:50,000
This is a pretty good test case for us because it's long and it also has some duplicates,
15
00:00:50,000 --> 00:00:53,000
a bunch of duplicate numbers, to make sure we're handling less than or equal to
16
00:00:53,000 --> 00:00:55,000
or whatnot correctly.
17
00:00:55,000 --> 00:00:57,000
So now we have much more confidence in our tree insertion.
18
00:00:57,000 --> 00:01:01,000
When we were looking to see if our tree contained something,
19
00:01:01,000 --> 00:01:03,000
whenever we were looking something up in the tree,
20
00:01:03,000 --> 00:01:06,000
we could throw away half the tree from consideration at each step.
21
00:01:06,000 --> 00:01:10,000
If our target number was less, we could throw away the right tree--conceptually.
22
00:01:10,000 --> 00:01:12,000
We just forget about it for a while.
23
00:01:12,000 --> 00:01:15,000
This means that even if the tree is very large,
24
00:01:15,000 --> 00:01:18,000
we don't have to make very many recursive calls.
25
00:01:18,000 --> 00:01:21,000
That makes this tree a very efficient data structure.
26
00:01:21,000 --> 00:01:26,000
And in fact, one way for Python to implement things like dictionaries
27
00:01:26,000 --> 99:59:59,000
is using just this sort of tree.
PK o!iAZ^_n , Programming_Practice_-_Trees/01-Trees.en.srtPK p!iAs>t 4 : Programming_Practice_-_Trees/02-Drawing_Trees.en.srtPK q!iA;ј = ' Programming_Practice_-_Trees/03-Drawing_Trees_Solution.en.srtPK r!iA/rG G 9 t( Programming_Practice_-_Trees/04-Representing_Trees.en.srtPK s!iA
B <