Speaker: All right, next let's talk about binary trees,
and binary search trees in particular.
This is a sample of what one might look like.
So instead of having a next and a previous pointer
pointing to the next and previous things in the list,
a tree is well, a tree structure.
So, the idea here is that every element
instead has a left and a right child pointer.
So we have the ability
to work our way down through this tree,
looking at the left and right children of each note
as we work our way down.
Now, if left and right are ordered,
meaning that things that are less than the thing
that I'm looking at go to the left,
and things that are greater than,
go to the right.
Then we call this a binary search tree
because it is an ordered binary tree.
And this is very useful for search. Right?
Now less than and greater than
doesn't mean that it has to be a number necessarily.
It just means that we have to have some consistent way
of saying, well, this value is greater than,
or less than this value. Maybe that's based on, you know,
alphabetical sort of strings or something like that.
It doesn't have to be a number necessarily.
So access in this case, is log(n). Why is that?
Well, if we have a perfectly balanced binary tree,
you can see that as we work our way down,
we're basically dividing our search space in half
every time.
So we start off with a half of the stuff on the left,
and half of the stuff on the right.
As soon as we pick a direction there,
because we know the thing we're looking for
is either less than, or greater than
the thing at the top of the tree.
We've instantly cut our search space in half.
And as we work our way down to the next level,
we do it again. Right?
So, here we would say, okay, well,
the thing I'm looking for is either less than,
or greater than this thing that I'm at,
I'm going to pick one direction and now I've again,
cut my search space in half yet again.
So we've gone from the entire search space,
to half of the search space,
to half of half of the search space.
And I could keep on going.
That is a logarithmic relationship,
which is why we say that access
is a O{log(n)} on average.
However,
there was a worst case scenario here
that you need to know about as well.
So, if I were to insert things into a binary search tree
in sorted order,
this would degenerate to a link list.
And that's going to be O(n),
as you might recall. Think about it, right?
If I like start with the number one and I answer it,
the number two, that's going to go to the right.
And if I then insert the number three,
that will go to the right again,
number four would go to the right again.
Five would go to the right again.
So, if I'm inserting things in sorted order,
I'm just going to end up with a singly linked list.
And that's not a particularly efficient structure
for searching for things.
So, it's good to know, that log(n)
represents the best case scenario, or the average scenarios,
how we say it in computer science world.
But O(n) is really the worst case scenario.
So in practical terms, it's good to know that, right?
Especially if you're dealing with sorta data
from the get-go.
So, sometimes theory and reality are a little bit different,
and it's good to speak to that.
Insertions and deletions are also log(n) again,
in the best case, and O(n) in the worst case.
Because you have to do a search to find out
how you're going to rearrange things. All right.
So, really no different there.
So, sometimes you'll see implementations
of binary search trees, where they are self-balancing.
So there are algorithms out there
that will rearrange the tree.
As you insert things into it automatically,
to try to keep it balanced.
This is useful in situations
where you're not doing a lot of inserts,
or maybe you just do the inserts upfront,
but what you're really doing quickly and at massive scale
are those lookups later on.
So if you really want to optimize for fast look-ups,
a self-balancing binary tree might be the way to go.
So, mostly this is used in cases
where you need to do an in-order traversal
of the stuff that you're putting in.
So it is possible to write a pretty simple
recursive algorithm that goes through everything
in a binary search tree and prints them out in sorted order.
You basically just work your way down all the way
to the left and go up a step, go to the right, you know,
and just recursively go back up, and just go through,
and search through as you get things in sorted order.
So, this is not a coding interview class.
We're talking about design interviews,
but a very common coding question
is implement a binary search tree in order traversal.
And that's something that's easily done using recursion.
So, if you want a little practice for your coding skills,
that's a good one to try.
And an incredibly useful,
and incredibly common data structure
in the world of system design, is the hash table.
Why is that?
It allows us to take a key that we're looking for
that has some value, some data associated with it,
and very quickly figure out where that data is stored.
So in the case of a hash table,
that's just a data structure sitting on one machine.
We might have some sort of a hash function
applied to our keys,
that maps those hash functions to a bucket of some sort.
So we have some fixed number of buckets
that we're storing stuff within.
And our hash function allows you to very quickly
through a single mathematical operation,
map that key to which bucket
that keys data is stored within.
So, in this particular example here,
the key A is being mapped to bucket number one,
through that hash function. So is key C somehow.
So that also maps to bucket one.
You can have less buckets than keys.
In fact, usually you will.
B might be mapped to the second one,
and D might be mapped to the third one.
So, once we actually know what bucket we're in,
we will search that bucket for the specific key
that we're looking for and its value.
So if it's more than one thing,
we might have to do a little bit of a traversal
to find it within that bucket.
But the idea is that we split this up
in such a way that these individual buckets
don't have a whole lot of data to go through,
to look, to look at.
So they can be very, very efficient.
Now, when you do have this case where a more than one key
points to the same bucket, we call that a hash collision.
And in that case, you know,
we have to have some sort of a strategy
for how do I find multiple things within the same bucket.
Often it will just be a link list like you see here,
but if we know that there's gonna be a lot
of hash collisions, you might want something more efficient.
For example, a binary search tree,
like we just talked about, is another alternative.
So big O notation, in this case, technically, inserts,
lookups, and deletions, or order of one,
because in the common average case,
you apply your hash function to your key,
and you go directly to the bucket where that data is stored.
So if you don't have any hash collisions,
that truly is an order one operation. However, again,
there's the worst case scenario to think about.
So if I have everything mapping to the same bucket,
and if my,
my hash function is absolutely terrible and inefficient,
and I've mapped things to a link list.
Well, in the worst case,
I might have O(n) for a lookup instead,
or an insert or deletion. Okay.
So again,
it's all in the implementation, tuning those hash functions,
and how big,
how many buckets you have is pretty crucial
to good performance.
But why is this particularly important for system design?
Well,
it's also a useful tool for distributing lookups
across a whole fleet of servers.
So if I have a horizontally partitioned database,
or data store, like a no sequel data store,
I could just have a hash function that says, okay,
you want this key?
I'm going to use that hash function to figure out
which machine in my whole cluster, that data is stored on.
So the whole idea of a hash function
can be used it's at two levels, right?
So, I might have one function
that maps to which machine my data is stored on.
And within that machine,
there might be another hash table,
that points to where that data
is actually stored within that machine.
So, extremely useful tool in the context of system design.
So anytime you need fast look-ups,
which is usually the case,
a hash table is a pretty good tool to have in your toolbox.