So, in this video, we'll go over the
basics behind implementing binary search
trees. We are not going to focus on the
balance aspect in this video that will be
discussed in later videos and we are going
to talk about things which are true for
binary search trees on general, balanced
or otherwise. But let's just recall, you
know, why are we doing this, you know,
what is the raison d'être of this data
structure, the balance version of the
binary search tree and basically, its a
dynamic version of a sorted array. So,
that's pretty much everything you can do
on a sorted array, maybe in slightly more
expensive time. They are still
really fast but in addition to this
dynamic, it accommodates insertions and
deletions. So, remember, if you want to
keep a sorted array data structure, every
time you insert, every time you delete,
you're probably going to wind up paying a
linear factor which is way too
expensive in most applications. By
contrast with the search tree, a balanced
version, you can insert and delete a
logarithmic time in the number of keys in
the tree. And moreover, you can do stuff
like search in logarithmic time, no more
expensive than binary search on a sorted
array and also you can sort of say the
selection problem in the special cases,
the minimum or maximum. Okay, it's not
constant time like in a sorted array but
still logarithmic pretty good and in
addition, you can print out all of the
keys from smallest to largest and in
linear time, constant time per element
just like you could with the linear scan
through a sorted array. So, that's what
they're good for. Everything a sorted
array can do more or less plus insertions
and deletions everything in logarithmic
time. So, how are search trees organized?
And again, what I'm going to say in the
rest of this video is true both for
balanced and unbalanced search trees.
We're going to worry about the balancing
aspect in the later videos. Alright, so,
let me tell you the key ingredients in a
binary search tree. Let me also just draw
a simple cartoon example in the upper
right part of the slide. So, this one to
one correspondence between nodes of the
tree and keys that are being stored. And
as usual in our data structure discussions
we're going to act as if the only thing
that we care about, the only thing that
exists at each node is this key when
generally, this associated data that you
really care about. So, each node in the
tree will generally contain both the key
plus a pointer to some data structure that
has more information. Maybe the key is the
employee ID number, and then there's a
pointer to lots of other information about
that employee. Now, in addition to the
nodes, you have to have links amongst the
nodes and there's a lot of different ways
to do the exact implementation of the
pointers that connect the node of the tree
together but the video I'm just going to
keep is straightforward as possible and
we're just going to assume that in each
node, there's three pointers. One to a
left child, another one to the right child
and then the third pointer which points to
the parent. Now, of course, some of these
pointers can be null and in fact in the
five node binary search tree I've drawn on
the right for each of the five nodes, at
least one of these three pointers is null.
So, for example, for the node with key one
it has a null left child pointer, there was
no left child. It's the right child
pointer going to point to the node with
key two and the parent pointer was going
to a node that has key three. Similarly
three is going to have a null parent pointer
and the root node in this case, three is a
unique node but has a null parent pointer.
Here the node with key value three, of
course, has a left child pointer points to
one and has a right child pointer that
points to five. Now, here is the most
fundamental property of search trees.
Let's just go ahead and call it the Search
Tree Property. So, the search tree
property asserts the following condition
at every single node of the search tree.
If the node has some key value then all of
the keys stored in the left subtree should
be less than that key. And similarly, all
of the keys stored in the right subtree
should be bigger than that key. So, if we
have some node who's stored key value is x
and this is somewhere, you know, say deep
in the middle of the tree so upward we
think of as being toward the root. And
then if we think about all the nodes that
are reachable, after following the left
child pointer from x, that's the left
subtree. And similarly, the right subtree
being everything reachable via the right
child pointer from x, it should be the
case that all keys in the left subtree are
less than x and all keys in the right
subtree are bigger than x. And again, I
want to emphasize this property holds not
just to the root but at every single node
in the tree. I've defined the search to a
property assuming that all of the keys are
distinct, that's why I wrote strictly less
than in the left sub tree and strictly
bigger than in the right subtree. But
search trees can easily accommodate
duplicate keys as well. We just have to
have some convention about how you handle
ties. So, for example, you could say that
everything in the left subtree is less
than or equal to the key at that node and
then everything in the right subtree
should be strictly bigger than that node.
That works fine as well. So, if this is
the first time you've ever heard of the
search tree property, maybe at first blush
it seems a little arbitrary. It seems like
I pulled it out of thin air but actually,
you would have reversed engineer this property
if you sat down and thought about what
property would make search really easy in
a data structure. The point is, the search
tree property tells you exactly where to
look for some given key. So, looking ahead
a little bit, stealing my fire from a
slide to come, suppose you were looking
for say, a key 23, and you started the
root and the root is seventeen. The point
of the search tree property is you know
where 23 has to be. If the root is
seventeen, you're looking to 23, if it's
in the tree, no way is it in the left
subtree, it's got to be in the right
subtree. So, you can just follow the right
child pointer and forget about the left
subtree for the rest of the search. This
is very much in the spirit of binary
search where you start in the middle of
the array and again, you compare what
you're looking for to what's in the middle
and either way, you can recurse on one of
the two sides forgetting forevermore about
the other half of the array and that's
exactly the point of the search tree
property. We're going to have to search
from root on down, the search tree
property guarantees we have a unique
direction to go next and we never have to
worry about any of the stuff that we don't
see. We can also draw a very loose analogy
with our discussion of heaps and may
recall heaps were also logically, we
thought of them as a tree even though they
are implemented as an array. And heaps
have some heap property and if you go back
to review the heap property, you'll find
that this is not the same thing as the
search three property. These are two
different properties and that's going to
trying to make different things easy. Back
when we talk about heaps, the property was
that this is for the extract min version.
Parents always have to be smaller than
their children. That's different than the
search tree property which says stuff to the
left, that's smaller than you, stuff to
the right is bigger than you. And heaps,
we have the heap property so that
identifying the minimum value was trivial.
It was guaranteed to be at the root. Heaps
are designed so that you can find the
minimum easily. Search trees are, are
defined so that you can search easily
that's why, you have this different search
tree property. If you want to get smaller,
you go left. If you want to get bigger you
go right. One point that's important to
understand early, and this will be
particularly relevant once we did, once we
try to enforce balancing in our subsequent
videos is that, for a given set of keys,
you can have a lot of different search
trees. On the previous slide , I drew one
search tree containing the key values one,
two, three, four, five. Let me redraw that
exact same search tree here. If you stare
to this tree a little while you'll agree
that in fact that every single node of
this tree, all of the things in the left
subtree are smaller, all of the things in
the right subtree are bigger. However, let
me show you another valid binary search
tree with the exact same sets of keys. So,
in the second search three, the root is
five, the maximum value. And everybody has
no right children, only the left children
are populated and that goes five, four,
three, two, one in descending order. If
you check here again, it has the property
that at every node, everything in the left
subtree is smaller. Everything in the
right subtree, in this case, empty, is
bigger. So, extrapolating from these two
cartoon examples, we surmised that for
a given set of n keys, search trees that
contain these keys could vary in height
anywhere from the best case scenario of a
perfectly balance binary tree which just
going to have logarithmic height to the
worst case of one of these link list like
chain which is going to be linear in the
number of keys n. And so just to remind
you the height of a search tree which is
also sometimes called the depth is just
the longest number of hops it ever take to
get to from a root to a leaf. So, in the
first search tree, here the height is two
and then the second search tree, the
height is four. If the search tree is
perfectly arranged with the number of
nodes essentially doubling at every level,
then the depth is you're going to run out
of nodes around the depth of log2n. And in
general, if you have a chain of n keys
that that's going to be n - 1 but we'll
just call it n amongst friends. So, now
that we understand the basic structure of
binary search trees, we can actually talk
about how to implement all of the
operations that they support. So, as we go
through most of the supported operations
one at a time, I'm just going to give you
a really high level description. It should
be enough for you to code up on
implementation if you want or as usual, if
you want more details or actual working
code, you can check on the web or in one
of the number of good programming or
algorithms textbooks. So, let's start with
really the primary operation which is
search. Searching, we've really already
discussed how it's done when we discuss
the search tree property. Again, the
search tree property makes it obvious how
to look for something in a search tree.
Pretty much you just follow your nose
you have no other choice. So, you started
the root, it's the obvious place to start.
If you're lucky, the root is what you are
looking for and then you stop and then you
return to root. More likely, the root is
either bigger than or less than the key
that you're looking for. Now, if the key
is smaller, the key you are looking for is
smaller than the key of the root, where
you're going to look? Well, the search
tree property says, if it's in the tree,
it's got to be in the left subtree so you
follow the left sub child pointer. If the
key you're looking for is bigger than the
key at the root, where is it got to be?
Got to be in the right subtree. So, you're
just going to recurse on the right
subtree. So, in this example, if you're
searching for, say the key two, obviously
you're going to go left from the root. If
you're searching for the key four,
obviously you're going to go right from
the root. So, how can the search
terminate? Well, it can terminate in one
of two ways. First of all, you might find
what you're looking for so in this
example, if you search for four, you're
going to traverse to right child pointer
then a left child pointer and then boom,
you're at the four and you return
successfully. The other way the search can
terminate is with a null pointer. So, in
this example, suppose you were looking for
a node with key six, what would happen?
Well, you start at the root, three is too
small so you go to the right. You get to
five, five is still too small cuz you're
looking for six so you try to go right but
the right child pointer is null. And that
means six is not in the tree. If there was
anywhere in the tree, it had to be to the
right of the three, it had to be to the
right of the five but you tried it and you
ran on the pointers so the six isn't
there. And you return correctly with an
unsuccessful search. Next, let's discuss
the insert operation which really is just
a simple piggy backing on the search that
we just described. So, for simplicity the
first think about the case where there are
no duplicate keys. The first thing to do
on this insertion is search for the key k.
Now, because there are no duplicates, this
search will not succeed. This key k is not
yet in the tree. So, for example, in the
picture on the right, we might think about
trying to insert the key six. What's going
to happen when we search for six, we
follow a right child pointer. We go from
three to five and then we try to spot
another one and make it stuck. There's a
null pointer going to the right of five.
Then when this unsuccessful search
terminates at a null pointer, we just rewire
that pointer to point to a node with this
new key k. So, if you want to permit
duplicates from the data structure, you
got to tweak the code and insert a little
bit but really barely at all. You just
need some convention for handling the case
when you do in counter the key that we are
about to insert. So, for example, if the
current note has the key equal to the one
you're inserting, you could have the
convention that you always continue on the
left subtree and then you continue the
search as usual again, eventually
terminating at a null pointer and you stick
the new inserted node you rewire to null
pointer to point to it. One good exercise
for you to think through which I'm not
going to say more about here is that when
you insert a new node, you retain the
search tree property. That is if you start
with the search tree, you start within
tree where at every node stuff to the left
is smaller, the stuff to the right is
bigger. You insert something and you
follow this procedure. You will still have
the search tree property after this new
node has been inserted. That's something
for you to think through.