0:00

In this lecture, we're going to talk about trees.

Â Let's look at some example trees.

Â So here we have a sentence, "I ate the cake".

Â Now, we're going to look at a syntax tree for that,

Â which shows the structure of the sentence.

Â So it's similar to sentence diagramming that you may have done in grade school.

Â 0:19

So we have at the top of the tree, the S for

Â sentence and then children: a noun phrase and a verb phrase.

Â The child of the noun phrase is the word I from the sentence.

Â And the child of the verb phrase is a verb and noun phrase, where the verb is ate,

Â and the noun phrase is a determiner and a noun, the and cake.

Â So along the bottom of the tree, we have the words from the sentence,

Â "I ate the cake", and the rest of the tree reflects the structure of that sentence.

Â We can look here at a syntax tree for an expression 2sin(3z-7),

Â we can break that up into the structure.

Â So at the top level, we have a multiplication,

Â that's really the last thing that's done, multiplying the 2 and the sine.

Â 1:09

Within the sine, what we're applying the sine to is 3z-7,

Â so we have the minus that's happening last with a 7 and then this 3z, 3 times z.

Â So this shows again the structure of the expression and

Â the order in which you might evaluate it.

Â So from the bottom, you would first do 3 times z, and then you would subtract 7

Â from that, you'd apply the sine to that, and then you multiply that by 2.

Â 1:36

Trees are also used to reflect hierarchy.

Â So this reflects hierarchy of geography where we have at the left hand side

Â the top level of the hierarchy, the world.

Â And then below that,

Â entities in the world, United States, all sorts of other things, United Kingdom.

Â And then below that, various subcomponents of the geography.

Â So we've got, for the case of the United States, states, and

Â then within those states, cities.

Â 2:04

Another example of a hierarchy is the animal kingdom.

Â This is part of it where we've got animals, and then below that, different

Â types of animals, so invertebrates, reptiles, mammals, and so on.

Â And then within each of these, we have various subcategorizations.

Â So this shows this entire hierarchy.

Â We also use trees in computer science for code.

Â So in order to represent code, we will do that with an abstract syntax tree.

Â So our code here is a while loop.

Â While x is less than 0, x is x+2, f of x.

Â So we reflect that at the top, we have while, which is our while loop.

Â And the children of the while loop are the condition that needs to be met for

Â the while loop to continue and then the statement to execute.

Â So the condition is x less than 0, so comparison operation, the variable x and

Â the constant 0.

Â And then the statement to execute, well, it's actually multiple statements so

Â we have a block.

Â And in those blocks, we have two different statements, an assignment statement and

Â a procedure call.

Â The assignment statement, the left child is the variable we're assigning to,

Â which is x, and the right child is an expression, in this case, x+2.

Â The procedure call, the left child is the name of the procedure, and

Â subsequent children are the arguments to that procedure.

Â In our case, we just have one argument x.

Â Binary search tree is a very common type of a tree used in computer science.

Â The binary search tree is defined by the fact that it's binary, so

Â that means it has at most two children at each node.

Â And we have the property that at the root node,

Â the value of that root node is greater than or

Â equal to all of the nodes in the left child, and

Â it's less than the nodes in the right child.

Â So here less than or greater than, we're talking about alphabetically.

Â So Les is greater than Alex, Cathy, and Frank, but

Â is less than Nancy, Sam, Violet, Tony, and Wendy.

Â And then that same thing is true for every node in the tree has the same thing.

Â For instance, Violet is greater than or equal to Tony and

Â strictly less than Wendy.

Â 4:30

The binary search tree allows you to search quickly.

Â For instance, if we wanted to search in this tree for Tony, we could start at Les.

Â Notice that we are greater than Les, so therefore, we're going to go right.

Â We're greater than Sam so we'll go right.

Â We're less than Violet so we'll go left and then we find Tony.

Â And we do that in just four comparisons.

Â It's a lot like a binary search in a sorted array.

Â 5:09

So if we go back to our example here, Les is a node that

Â has the key Les and two child trees, the Cathy child tree and the Sam child tree.

Â The Cathy child tree is a node with a key Cathy and

Â two child trees, the Alex child tree and the Frank child tree.

Â Let's look at the Frank child tree.

Â It's a node with a key Frank and two, well, does it have any child trees?

Â No, it has no child trees.

Â 5:37

So let's look at some other examples.

Â An empty tree, well, we don't really have a good representation for that,

Â it's just empty.

Â A tree with one node is the Fred tree, and it has no children.

Â A tree with two nodes is a Fred with a single child Sally,

Â that in itself has no children.

Â 6:14

And here, the children of Fred are Kate, Sally, and Jim.

Â We are actually showing that with arrows, commonly, when you show trees,

Â you don't actually show the arrows.

Â We just assume that if a node is above another node,

Â that it's a parent of that node.

Â 6:53

The descendant is an inverse of the ancestor, so it's the child or

Â child of child and so on.

Â So the descendants of Fred are all of the other nodes since it's the root, Sam,

Â Hugh, Kate, Sally and Jim.

Â The descendants of Kate would just be Sam and Hugh.

Â 7:21

A leaf is a node that has no children.

Â So that's Sam, Hugh, Sally, and Jim.

Â An interior node are all nodes that aren't leaves.

Â So this is Kate and Fred.

Â Another way to describe it is all nodes that do have children.

Â A level: 1 plus the number of edges between the root and

Â a node, let's think about that.

Â Fred, how many edges are there between the root and the Fred node?

Â Well, since the Fred node is the root, there are no edges.

Â So its level would be 1.

Â Kate has one edge between Fred and Kate,

Â so its level would be 2, along with its siblings, Sally and Jim.

Â 8:56

The most common representation probably of trees, is really without the parent.

Â But it's possible to also have parent pointers, and that can be useful as a way

Â to traverse from anywhere in a tree to anywhere else by going up and then down,

Â following parent nodes and then child nodes.

Â On rare occasions,

Â you could have a tree that's represented just with parent pointers.

Â Okay, but that's unusual because a lot of times, kind of the way you get access

Â to a tree is via its root and you want to go down from there.

Â There are other less commonly used representations of trees as well,

Â we're not going to get into here.

Â 10:01

Since trees are recursively defined, it's very common to write

Â routines that operate on trees that are themselves recursive.

Â So for instance,

Â if we want to calculate the height of a tree, that is the height of a root node,

Â we can go ahead and recursively do that, going through the tree.

Â So we can say, for instance, if we have a nil tree, then its height is a 0.

Â 10:27

Otherwise, we're 1 plus the maximum of the left child tree and the right child tree.

Â So if we look at a leaf for example, that height would be 1 because the height

Â of the left child is nil, is 0, and the height of the nil right child is also 0.

Â So the max of that is 0, 1 plus 0.

Â We could also look at calculating the size of a tree that is the number of nodes.

Â Again, if we have a nil tree, we have zero nodes.

Â Otherwise, we have the number of nodes in the left child plus 1 for

Â ourselves plus the number of nodes in the right child.

Â So 1 plus the size of the left tree plus the size of the right tree.

Â