We'll follow through the standard method that we do for implementing an abstract data type looking at the instance variables, and constructor, and then the client code, and methods. So, let's just review what it is that we want to do. So, we have an idealized model of an associated storage mechanism. And what we want is an ADT that allows us to write Java programs that use and manipulate symbol tables. And here's the API for that ADT that we articulated early on. And then we have these performance specs and we don't consider an implementation to be a symbol table unless it meets these specs. The order of growth of the running time should be logarithmic at worst. The memory usage should be linear in the size of the collection if it's not empty. And there shouldn't be any limits within the code on the collection size. So, that's the challenge we are going to embark on right now. Okay. So, we've made the data structure choice that we're going to use BST. So, what do the instance variables in the constructor look like? Well, there's only one instance variable that's the root. We do need this private class that we're going to use to build up the binary search tree and it's got those fields key in value, and then references to the left, and right subtree, and then a small constructor that will initialize the key in value. And that's it. That's one instance variable and then the private class that describes the data type that is a node. Okay. What about the test client? We already looked at that. That's the frequency counter test client that we looked at before that tries out all our code. And so, we expect it to do the frequency count and actually print out the keys in sorted order. The example we did before we sorted them again based on the frequency count, but this is the behavior that we expect from our symbol table. And then there's the methods. So, this is empty as the binary search tree empty. Well if the root's null it's empty. The put method that's the code that we looked at when discussing the BST data structure and we'll see it again in the next slide, and the same with the get method contains we just get the key and see if it's associated with null. That's our convention allows us to implement contains with that one liner. And then iterable we talked about that one as well, and we'll summarize it again in the next slide. So, those are the four components of the data type implementation. And here's the complete code, again it fits on the slide maybe a slightly smaller font than others, but not too bad. So, that's the instance variable, the nested class, the methods. So, those are the public methods that are in the API and then each one of those is supported by a recursive helper method that are private methods that are not visible to the clients and then we have our test client. So, that's a complete implementation of the symbol table using binary search tree. And this is just a quick trace to see what it does for example, so we have it and then was comes and not even showing the frequencies just focusing on the keys. And the arrives to the left of was best is smaller than it, so it gets added on the left of it. And then of is bigger than it, less than was, less than the and so forth. So, you can see the binary search tree getting built up by new nodes getting added at the bottom. Next, we have to look at the analysis and try to understand this performance. And do we meet the performance specifications that we've set?