So what I want to do next is test your
understanding about the search and
insertion procedures by asking you about
their running time. So of the following
four parameters of a search tree that
contains n different keys, which one
governs the worst case time of a search or
insertion. So the correct answer is the
third one. So, the heights of a search
tree governs the worst case time of the
search or of an insertion. Notice
that means merely knowing the number of
keys n is not enough to deduce what the
worst case search time is. You also have
to know something about the structure of
the tree. So, to see that, just let's
think about the two examples that we've
been running so far. One of which is nice
and balanced. And the other of which,
which contains exactly the same five keys
is super unbalanced, It's this crazy
linked list in effect. So, in any
search tree, the worst case time to do is
search or insertion is
proportional to the largest number of
pointers left to right child pointer that
you might have to follow to get from the
root all the way to a null pointer. Of course
in a successful search, you're going to
terminate before you encounter a null
pointer but in the worst case, you want
insertion you go all the way to a null
pointer. Now on the tree on the left
you're going to follow at most 3 such
pointers. So for example, if you're
searching for 2.5. You're going to follow
a left pointer followed by a right
pointer. By another pointer and that one
is going to be null. So we're going to
follow three pointers. On the other hand,
in the right tree, you might follow as
many as five pointers before that fifth
pointer is null. For example, if you
search for the key zero, you're going to
traverse five left pointers in a row and
then you're finally going to encounter the
null at the end. So, it is not constant
time certainly, you have to get to the
bottom of the tree. It's going to be from
proportional to logarithmic, logarithm in
the number of keys if you have a nicely
balanced binary search tree like this one
on the left. It's going to be proportional
to the number of keys n as in the fourth
answer if you have a really lousy
search tree like this one on the right and
in general. Search time or the insertion
time is going to be proportional to the
height. The largest number of hops we need
to take to get from the root to
the leaf of the tree. Let's move on to some more
operations that search tree support but
that, for example, the dynamics data
structures of heaps and hash tables do not.
So let's start with the minimum and
the maximum. So, by contrast and a heap
remember, you can choose one or the two.
You can either find the minimum, usually
you find the maximum easily but not both.
And the search tree is really easy to
find, either the min or the max. So, let's
start with the minimum. One way to think
of it is that you do a search for negative
infinity in the search tree. So, you
started the root. And you just keep
following left child pointers until you
run out, until you hit a null. And
whatever the last key that you visit has
to be the smallest key of the tree, right?
Because, think about it, suppose you
started the root. Supposed that the root
was not the minimum, then where is the
minimum got to be, It's got to be in the
left sub-tree so you follow the left
child pointer and then you just
repeat the argument. If you haven't
already found the minimum, where it's got
to be with respect to current place,
it's got to be in the left sub tree and
you just iterate until you can't go to the left
any further. So for example, in our
running search tree. You'll notice that if
we just keep following left child
pointers, we'll start at the three, we'll
go to the one, we'll try to go left from
the one. We'll hit a null pointer and
we'll return one and one is indeed the
minimum key in this tree. Now, given that
we've gone over how to compute the
minimum, no prizes to guess how we compute
the maximum. Of course, if we want to
compute the maximum instead of following
left child pointers we follow right child
pointers by symmetric reasoning as
guaranteed upon the largest key in the
tree. It's like searching for the key plus
infinity. Alright. So what about computing
the predecessor? So remember this means
you're given key in the tree, in the
element of the tree and you want to find
the next smallest element so for example
the predecessor of the three is two. The
predecessor of the two in this tree is the
one. The predecessor of the five is the
four. The predecessor of the four is the
three. So, here I'll be a little hand
wavy just in the interest of getting
through all of the operations in
reasonable amount of time but let me just
point out that there is one really easy
case and then there is one slightly
trickier case. So the easy case. Is
when the node with the key k has a
non-empty left sub tree. If that's the
case, then what you want is simply the
biggest element in this node left sub
tree. So, I'll leave it for you to prove
formally that this is indeed the
correct way to compute predecessors
for keys that do have a non-empty left sub
tree, let's just verify in our example
by going through the trees that have a
left sub tree and checking this is in
fact what we want. Now, if you look at it,
there's actually only two nodes that have
a non-empty left sub tree. The three has a
non-empty left sub tree and indeed the
largest key in the left sub tree three is
the two and that is the predecessor of the
three so that worked out fine. And then
the other node with a non-empty left subtree is the five
and it's left subtree is simply the element four
of course the maximum of that tree is also
four. And then you'll notice that is
indeed the predecessor of five in this
entire search tree. So, the trickier case
is what happens if you know the key with
no left subtree at all. Okay. So, what are
you going to do if you not in the
easy case, Well, given at this node with
key k, you only have three pointers and by
assumption, the left one is null so that's
not going to get you anywhere, now, the
right childpointer if you think about it
is totally pointless for computing
the predecessor. Remember, the predecessor
is going to be a key less than the given key
k. The right subtree by definition of a
search tree only has keys that are bigger
than k. So, it stands for reason to find
the predecessor we got to follow the
parent pointer. Maybe in fact more than
one parent pointer so to motivate exactly
how we're going to follow parent pointers,
let's look at a couple of examples in our
favorite search tree here on the right.
So, let's start with a node two. So, we
know we got to follow a parent
pointer. When we follow to this parent
pointer, we get to one and boom, one in
fact is two's predecessor in this tree so
that was really easy to computer two's
predecessor. It seemed that all we have to
do is follow the parent pointer. So, for
another example though which think about
the node four. Now, four when we follow
which parent pointer, we get to five and.
Five is not 4's predecessor, it's 4's
successor. What we wanted a key that is less
than where we started, we follow the
parent pointer and it was bigger. But, if
we follow one more parent pointer, then we
get to the three. So, from the two we
needed to follow one parent pointer, from
the four we needed to follow two parent
pointers. But the point is, you just need
to follow parent pointers until you get to
a node with key smaller than your own. And
at that point you can stop and that's
guaranteed to be the predecessor. So,
hopefully, you would find this intuitive.
I should say, I have definitely not
formally proved that this works and that
is a good exercise for those of you that
want to have a deeper understanding of
search trees and this magical search tree
property and all of the structure that it
grants you. The other thing I should
mention is another way to interpret the,
the terminating criteria. So what I've
said is you stop your search of parent
pointers as soon as you get to through
smaller than yours If you think it about
a little bit, you'll realize you'll get to
a key smaller than yours, the very first
time you take a left turn. So the very
first time that you go from a right child
to it's parent. Look at the example, when
we started from two, we took a left turn,
right? We went from upper link going
leftward To it's a right child of one, and
that's when we got to the predecessor in
just one step. By contrast when we started
from the four, our first step was to the
right. So, we got to a node
that was bigger than where we started for
five is four's left child which is going
to be smaller than five. But the first
time we took a left turn on the next step,
we got to a node that is not only smaller
than five but actually smaller from four,
smaller from the starting point. So, in
fact, you're going to see a key smaller
than your starting point at very first
time, you take a left turn, the very first
time you go from a node to a parent and in
fact, that node is that parent's right
child. So this is another statement which
I think is intuitive but which formally is
not totally obvious. And again I encourage
you to think carefully about why these two
descriptions of the terminating criteria
are exactly the same so it doesn't matter
if you stop when you first find a key
smaller than your starting point. It
doesn't matter if you first stop when you
follow a parent pointer that goes from a
node that's the right child of a node.
Either way you're going to stop at exactly
the same time so I encourage you to think
about why those are the exact same
stopping condition. A couple of other
details if you start from the unique node
that has no predecessor at all, you'll
never going to trigger this terminating
condition so for example if you start from
the node one in the search tree, not only
is the left subtree empty which says
you're suppose to start traversing parent
pointers but then when you traverse a
parent pointer, you only go to the right.
You never turn left and that's because
there is no predecessor so that's how you
detect that you're at the minimum of a
search tree. And then of course if you
wanted to be the successor of the key
instead of the predecessor, obviously you
just flip left and right through out this
entire description. So that's the high
level explanation of all of these
different ordering operations, minimum and
maximum predecessor and successor work in
a search tree. Let me ask you the same
question I asked you when we talked about
search in insertion. How long that these
operations take in the worst case? Well,
the answer is the same as it was before.
It's proportional to the height of the
tree and the explanation is exactly the
same as it was before. So to understand
the dependence on the height was just
focused on the maximum operation that has
the state within the question. The other
three operations, the running time is
proportional to the height in the worst
case for exactly the same reasons. So,
what is the max operation do when you
started the root and you just follow the
right child pointers until you run out
them so you hit null. So, you know, that
the running time is going to be no worse
in the longest such paths. It's particular
path from the root to essentially a
leaf. So instead we're going to have a
running time more than the height of the
tree, on the other hand for all you know.
The path from the root to the maximum key
might well be the longest one in the tree.
It might be the path that actually
determines the height of the search tree.
So, for example in our running unbalanced
example, that would be a bad tree for the
minimum operation If you look for the
minimum in this tree, then you have to
traverse every single pointer from five
all the way down to one. Of course there's
an analogious bad search tree for the
maximum operation where the one is the
root and the five is all the way down to the left. Another thing you can do is search
trees which mimics what you can do with
sorted arrays is you can print out all of
the keys in the sorted order in linear
time with constant time per element.
Obviously, in the sorted array this is
trivial. Use your for loop start ing at
the beginning at the array pointing up the
keys one at a time and there's a very
elegant recursive implementation for doing
the exact same thing in a search tree. And
this is known as an in order traversal of
binary search tree. So as always you begin
at the beginning namely at the root of the
search tree. And a little bit of notation
of which call, all of the search tree that
starts at r's left child t sub l and the
search tree routed at r's right child t
Sub r. In our running example of course
the root is three t sub l with
correspondent in the search tree
comprising only the elements one and two,
t sub r would correspond to the sub-tree
comprising only the elements five and
four. Now, remember we want to print out
the keys in increasing order. So in
particular, the first key we want to print
out is the smallest of them all. So it's
something we definitely don't want to do
is we don't want to first print out the
key at the root. For example in our search
tree example, the root's key is three, we
don't want to print that out first. We
want to print out the one first. So where
is the minimum lie? Well, by the search
tree property, it's got to lie in the left
subtree t sub l, So we're just going to
recurse on t Sub l. So by the magic of
recursion or if you prefer induction, what
re-cursing on t sub l is going to
accomplish is we're going to print out all
of the keys in t sub l in increasing order
from smallest to largest. Now that's
pretty cool because t sub l contains
exactly the keys that are smaller than the
key of the root. Remember that's the
search tree property. Everything bigger
than the root's key has to be in the left
sub tree. Everything bigger than the
root's key have to be in its right sub
tree. So in our concrete example of this
first recursive call is we're going to
print the keys one and then two. And now,
if you think about it it's the perfect
time to print out the key at the root,
right? we want to print out all the keys in
increasing order we've already done
everything less than the root's key Where
re-cursing and on the right hand side will
take you everything bigger in it so in
between the two recursive calls, this is
why it's called an in order traversal,
that's when we want to print out. R's key.
And clearly this works in our concrete example, the first recursive call print out one and two,
it's the perfect time to print out three and
then a recursive call of print out four
and five. And more generally, the
recursive call on there right subtree
will print out all of the keys bigger than
the roots key and increasing order again
by the magic of recursion or induction
So, the fact that the pseudo-code is
correct. The fact that the so-called
in-order traversal indeed print out the
keys in increasing order. This is a fairly
straightforward proof by induction. It's
very much in the spirit or the proofs by induction, correctness of divide and conquer
algorithms that we've discussed earlier in
the course. So what about the running time
of an in order traversal? The claim is
that the running time of this procedure is
linear. It's O of n where n is the number
of keys in the search tree. And the reason
is, there's exactly one recursive call for
each node of the tree and constant work is
done in each of those recursive calls. And
a little more detail, so what is the
in order] traversal do, It will print
out the keys in increasing. In particular
it prints out each key exactly once. Each
recursive call prints out exactly one key's
value. So there's exactly n recursive
calls and all of the recursive call does
is print one thing. So n recursive calls
constant time for each that gives us a
running time of O(n) overall. In most
data structures, deletion is the most
difficult operation and in search trees.
There are no exception. So let's get into
it and talk about how deletion works,
there are three different cases. So the
first order of business is to locate the
node that has the key k, locate
the node that we want to get rid off.
Right so for starters, maybe we're
trying to delete the key two from our
running example search tree. So the first
thing we need to do is figure out where it
is. So, there are three possibilities for
the number of children that a node in a
search tree might have and might have zero
children that might have one child
it might have two children, corresponding to
those three cases that the deletion
pseudo-code will also have three cases.
So, let's start with the happy case where
there's only zero children like in this
case where deleting the key 2
from the search tree. Then of course, we
can, without any reservations just delete
the node directly from the search tree,
Nothing can go wrong, there's no children
depending on that node. Then there is the
medium difficult case. This is where. The
node containing k has one child. An
example here would be, if we wanted to
delete five from the search tree so the
medium case is also not too bad. All you
got to do is splice out the node that you
want to delete. That creates a hole in the
tree but then that node, deleted node's
unique child assumes the previous position
of the deleted node. I can make a nerdy
joke about Shakespeare right here but I'll
refrain. For example, in our five node
search tree if we wanted to, let's say we
haven't actually deleted two out of this
one, if we wanted to delete the five. The
five when we take it out of the tree that
would leave a hole but then we just
replace the position previously held by five
by it's unique child four. And if you
think about it that works just fine in the
sense of that preserves the search tree
property. Remember the search tree
property says that everything in say, a
right subtree has to be bigger than
everything in the nodes key, so we've made
four the new right child of three but four
and any children that it might have were
always part of 3's right subtree so all
that stuff has got to be bigger than three
so there's no problem putting four and
possibly all of its descendants. as the
right child of three. The search tree
property is in fact retained. So, the
final difficult case then is when the node
being deleted has both of its children,
has two children. So, in our running
example with five nodes, this would only
transpire if you wanted to delete the
root, you want to delete the key three
from the tree. The problem, of course, is
that, you know, you can try ripping out
this node from the tree but then, there's
this hole and it's not clear that it's
going to work to promote either child.
Into that spot. You might stare at our
example search tree and try to understand
what would happen if you try to bring one
up to be the root or if you try to bring
five up to be the root. Problems would
happen, that's what would happen. This is an
interesting contrast to when we faced the
same issue with heaps. Because the heap
property in some sense is perhaps less
stringent, there we didn't have an issue.
When we wanted to delete something with
two children, we just promoted the smaller
of the two children assuming we wanted to
export and extract them in operation.
Here, we're going to have to work a little
harder. In fact this is going to be really
neat trick. We're going to do something
that reduces the case of two children to
the previously solved cases of zero or one
children. So here's a very sneaky way we
identify a node to which we can apply
either the case zero or the case one
operation. What we're going to do is we're
going to. Start from k and we're going to
compute k's predecessor. Remember, this is
the next smallest key in the tree. So, for
example, the predecessor of the key three
is two. That's the next smallest key in
the tree. In general, let's call case
predecessor l. Now, this might seem
complicated. We're trying to implement one
tree operation and with deletion and all
of a sudden we're invoking a different
tree operation predecessor which we
covered a couple of slides ago. And to
some extent you're right you know,
delete, this is a nontrivial operation.
But, it's not quite as bad as you think
for the following reason. When we compute
this predecessor, we're actually in the
easy case of the predecessor operation
conceptually . Remember how do you get a
predecessor, well it depends. What does it
depend on? It depends on whether you got a
non-empty left sub tree or not. If you
don't have a non-empty left sub tree,
that's how you got to those things and
follow a parent pointers upward until you
find a key which is smaller than what
you've started. But. If you've got a left
sub tree, then it's easy. You just find
the maximum of the left sub tree and
that's got to be the predecessor and
remember, finding maximum are easy. All
you have to do is follow right child
pointers until you can't anymore. Now,
what's cool is because we only bother with
this predecessor computation in the case
where case k's node has both children. We only
have to do it in the case where it has a
non-empty left subtree. So really when we
say compute k's predecessor l. All you
got to do is follow k's left child. That's
not null because it has both children. And
then, follow right child pointers until
you can't anymore and that's the
predecessor. Now, here's the fairly
brilliant parts of the way you do
implement deletion in the search tree
which is you swap these two keys, k and l.
So for example in our running search tree,
instead of this three at the root we would
put a two there and instead of this two at
the leaf, it would put a three there. And
the first time you see this, it just
strikes you as a little crazy, maybe even
cheating or just simply disregarding the
roles of, rules of search trees. And
actually, it is like check out what happen
to our example search tree. We swap the
three and the two and this is not a search
tree anymore, right? So, we have this three
which is in two left sub tree and a three
is bigger than the two and that is not
allowed. That is violation of the search
tree property. Oops. So, how can we get
away with this and we get away with this
is we're going to delete three anyway. So,
we're going to wind up with the search
tree at the end of the day. So we may have
messed up the search tree property a
little bit but we've swapped k in the
position where its really easy to get rid of.
Well how did we compute case
predecessor l? Ultimately that was the
result of a maximum computation which
involves following right child pointers
until you get stuck and l was the place we
got stuck. What's the meaning to get
stuck? It means l's right child pointer is
null. It does not have two children. In
particular it does not have a right child.
Once we swap k in the l's old position, k
now does not have a right child. It may or
may not have a left child and the example
on the right it does not have a left child
either in this new position but in general
it might have a left child. But, it
definitely doesn't have a right child.
Because that was a position at which a
maximum computation got stuck. And if we
want to delete a node that has only zero
or one child, well that we know how to do.
That we covered in the last slide. Either
you just delete it, that's what we do in
the running example here. Or in the case
where k's new node does have a left child,
you would do the splice out operation. So
you would rip out the node that contains k
and that the unique child of that node
would assume the previous position of that
node. Now an exercise which I'm not going
to do here but I strongly encourage you
think through in the privacy of your own
home, is that , in fact, this deletion
operation retains the search tree
property. So roughly speaking, when you do
the swap, you can violate the search tree
property as we see in this example but all
of the violations involved the node
you're about to delete so once you delete
that node, there's no other violations of
the search property so bingo, you're left
with the search tree. The running time
this time no get, no prizes for guessing
what it is because it's basically just one
of these predecessor computations plus
some pointer rewiring just like the
predecessor and search is going to be
governed by the height of the tree. So let
me just say a little bit about the
final two operations mentioned earlier,
select and rank. Remember select is just
a selection problem. I'll give you an
order statistic like seventeen and I want you
to return the seventeenth smallest key in
the tree. Rank is I give you a key value
and I want to know how many keys in the
tree are less than or equal to that value.
So, to implement these operations
efficiently, we actually need one small
new idea which is to augment binary search
trees with additional information at each
node. So, now the search tree will contain
not just a key but also information about
the tree itself. So, this idea is often
called augmenting your data structure and
perhaps the most canonical augmentation of
the search tree like these is to keep track
in each node, not just to the key value
but also over the population of tree nodes
in the sub tree that is rooted there. So
let's call this size of x. Which is the
number of tree nodes in the subtree rooted
at x. So to make sure you know what I
mean, let me just tell you what the size
field should be for each of the five nodes
in our running search tree example. So
again example, we're thinking about how
many nodes are in the subtree rooted given
node. Or equivalently, following child
pointers from that node how many different
tree nodes can you reach? So from the root
of course, you can reach everybody.
Everybody's in the tree rooted at the root
so the size there is five. By contrast,
you start at the node one, well, you can
get to the one or you can follow the right
child pointer to get to the two. So at the
one. The size would be two and the node
with the key value five for the same
reason, the size would be two. At the two
leaves, the subtree where the leaf is just
the leaf itself so there, the size would
be one. There's an easy way to compute the
size of a given node once you know the
size of its two sub trees. So, if the
given node in the search tree has children
y and z, then, how many nodes are there in
the sub tree rooted x, well, there's those
that are rooted at y. There are those in
the left sub tree, there are those that
are reachable from z that is there are
the children that are also children of z
and then there's x itself. Now in
general, whenever you augment a data
structure, and this is something we'll
talk about again when we discuss red black
trees, you've got to pay the piper. So,
the extra data that you maintain it might
be useful for speeding up certain
operations. But whenever you have
operations that modify the tree,
specifically insertion and deletion, you
have to take care to keep that extra data
valid, keep it maintained. Now, in the
case of the subtree sizes, there are quite
straightforward to maintain under
insertion and deletion without affecting the
running time of insertion and deletion
very much but that's something you should
always think about offline. For example,
when you perform an insertion remember how
that works. You do as, essentially a
search. You follow left and right child
pointers down to the bottom of the tree
until you get a null pointer then that's
where you stick a new node. Now what you
have to do is you have to trace back up
that path, all of the ancestors of the new
node you just inserted and increment their
subtree sizes by one. So let's wrap up
this video by showing you how to implement
the selection procedure given an nth order
statistic in a search tree that's been
augmented so that at every node you know
the size of a subtree rooted at that node.
Well of course as always you start at the
beginning which in the search tree is the
root. And let's say the root has a
sub-children y and z. Y or z could be
null, that's no problem. We just think of
the size of a null node as being zero.
Now, what's the search tree property? It
says, every, these keys that are less than
the keys sorted x are precisely the one
that are in the left sub tree of x. The
keys in the tree, they are bigger than the
key to x or precisely the ones that you're
going to find in x's right sub tree. So,
supposed we're asked to find the
seventeenth order statistic in the search
three. Seventeenth smallest key that's
stored in the tree, Where is it going to
be? Where should we look? Well, it's going
to depend on the structure of the tree and
in fact it's going to depend on the
subtree sizes. This is exactly. We're
keeping track of them so we can quickly
make decisions about how to navigate
through the tree. So for a simple example,
suppose that x's left subtree contains say
25 keys. So remember y know locally
exactly what the population of the subtree
is so in constant time from x, we can
figure out how many keys are in y subtree
let's say its 25. Now, by the defining
property of search trees, these are the 25
smallest keys anywhere in the tree. Right,
x is bigger than all of them. Everything
in x's right subtree is bigger than all of
them. So, the 25 smallest order
statistics are all in the subtree rooted
to y, clearly that where we should recurse. Clearly
that's where the answer lies so in
recursing the subtree root of y and then
we are again looking for the seventeenth
order statistic in this new smaller search
tree. On the other supposed when we
started x and we look, we ask why. How,
how many nodes are there in your subtree.
Maybe y locally have stored the number
twelve. So there's only twelve things in
x's left subtree. Well, okay, x itself is
bigger than all of them so that's going
to, x is going to be the thirteenth
biggest order statistic. It's going to be
the thirteenth biggest element in the
tree. Everything else is in the right sub
tree. So, in particular, the seventeenth
order statistic is going to be in
the right sub tree so we're going to
recurse in the rght sub tree. Now, what
are we looking for, we're not looking for
the seventeenth order statistic anymore. The
twelve smallest things all in x's sub tree, 
x itself is the thirteenth
smallest so we are looking for the fourth
smallest of what remains. So, the
recursion is very much along the lines of
what we did in the divide and conquer
selection algorithms earlier in the
course. So to fill in some more details,
let's let a denote the subtree size at y.
And if it happens that x has no left
child, we'll, the point would be a to be
zero. So the super lucky case is when
there's exactly i - 1 nodes in the left
subtree. That means the root here, x is
itself the ith order statistic remember it's bigger
than everything In it's left subtree it's
smaller than everything in its right
subtree.  But, in the general case we're
going to be recursing either on the left
subtree or in the right subtree. We
recurse on the left subtree when its
population is large enough that we
guarantee it and compasses the ith order
statistic. And that happens exactly when it
sides is at least i. That's because the left
subtree has the smallest keys that are
anywhere in the search tree. And in the
final case when the left subtree is so
small that the only does it not contain
the ith order statistic but also x is
too small to be an ith order statistic then we
recurse in the right subtree knowing that
we have thrown away a + 1, the a + 1
smallest key values anywhere in the
original tree. So, correctness of this
procedure is pretty much exactly the same
as the inducted correctness for the
selection algorithms we've discussed
earlier in effect to the root of the
search tree is acting as a pivot element
with everything in the left sub tree being
less than the root everything in the right
sub tree being greater than the element in
the root so that's why the recursion is
correct. As far as the running time, I
hope it's evident from the pseudo code
that we do constant time each time they
recurse. How many times can we recurse
when we keep moving down the tree that
maximum number of times we can move down
the tree is proportional to the height of
the tree. So, it was again is proportional
to the height. So, that's the select
operation, There is an analogous way to
write the rank operation. Remember, this
is where you're given the key value and
you want to count up the number of stored
keys that are less than or equal to that
target value, Again, you use this
augmented search trees and again, you can
get running time porportional to the height
and I encourage you to think through
the details of how implement rank
offline.