
Title:
05x01 Trees

Description:

Welcome once again to another chance to practice your programming skills.

Today we're going to take a look at a problem that's important for physical devices

like yearbooks in a school or phone books or really any sorted index.

The problem we're going to cover this time is how to organize

and search through sorted information.

The approach I want to take is to use a tree.

We've seen trees before in some computer science programming.

The particular kind of tree I'm going to focus on

is one that has 2 branches at every level.

Suppose I have a number of friends that I want to keep track of in my yearbook

or in a telephone book.

I could use a Python list to include all 4 of their names or all 4 of those elements.

And I can check to see if an element is in a list in Python just by using the keyword "in"

putting the element on the left and the list on the right.

But we might wonder, "What is Python doing behind the scenes?"

"How is this implemented in practice?"

One way to do itand the way we'll explore today

is to build up a special kind of tree holding all of the information that I want to see.

I'm going to start with the first element of my list

and make it the root or the top of the tree.

Let me sketch out the rest so the tree is easier to see.

I've added the elements from my list1, 2, 3 and 4to this tree,

and I've put them in a special order corresponding to how they'd fall

in English alphabetical order.

So since the J in Jacob comes before the M in Margaret,

I've made Jacob the left child in Margaret.

Since the N in Nelson comes after the M in Margaretj, k, l, m, n, o, p;

yes, I can remember the English alphabetI've made it the right child.

And the A in Alice follows all the way down here to the left.

I'm going to construct a special tree to store information like this

that has a number of properties.

The first 2 just summarize or formalize this ordering intuition we had above.

Everything to the left of Margaret and all the way down

is less than or equal tocomes before in the alphabet,

is a smaller number than if I'm storing phone numbers instead

the information stored at Margaret's node.

Jacob and Alice both come before Margaret in the alphabet, so they're both on the left.

And similarly, right subtrees contain only information that's greater than or equal to

larger, later in the alphabet.

Nelson comes after Margaret, so it's here on the right.

And then finallyand this is really important

both the left and the right subtrees also follow rules I, II, and III.

It is turtles all the way down.

That makes this tree something special in computer science:

a recursive data structure.

We've already seen recursive functions that are defined in terms of themselves.

Now I'm talking about a recursive way to lay out data that's defined in terms of itself.