Binary Search Trees

Loading...

En provenance du cours de Princeton University

Analysis of Algorithms

43 notes

Princeton University

Analysis of Algorithms

43 notes

This course teaches a calculus that enables precise quantitative predictions of large combinatorial structures. In addition, this course covers generating functions and real asymptotics and then introduces the symbolic method in the context of applications in the analysis of algorithms and basic structures such as permutations, trees, strings, words, and mappings. All the features of this course are available for free. It does not offer a certificate upon completion.

À partir de la leçon

Trees

The quintessential recursive structure, trees of various sorts are ubiquitous in scientific enquiry, and they arise explicitly in countless computing applications. You can find broad coverage in the textbook, but the lecture focuses on the use of analytic combinatorics to enumerate various types of trees and study parameters.

Trees and Forests14:16

Binary Search Trees 22:50

Path Length 25:55

Other Types of Trees 13:56

Rencontrer les enseignants

Robert Sedgewick
William O. Baker *39 Professor of Computer Science
Computer Science

Next we're going to talk about binary search trees.

And we saw that binary trees are a classic structure in combinatorics, and

they're enumerated by the Catalan numbers.

But they're also a classic structure in computer science.

It's a fundamental data structure that is used for all sorts of things,

but one of the most important is for implementing symbol tables,

where we have lots of information, each piece of information

is associated with a key, and we want to insert things into the symbols table, and

we want to retrieve them by key.

You can find much more information about symbol tables in our

Algorithms book or in the books that are associated with the book.

But I'll describe what binary search trees are because

that's one of the most important algorithms in computer science and

it uses a classical data structure, the binary tree.

So we work with nodes, and

those are things that we can write programs to manipulate.

Each node has a key, and the keys have values that are so

called comparable values, that means we can take two of them and

know whether one's less, equal, or greater than the other, that's all.

Now usually in the implementations we do nowadays,

we assume the keys to be all distinct.

We can do things with equal keys, but both for the analysis and for

the implementation, it's better to use distinct keys.

Now, in the binary tree representation, nodes have two subtrees,

left subtrees and right subtrees, which are empty or might be whole trees.

And if there's keys in the left subtree, all those keys are smaller than v.

And if there's keys in the right subtree, they're all larger than v.

That's what a binary search tree is.

Now [COUGH] in Java, again, without going into detail of Java code,

for those of you who don't know it, you might have to read

the Algorithms book a bit to really follow all of this.

And those of you who do know it, but either way, it's very elegant and simple,

small amount of code to implement nodes and binary trees in Java.

So we build a data type that holds this associated information,

so that we can manipulate it and keep it together and

write programs that manipulate, you'll see what those look like in just a minute.

And the only operation that we need to perform is to be able to create a new

node, with a given key and value.

And that's what this code does, is defines that data type, a node's got four fields,

it's got a key and a value, and it's got a reference to the two subtrees.

The left subtree has smaller keys, and the right subtree has larger keys.

And that's how we represent it.

And for programming language aficionados, we usually use generic types for

keys, which means that we can hold any type of data with that.

And again, you can read about these details in the Algorithms book.

So that's what the computer representation of a binary search tree looks like.

We have nodes that have keys and values.

And then each node points to another node, which is another binary search tree,

the one on the left with smaller keys and the one on the right with larger keys.

And it's a recursive structure.

And eventually, we get to places where the left subtree is empty, or

the right subtree is empty, in which case, those links would be null.

So that's the structure.

And now, what I'm going to describe is programs for

manipulating that structure for inserting new keys and for searching for keys.

The easiest is search, and let's look at the search implementation.

This is a recursive program that operates on that recursive structure.

There's some programming language jargon at the top that has to do with

the generics, and otherwise, let's look at what it does.

So this is the data type for manipulating binary trees, what is the binary tree?

It's a root node, so that's what the first line of code says.

Then there's the definition of nodes, and then this is the method for

retrieving the value associated with a given key.

I'll do it line by line.

We have a variable x that we set to be the root of the tree.

As long as that node, x, is not null, then we're going to compare

the key at x, that's x.key, with the key that we were given to search for.

That comparison can have three outcomes, either less than 0 or

greater than 0 or equal 0.

If it's less, the key we're looking for is less than x's key,

then we'll go to the left.

Go to the left is x = x.left.

That's recursively moved down the tree to the left subtree that contains smaller

nodes than x's, and we have a smaller key, so that's where we want to go.

If it's greater, we go to the right.

And if it's equal, we're done, we return x's value.

That's the implementation of search for binary search trees.

So in this example, you can see to search, say, for M, we start at S.

M is less than S, so we go left.

It's greater than E, so we go right.

And then we're successful to see M.

If we're searching for something that's not in the tree, say, we're searching for

Q, we go left.

Again, Q's less than S.

It's bigger than E, we go right.

It's bigger than M, we go right, but now we're on a null link.

And essentially, that says that if Q were in the tree, it

would have to be here, but there's nothing in the tree here, so it's not here.

And in that case,

down to the last statement in the get implementation, we return null.

So, it's a very simply expressed algorithm.

This is in a modern programming language.

It's also easy to program these and even assemble a machine line,

which people my age have done that even.

In any programming environment now, you can implement

binary trees pretty easily with a small amount of code.

So that's unsuccessful.

Now what about insert?

So this is the code for insert out of the algorithm floor, and

essentially, what it does is, when we do an unsuccessful search,

and we come to a null link, so, say, you insert Q, we get to the same place.

But then what it does is create a new node for Q.

That's first line, x equals null, return new node.

And then attaches it there, and so

that's in the recursive calls, rather than just x = x.left,

we say x.left = recursive call, and that's what does the attachment of the new node.

This is a little bit tricky, but it's very concise recursive code.

And then now we've implemented both insert and search.

And so that's an important algorithm that we want to analyze the performance of this

algorithm.

It's actually got good performance, and it's widely used.

Now the key fact that we have to worry about in doing this analysis is that

the shape of a binary search tree depends on the order of insertion of the keys.

So, the best thing that could happen would be the keys

are inserted in such a way that the tree is perfectly balanced.

That's like the tree that's ascribed Merge Sort

that we looked at in the first lecture.

The height of that tree is log N, and in that case,

all searches are going to be guaranteed to take less than log N, key comparisons say.

A typical case is more like the one that I showed for the example, where

there's some nodes on either side for most subtrees, but it's not perfectly balanced.

That's the one that we want to analyze, and we'll get to that in a minute.

And there's also the worst case, say, the keys come in in order.

If your keys come in in order, then it's not

very good performance because the average cost of searching for a key in

the tree is going to be about N/2, and that's going to be a performance problem.

If you think of a huge symbol table, and nowadays most of them are huge,

let's say a million or a billion keys,

this one over here is going to get to any key with 20 or 30 searches.

This one could require half a million or half billion.

It's a very important performance difference that's going to

make the difference between being able to address a problem and

not address it at all.

And where does the average fall in between?

That's where the analysis of algorithms comes in.

So it's reasonable to analyze binary search

tree structures under the assumption that the keys are inserted in random order.

Now that's a starting point, certainly,

you've got situations where clients do not insert them in random order.

And it's not like Quick Sort, where we can randomize because the insertions might

come from some completely external force, and we don't have any of those source,

and we don't have any way to rearrange their orders.

So it's not a randomized algorithm that we can guarantee

performance probabilistically, the way we can with Quick Sort.

But still, it's a reasonable model that

actually can be validated in lots of practical situations.

So it's a good starting point for analysis of a tree algorithm.

And when you do that, if you have,

this is BST built from 80 keys inserted in random order.

You can see that the trees you get, they're different, but

unlike what we saw for random binary trees with each tree taken equally likely,

these are kind of balanced.

Well sometimes, you get a little imbalance.

So that's typical random binary search trees, and again,

our goal is to characterize this analytically and

explain why this is different from what we get with random binary trees.

So we're going to analyze them both.

Now, the key thing is that when you're analyzing binary search trees,

the shape of the tree is a property of permutations, not trees.

Our input model is a random permutation.

That's N things in arbitrary order, N factorial possibilities.

Binary search trees, where we're talking about a random tree, we're talking about

one out of a cataly number of possibilities, which is way less.

So that's really important to remember that we're talking about

property of permutations, not tree.

So you can have, and this gives all possibilities for 1, 2, 3, and 4 nodes.

And the one that's blown up is just one illustration that shows that

two different permutations can lead to the same tree shape.

So this case, 1 comes in, and 3 goes to the right, and

then 2 goes to the left of 3, and then 4 goes to the right of 3.

But 4 and 2 could come in the other order, and you'd still get the same tree.

And again, on the other hand, the tree where the keys come

in all in order, 1, 2, 3, 4, that's the only permutation that gives that shape.

The ones that are more balanced is more permutations that I give rise to them.

Now that's an important observation to try to understand why we get

more balance with binary search trees than with binary trees.

So that's an observation, and we're going to validate that.

Now in order to get it done, we really want to think about the question, if you

have a tree shape, how many permutations are going to lead to that tree shape?

So that means if you would take a permutation and insert it into

initially empty binary search tree, how many of them are going to give that shape?

Well, we sort of just did that.

The answer to that is there's two different ones.

The 2 has to be first, that's the one at the root.

And then either you can have the 1 go to the left and the 3 go to the right, or

the 3 go to the left and the 1 go to the right, and those are the only ones.

Let's look at a bigger tree.

How many permutations map to that one?

Well, that's a more complicated problem.

So well, one thing you know is that the root has to be 4.

So you've got at least the first element of permutation has to be 4.

And then you have to have 1, 2, and 3 on the left and 5 and 6 on the right.

Well 5 and 6 on the right, there's only one order that gives that shape,

5 has to go first and then 6.

And on the left, you have the two possibilities.

Either the 2, 1, 3, but the other thing is that those two

possibilities with the 1, 2, 3 and the 5 and 6,

they can be intermixed any number of ways, so the answer is 20.

You've got 5 keys, that's the stuff that goes on the left and

the right, and you can intermix them 5 choose 2 ways.

And then you've got the two possibilities for

the left, and in this case, the one possibility for the right.

And those are the 20 permutations that lead to that tree shape.

And you can check that, validate that if you don't quite believe or

understand that map.

So that's a bigger example.

And then, from that, it's not hard to come to the general case,

how many permeations map to a general binary tree like that?

Well, there's some number of nodes on the left subtree,

say the left subtree's t sub l, then size of t sub l.

Then the root has to be that number + 1, and

then the right subtree has its number of nodes.

And then by the same argument that we just gave,

if you define P sub t to be the number of permutations that map to a tree t,

then you have a recursive formula.

P sub t = t sub l + t sub R choose t sub l, so number of different

ways to intermix them, the smaller elements in the larger elements.

And then for all the ways of intermixing them, you can still put

them in any one of the P sub t sub l orders or any one of P sub t sub R orders.

You have to multiply all those together to get the number of permutations that map to

a general binary tree.

So that's an interesting observation, and actually,

you can apply that root formula recursively and

just read off from the tree the number of shapes that mapped to it.

But we're going to use that exact formula a little bit later on.

So and the other thing to observe from this formula is that that binomial

coefficient is going to be much, much larger When the two subtrees

are nearly balanced, that's the Gaussian distribution.

So it's much larger at the middle, and we verified that analytically.

If it's within square root of that, it's going to be much, much larger.

And if t sub l is small, or

t sub r is small, it's going to be exponentially smaller.

So the number of permutations that map to an unbalanced tree is way,

way smaller than the number that map to a balanced tree, and

that's why, that's what we observe in practice.

So in summary, so far,

I've described two different binary tree models that they're both fundamental.

Binary, random binary trees from the catalan is

the classic combinatorial structure.

Binary search trees is a classic Computer Science structure.

In the one model, in the BST model that we use in simple table implementations,

balance shapes are much more likely and actually one way to think of it is,

what's the probability that the root is of rank K, for given K, 1 to N?

Well, in the BST model, it's built from a random permutation.

So, it's the first element in the permutation that goes at the root,

so the probability than any particular value is at the root is just 1/N.

It's the same for all.

That doesn't seem like it balances, but if you compare it.

And so, anyway, that sort of, balances.

And second of all, compare that probability with what you get for

the other case.

So the Catalan model, on the other hand, each tree shape is equally likely.

And this is the probability that the root is of rank k in a random binary tree.

You can't have any tree on the left and

any tree on the right out of all possible trees.

That's called a Catalan distribution.

And that gives rise to these much more

unbalanced trees to fundamentally different models.

I want to emphasize that, because we go into the analysis, and

we get into the math without the picture, it's easy to lose track of the fact that

we're talking about something that's totally totally different.

In fact, here's a plot of that cattle land distribution.

That the root is rank k in a relatively it was binary tree with N nodes.

And again, this is normalized the way that we usually do this distributional parts,

so that we can see how it converges to a curve and look at the curve.

Most of the weight is often at the edges, extremely close to the edges, in fact.

So as N gets larger, most of the probability

that the root is a rank and number two is because exponentially small.

And the probability that the root is the smallest or

the largest actually is a quarter.

So it's actually a pretty good chance that it's going to be unbalanced.

And just, by the way, there's no magic in plotting a distribution like this.

And people who are comfortable with programming,

I encourage you to go ahead and try to develop plots like that.

It's easy to write inefficient programs.

But if you think about it, and this one isn't even all that efficient, but anyway,

this is the problem that I used to produce that plot.

So as I mentioned, the probability that at least one of

the two subtrees is empty is about a half, so that's why it's going to be unbalanced.

It's like flipping a coin and put in an empty or putting in a random one,

it's going to lead to much, much different shape than we get for the other case.

Now, again, just to full disclosure of the code that I'm using

to make these pictures for people that are comfortable with programming,

the code that I used to generate random binary trees.

And it's all very similar to the code that I talked about for binary search trees.

The only difference is that I ask, add coordinates to get the height and

the width, and there's little calculation in terms of where to place nodes.

And I used our programming model from the algorithms book site to do the drawings.

But what I want to talk about now is the generate method that is

supposed to generate a new tree at a certain depth.

And what that node does is, basically it's a recursive program that computes

the internal rank of the root according the appropriate probability distribution,

and then recursively generates trees on the left and on the right.

And in this case, to make the trees look good,

I actually included the invisible external nodes in the rank field.

And the point of this is it show there are a lot of similarities, and

I use this same code to generate both kinds of trees.

The other difference is for random BST, I uniformly choose the value of that rank.

And for a random binary tree, I went to that Catalan distribution to use it.

So with a relatively small amount of code, I've been generating these tree diagrams.

And then, again, full disclosure, and I'm not going to go through that.

This is the code using our standard drawing model

from the algorithm's book site that scales and draws the binary tree,

as I talked about, a few minutes ago.

And, for those of you who enjoy programming, it's an interesting exercise,

to implement the centered bi level method that

I did for other random Catalan trees, and

to draw general trees and forests and other things.

Each one of those tasks in intriguing programming exercise for

people who enjoy programming.

So that's an introduction to binary search trees, and next,

we'll get into the analysis.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play