0:01

Now, we're going to take a look at ordered symbol table operations using the binary

Â search tree data structure as the underlying implementation. Well, each one

Â of these operations are fairly straight forward but just to check our ability to

Â manipulate this data structure, we'll take a look at each. Suppose, we wanted to find

Â the minimum key in a binary search tree, or the maximum key. Well, just looking at

Â one example you can see almost immediately what to do to find the minimum, we move

Â left from the root until we find a null key, that's where the smallest key in the

Â data structure is. To find the maximum, we move right from the root, until we find a

Â null key. What about floor and ceiling? Well, those are a little bit more

Â complicated and we'll have to, not quite the same as in the ordered array for the

Â binary search so we have to do a little bit more work for that. So just for

Â example, let's take a look at the problem of computing the floor. So, what we want

Â to find is so say, we're seeking the floor of G. So, that's the largest key in the

Â data structure that is less than G. In this case, the answer is E. So let's just

Â take a look at what we have to do in the tree, the path we have to take in the tree

Â to figure that out. Well so, we are looking for the largest key that's less

Â than G. And have S well, that key is definitely going to be in the left

Â subtree. Its not going to be bigger than S because S is bigger than G so we go to the

Â left. So now, we are sitting at E. And so what's the largest key that's less than G

Â in this, in this tree here. Well, it might be E but there's no way it's to the left

Â of E because those keys are all smaller than E and therefore smaller than G. So, E

Â is a key candidate. But it might also be in the right so we move to the right in

Â this case. Alright [cough]. So that's [cough] if K is equal to the key at the

Â root, the floor of K is K. If K is less than the key, it roots i n the left

Â subtree. That's the one we just did. If it's greater than the key at the root. The

Â floor of K is in the right subtree, if there is any key smaller than K in the

Â right subtree. So, in this case, there's no key smaller than G in the right

Â subtree. So therefore, the answer is E. So, our code has to check for these three

Â cases. And here's the code that does it. It's not that much code. It's just

Â complicated code to understand. So if we find our key, that's the floor. If we're

Â going to the left we find the floor, the one on the left. And in on the right we

Â have to do a, a little bit of tricky code to make sure that we return the floor on

Â the right subtree, if there's some tree there. If there's, if there's no node

Â there then, then, then we, we return the root itself. So, that's a, a

Â implementation that, that code is definitely tricky and a similar code for

Â ceiling. So now, what about operations like rank and select? How many keys are

Â there less than a given key? And, give us the seventh largest key to facilitate

Â implementing those operations and also size all we do is keep an extra field in

Â each node, which is the number of the nodes in the subtree rooted at that node.

Â So, this tree has got eight nodes in it. This subtree has six nodes in it and so

Â forth. And those counts are going to not only enable us to immediately implement

Â the size function, just return the count at the root but also, they'll give us good

Â implementations of rank and select. So, let's look at those now. So, we add

Â account field to every node and then to implement the size function well, if it's

Â null, we return zero. So a client might call us for a null tree or [cough] or an

Â empty tree. Otherwise we return, x.count, which is the number of nodes in that, in

Â that subtree by definition. The way we maintain, there's a number of ways we can

Â maintain the thing but the one that we'll adopt un iformly because it adapts to more

Â complicated situations is just before we're done with the put operation we'll

Â say, okay we've done all our work and before we return the pointer to the given

Â subtree we're going to take the size of what's on the left and the size of what's

Â on the right and add one for us and that's going to be our count. So, whether or not

Â there was a new node added we don't have to test for that this recursively takes

Â care of the problem of maintaining the size in every node when there's a new node

Â inserted. And, it also handles more general situations, as we'll see later on.

Â So, that's how to maintain size. So now, how do we implement rank? Well, it's a

Â little like floor. It's an easy recursive algorithm, but there are three cases. So

Â let's look at the, at the three cases. So, we want to know the number of keys less

Â than K. So [cough] we're going to have a recursive algorithm for our given key. So,

Â let's, one of the easy ones is, if our key is equal to the, if were [cough] to the,

Â the key at the current node then the number of keys less than our key is the

Â size of the left subtree of that node. So, if we're looking for the rank of E say,

Â how many keys are there less than E there's exactly two, that's by definition

Â in the data structure that's the number of keys that are less than E. So, that's that

Â one for rank. What about the [cough] starting at the root if we have the case

Â where E is less than S. So, the rank of E in this whole tree is the same as the rank

Â of E in the left subtree. So, there's that case and then if we're going to the right,

Â then we have to add one for the root and one for the left subtree of the root and

Â then find the rank of us on the right. So, that's an easy recursive algorithm for

Â finding out the rank. And it's definitely an instructive exercise to check that you

Â believe that, that method works. The other thing we h ave to do is iteration. And

Â iteration is a fundamental operation on tree structure. And it's based on so

Â called in-order traversal. And that's also a simple recursive algorithm. Traverse the

Â left subtree enqueue the key, traverse the right subtree. So, to iterate we're going

Â to maintain a queue of keys. And then, we're going to call this recursive

Â in-order [cough] method. And that method is going to add all the keys in the tree

Â to the queue. And then we'll just return that queue. And that's, a queue is an

Â iterable data structure, and the client can iterate that. And, in order, it's just

Â a simple recursive method. Put everybody to the left on the queue then put the root

Â on the queue, then put everybody to the right on the queue. And to believe this

Â method, you just have to think recursively and prove by induction that this in order

Â method puts all the keys in the data structure on the queue in their natural

Â order. First, it puts all the ones to the left on the queue. If that, that happens

Â in their natural order, then the next thing that has to appear is the key at the

Â root. And then if the ones on the right go in their natural order, and then, by

Â induction, they're all in their natural order. That's a very simple implementation

Â of an iterator for these symbol table with comparable keys. So we have to again prove

Â that property by induction. And that's easy to do. The diagram at the right gives

Â another simple way to look at it pictorially. All the keys that are smaller

Â on the left we are going to put them out, and then we put the key at the root and

Â then we put all the keys on the right out in order. And then that key is going to

Â have all those keys in order by induction. So, here's the operation summary for

Â ordered symbol table. And the quick summary is that every one of those

Â operations, while ordered iteration is optimal, it just gets them in linear time.

Â And all the res t of'em take time proportional to the height of the tree.

Â Now, if the, the keys are inserted in random order, we know that height by

Â analysis, is going to be proportional to log N. Or if it's some application where

Â the order of insertion of the keys is well modeled by random order and that's not

Â unusual at all. A binary search tree is a simple and extremely effective data

Â structure that can support all of these operations in a quickly, much better than

Â binary search in an ordered array which is not dynamic and slow for insertion. So,

Â that's a look at binary search tree implementations of ordered operations when

Â keys are comparable.

Â