This course introduces the broader discipline of computer science to people having basic familiarity with Java programming. It covers the second half of our book Computer Science: An Interdisciplinary Approach (the first half is covered in our Coursera course Computer Science: Programming with a Purpose, to be released in the fall of 2018). Our intent is to demystify computation and to build awareness about the substantial intellectual underpinnings and rich history of the field of computer science. First, we introduce classic algorithms along with scientific techniques for evaluating performance, in the context of modern applications. Next, we introduce classic theoretical models that allow us to address fundamental questions about computation, such as computability, universality, and intractability. We conclude with machine architecture (including machine-language programming and its relationship to coding in Java) and logic design (including a full CPU design built from the ground up). The course emphasizes the relationships between applications programming, the theory of computation, real computers, and the field's history and evolution, including the nature of the contributions of Boole, Shannon, Turing, von Neumann, and others.
Binary search trees
Loading...
Del curso dictado por Princeton University
Computer Science: Algorithms, Theory, and Machines
41 calificaciones
De la lección
SYMBOL TABLES
The symbol table abstraction is one of the most important and useful programmer's tools, s we illustrate with several examples in this lecture. Extending the scientific approach of the previous two lectures, we introduce and study binary search trees, a classic data structure that supports efficient implementations of this abstraction.
Conoce a los instructores
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Kevin WayneSenior Lecturer
Computer Science
The data structure that we're going to use to develop
efficient implementations for symbol tables is called a binary search tree.
It's classic fundamental data structure that every computer scientist should know.
So, now what we're going to do is add two links and
another link so that we have a doubly-linked data structure.
And actually, again, I showed with one link how many things you can get.
With two links, you can get lots of different things.
Here's a doubly-linked list.
And what we're going to talk about in this lecture is called a binary tree.
You can implement general trees, circular lists.
The general case is extremely complicated to study.
So, again, adding a second link
gives us the flexibility to do a lot of things with the data structure,
but also the responsibility to keep things under control.
And again, from the point of view of a particular object,
these structures kind of look the same,
but they can get to be quite complicated.
So, maintenance and restricting what we do is
a very important part of working with a linked structure like this.
So let's look at a binary search tree.
It's a simple doubly-linked data structure that uses comparable keys and two links.
It's a recursive data structure that has
distinct comparable keys in its order in a very specific way.
So, a BST, binary search tree,
is either null or it's a reference to BST node, the root.
And a BST node is a data type that has references to a key,
a value, and two BSTs,
a left subtree and a right subtree.
So this is an extension of our linked list data type.
We're going to use a private class that has the information.
We're going to have a key and a value.
And then our links are references to other nodes,
one of them is called the left and the other one is called right.
And then to make our client code a little bit more succinct,
we're going to have a constructor that takes the key and
value as argument and sets up the key and value fields.
The key characteristic of the binary search tree is that it's ordered,
and this is a definition of the ordering within the data structure.
All the keys in the left subtree of each node are smaller than
its key and all the keys in the right subtree of each node are larger than its key.
Since the keys are distinct,
we don't have to worry about any equality.
Now, this is an example of a binary search tree.
It's a root, is a reference to a node.
That nodes got a key.
In this case, the word "it".
We got alphabetical order of the keys.
Their values are associated.
So it has the value of two associated with it.
On the left, is another binary search tree.
In this case, it's just got one node.
On the right, is another binary search tree that's got four nodes.
All the keys on the left are before it in the alphabetical ordering.
All the keys on the right are after it in the alphabetical ordering.
And more than that, the trees on the left and the right also satisfy that property.
So they're recursively all the way down the data structure.
So, V has a smaller key to its left and a larger key to its right.
That's a binary search tree,
and that's going to be the basis of our symbol table implementation.
As with link lists,
we'll look at the code that we use to process trees before looking at
the symbol table implementation just to get used to
working with a data structure of this sort.
So what are the standard operations that we're going to want to perform?
We're going to want to do a searching tree.
We're going to want to add a new key-value pair.
And we're going to want to traverse the tree,
visit every node in order of the keys.
Also, we want to be able to remove a given key.
That one is a little more complicated,
and we're not going to address it in this lecture,
but that's not so difficult.
We'll covered it in algorithms course.
So let's look at the code required to implement these sorts of operations.
So, search, we want to find the value associated
with a given key in a BST or return null if it's not there.
So, all we use is a recursive method that mirrors this recursive data structure.
If the given key is less than the key at the current node, go left.
If it's greater, go right.
If it's equal, you found it. That's this code.
So, data type operations going to be called get,
and we'll call a recursive routine that takes an extra argument,
which is the tree that you're searching in.
So we call a recursive routine for the root.
So, now here's our recursive routine.
It takes a node in a key.
And it's like binary search,
except that we have to account for the fact that we're
working in this recursive data structure, not an array.
If the node that were given is null,
then we say no, we didn't find anything.
Now we do the comparison of the key that we had
as argument with the key in the current node.
If it's less, then we just go to the left,
recursively call this routine for the node on the left or the tree on the left.
If it's greater, we go to the right,
recursively call the routine for the node or the tree on the right.
Otherwise, it's equal, which return the value that we're supposed to return.
And that's it. That's search in a binary search tree.
So, here's an example.
Suppose that we're searching for the string "the" in this tree.
So we start by checking,
comparing "the" against "it".
In this case, it's greater. So we move right.
And so, now we're comparing "the" against "was". It's less.
So we go left. And then we compare "it" against "the",
and that's a SEARCH HIT.
So we just return the value.
So, what about if the key is not in the tree?
So let's look at the code for searching and finding,
and it's not there, and then associating new value with it.
So, again, we're going to use the same basic idea.
If it's less, go left.
If it's greater, go right.
That's the code. If the values already there,
then we just change the value.
That's all we're supposed to do in that case.
So, now, we're supposed to put a new value with V. If it's greater, we go to the right.
If it's less, we go to the left.
And then we just change the value.
That's a SEARCH HIT. Let's associate a new value.
So that's easy to do the search and change the value.
So, a code for adding a new key is a little more complicated.
But if you think about it recursively,
it's not so bad.
So what we're going to do is search for the key.
If it's not in the tree,
we're going to wind up on a no link.
In that case, we're going to create a new node and return the link to that node.
Every time we go down the tree,
when we come back up,
we're going to assign the link to the node that we just went down.
And then in this one case, it will be a new node.
So, here's what the code looks like,
and you want to study this to be sure that you understand it.
It's a little bit subtle,
but not so complicated if you think of it recursively.
So, let's suppose we're putting a new key "worst" and associating with the value one.
So, in this search,
it's greater. So we go right.
And "worse", now it's greater.
So we go right. So, now we wind up on null.
So, in this case,
we executed the code x.right equals put of (x.left, key, value).
And we're on this call to put x.right key-value.
And that call found a null.
So it's going to create a new node.
And then what does it do with that node?
It returns a reference to that node.
So, if we look at x.right equals put of (x.right, key,
value), put of (x.right, key,
value) is a reference to the new node.
And that's where it get assigns in the right link of the node that contains "was".
It's also true, as we go up,
the tree were reassigning the same links that we went down,
but that's no real extra cost.
With this recursive setup,
we're able to implement insertion just by adding a line to the recursive put routine.
Now, this code is subtle,
and it's worthy of study.
But the bottom line is,
it's quite easy to add a new node.
The third thing that we want when using a binary search trees
underlying data structure is code that can
traverse the tree and give us the keys in sorted order.
So what we're going to do is put them on a queue,
and we'll see why in just a second.
And this is a very simple recursive method.
We put them on the queue for the less subtree,
and then we put the key at the root in the queue,
and then we do it for the rights of subtree.
And how do we convince ourselves that this is going to work?
Well, the way we do for any recursive method.
If they're in order, on the left,
once we've done it on the left,
we know that those are all smaller than the key at the root.
So we can put the key at the root on and have them in order including the root.
And then, if they're going to be an order and the key in the right,
we just do it for the right,
and we can be convinced that we get all the keys in the binary search tree in order.
So, here's our top level routine.
We're going to build a queue and return that queue in this routine called keys.
And it's got this return type of iterable key.
So what that means is that it implements
the iterable data type for Java that supports the foreach.
How does that work?
Well, we made queue iterable so that a client of these keys routine
can use foreach with that
because what'll happen is that it will use the queue which is iterable.
So this enables clients of our symbol table, for example,
to iterate through keys just because we put them on a queue.
Client doesn't need to know that.
And then, all we do is call this simple
recursive routine for the binary search tree that's referenced by root.
So it takes a reference to a node with the root and our queue as arguments,
effects as null just return.
Otherwise, recursively call itself for the left,
put the key at the root on the queue,
and then recursively call itself for the right.
This is an extremely simple implementation of this basic facility.
So, here's our example.
So, first thing we do is go left.
And then in this, the left has no and then it puts the key at the root,
which is best on the queue.
And then on the right, it's null.
So it goes back up to the root.
And now the top level call the same method for the right subtree.
Now we have to go left, go left again.
Now we have null.
So we just print that and then go back.
And now, this is print the key at that node.
Now, having done, it's left subtree.
And now, go do. It's right subtree,
which is just one node.
And now we go back.
And now we've done the left subtree of that node,
and we're done because this right subtree is null.
So that's printing the keys out in sorted order for that simple example.
So, now we've implemented the basic methods that we need for
using a binary search tree as an underlying data structure for symbol table.
Now we can search, change a value,
add a node, and traverse the keys in sorted order.
So, next, we'll look at the symbol table ADT implementation in full detail.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
