In this sequence of videos, we'll discuss
our last but not least data structure
namely the Balanced Binary Search Tree.
Like our discussion of other data
structures we'll begin with the what. That
is we'll take the client's perspective and
we'll ask what operations are supported by
this data structure, what can you actually
use it for? Then we'll move on to the how
and the why. We'll peer under the hood of
the data structure and look at how it's
actually implemented and then
understanding the implementation to
understand why the operations have the
running times that they do. So what is a
Balanced Binary Search Tree good for?
Well, I recommend thinking about it as a
dynamic version of a sorted array. That
is, if you have data store in a Balanced
Binary Search Tree, you can do pretty much
anything on the data that you could if it
was just the static sorted array. But in
addition, the data structure can
accommodate insertions and deletions. You
can accommodate a dynamic set of data that
you're storing overtime. So to motivate
the operations that a Balanced Binary
Search Tree supports, let's just start
with the sorted array and look at some of
the things you can easily do with data
that happens to be stored in such a way.
So let's think about an array that has
numerical data although, generally as
we've said, in data structures is usually
associated other data that's what you
actually care about and the numbers are
just some unique identifier for each of
the records. So these might be an employee
ID number, social security numbers, packet
ID numbers and network contacts, etcetera.
So what are some things that are easy to
do given that your data is stored as a
sorted array, most a bunch of things?
First of all, you can search and recall
that searching in a sorted array is
generally done using binary search so this
is how we used to look up phone numbers
when we have physical phone books. You'd
start in the middle of the phone book, if
the name you were looking for was less
than the midpoint, you recurse on the
left hand side, otherwise you'd recurse
on the right hand side. As we discussed
back in the Master Method Lectures long ago,
this is going to run in logarithmic time.
Roughly speaking, every time you recurse,
you've thrown out half of the array so
you're guaranteed to terminate within a
logarithmic number of iterations so binary
search is logarithmic search time.
Something else we discussed in previous
lectures is the selection problem. So
previously, we discussed this in much
harder context of unsorted arrays.
Remember, the selection problem in
addition to array you're given in order
statistic. So, if your order statistic
that your target is seventeen, that means
you're looking for the seventeenth
smallest number that's stored in the
array. So in previous lectures, we worked
very hard to get a linear time algorithm
for this problem in unsorted arrays. Now,
in a sorted array, you want to know the
seventeenth smallest element in the array.
Pretty easy problem, just return whatever
element happens to be in the seventeenth
position of the array since the array is sorted,
that's where it is so no problem. It's
already sorted constant time, you can
solve the selection problem. Of course,
two special cases of the selection problem
are finding the minimum element of the
array. That's just if the order statistic
problem with i = 1and the maximum
element, that's just i = n. So this just
corresponds to returning the element
that's in the first position and the last
position of the array respectively. Well
let's do some more brainstorming. What
other operations could we implement on a
sorted array? Well here's a couple more.
So there are operations called the
Predecessor and Successor operations. And
so the way these work is, you start with
one element. So, say you start with a
pointer to the 23, and you want to know
where in this array is the next smallest
element. That's the predecessor query and
the successor operation returns the next
largest element in the array. So the
predecessor of the 23 is the seventeen,
the successor of the 23 would be the 30.
And again in a sorted array, these are
trivial, right? You just know that
predecessors just one position back in the
array, the successor is one position
forward. So given a pointer to the 23, you
can return to 17 or the 30 in
constant time. What else? Well, how about
the rank operation? So we haven't
discussed this operation in the past. So
what rank is, this has for how many key
stored in the data structure are less than
or equal to a given key. So for example,
the rank of 23 would be equal to 6.
Because 6 of the 8 elements in the array are less
 than or equal to 23. And if you think about it,
implementing the rank operation is really
no harder than implementing search. All
you do is search for the given key and
wherever it is search terminates in the
array. You just look at the position in
the array and boom, that's the rank of
that element. So for example, if you do a
binary search for 23 and then when you
terminates, you discover it is, they're in
position number six then you know the rank
is six. If you do an unsuccessful search,
say you search for 21, well then you get
stuck in between the 17 and the 23,
and at that point you can conclude that
the rank of 21 in this array is five. Let
me just wrap up the list with the final
operation which is trivial to implement in
the sorted array. Namely, you can output
or print say the stored keys in sorted
order let's say from smallest to largest.
And naturally, all you do here is a single
scan from left to right through the array,
outputting whatever element you see next.
The time required is constant per element
or linear overall. So that's a quite
impressive list of supported operations.
Could you really be so greedy as to want
still more from our data structure? Well
yeah, certainly. We definitely want more
than just what we have on the slide. The
reason being, these are operations that
operate on a static data set which is not
changing overtime. But the world in
general is dynamic. For example, if you
are running a company and keeping track of
the employees, sometimes you get new
employees, sometimes employees leave.
That is one of the data structure that
not only supports these kinds of
operations but also, insertions and
deletions. Now of course it's not that
it's impossible to implement insert or
delete in a sorted array, it's just that
they're going to run way too slow. In
general, you have to copy over a linear
amount of stuff on an insertion or
deletion if you want to maintain the
sorted array property. So this linear time
performance when insertion and deletion is
unacceptable unless you barely ever do
those operations. So, the raison d'etre 
of the Balanced Binary Search Tree
is to implement this exact same set
of operations just as rich as that's
supported by a sorted array but in
addition, insertions and deletions. Now, a
few of these operations won't be quite as
fast or we have to give up a little bit
instead of constant time, the one in
logarithmic time and we still got
logarithmic time for all of these 
operations, linear time for outputting the
elements in sort of order plus, we'll be
able to insert and delete in logarithmic
time so let me just spell that out in a
little more detail. So, a Balanced Binary
Search Tree will act like a sorted array
plus, it will have fast,  meaning
logarithmic time inserts and deletes. So
let's go ahead and spell out all of those
operations. So search is going to run in
O(log n) time, just like before. Select runs
in constant time in a sorted array and
here it's going to take logarithmic, so
we'll give up a little bit on the
selection problem but we'll still be able
to do it quite quickly. Even on the
special cases of finding the minimum or
finding the maximum in our, in our data
structure, we're going to need logarithmic
time in general. Same thing for finding
predecessors and successors they're not,
they're no longer constant time, they go
with logarithmic. Rank took as logarithmic
time and the, even the sorted array
version and that will remain logarithmic
here. As we'll see, we lose essentially
nothing over the sorted array, if we want
to output the key values in sorted order
say from smallest to largest. And
crucially, we have two more fast
operations compared to the sorted array of
data structure. We can insert stuff so if
you hire a new employee, you can insert
them into your data structure. If an
employee decides to leave, you can remove
them from the data structure. You do not
have to spend linear time like you did for
sort of array, you only have to spend the
logarithmic time whereas always n is the
number of keys being stored in the data
structure. So the key takeaway here is
that, if you have data and it has keys
which come from a totally ordered set
like, say numeric keys, then a Balanced
Binary Search Tree supports a very rich
collection of operations. So if you
anticipate doing a lot of different
processing using the ordering information
of all of these keys, then you really
might want to consider a Balanced Binary
Search Tree to maintain them. Well then,
keep in mind though is that we have seen a
couple of other data structures which
don't do quite as much as balanced binary
search trees but what they do, they do
better. We already, we just discussed in
the last slide of the sorted array. So, if
you have a static data set, you don't need
inserts and deletes. Well then by all
means, don't bother with Balanced Binary
Search Tree that use a sorted array
because it will do everything super fast.
But, we also sought through dynamic data
structures which don't do as much but do
it, but what they do, they do very well.
So, we saw a heap, so what the heap is
good for is it's just as dynamic as a
search tree. It allows insertions and
deletions both in logarithmic time. And in
addition, it keeps track of the minimum
element or the maximum element. Remember
in a heap, you can choose whether you want
to keep track of the minimum or keep track
of the maximum but unlike in a search
tree, a heap does not simultaneously keep
track of the minimum and the maximum. So
if you just need those three operations,
insertions, deletions and remembering the
smallest, and this would be the case for
example in a priority queue or scheduling
application as discussed in the heap
videos. Then, a Binary Search Tree is over
kill. You might want to consider a heap
instead. In fact, the benefits of a heap
don't show up in the big O notation here
both have logarithmic operation time but
the constant factors both in space and
time are going to be faster with a heap
then with a Balanced Binary Search Tree.
The other dynamic data structure that we
discussed is a hash table. And what hash
tables are really, really good at is
handling insertions and searches, that is
look ups. Some, sometimes, depending on the 
implementation also handle deletions
really well also. So, if you don't
actually need to remember things like
minima, maxima or remember ordering
information on the keys, you just have to
remember what's there and what's not. Then
the data structure of choice is definitely
the hash table, not the balance binary
search tree. Again, the Balance Binary Search
Tree would be fine and we'd give you
logarithmic look up time but it's kind of
over kill for the problem. All you need is
fast look ups. A hash table recall will
give you constant time look ups. So that
will be a noticeable win over the Balanced
Binary Search Tree. But if you want a very
rich set of operations for processing your
data. Then, the Balanced Binary Search
Tree could be the optimal data structure
for your needs.