So, in this video, we'll graduate beyond the domain of just vanilla binary search
trees, like we've been talking about before, and we'll start talking about
balanced binary search trees. These are the search trees you'd really
want to use when you want to have real time guarantees on your operation time.
Cuz they're search trees which are guaranteed to stay balanced, which means
the height is guaranteed to stay logarithmic, which means all of the
operations search trees support that we know and love, will also be a logarithmic
in the number of keys that they're storing.
So, let's just quickly recap. What is the basic structure tree property?
It should be the case that at every single node of your search tree, if you go to the
left, you'll only see keys that are smaller than where you started and if you
go to the right you only see keys that are bigger than where you started.
And a really important observation, which is that, given a set of keys, there's
going to be lot and lots of legitimate, valid, binary search trees with those
keys. So, we've been having these running
examples where the keys one, two, three, four, five.
On the one hand, you can have a nice and balanced search tree that has height only
two, with the keys one through five. On the other hand, you can also have these
crazy chains, basically devolved to link lists where the heights for, and elements
could be as high as N - 1. So, in general, you could have an
exponential difference in the height. It can be as small, in the best case, as
logarithmic and as big, in the worst case, as linear.
So, this obviously motivates search trees that have the additional property that you
never have to worry about their height. You know they're going to be well
balanced. You know they're going to have height
logarithmic. You're never worried about them having
this really lousy linear height. Remember, why it's so important to have a
small height? It's because the running time of all of
the operations of search trees depends on the height.
You want to do search, you want to insertions, you want to find predecessors
or whatever, the height is going to be what governs the running time of all those
properties. So, the high level idea behind balanced search
trees is really exactly what you think, which is that, you know, because the
height can't be any better than logarithmic in the number of things you're
storing, that's because the trees are binary so the number of nodes can only
double each level so you need a logarithmic number of levels to
accommodate everything that you are storing.
But it's got to be logarithmic, lets make sure it stays logarithmic all the time,
even as we do insertions and deletions. If we can do that, then we get a very rich
collection of supported operations all running in logarithmic time.
As usual, n denotes, the number of keys being stored in the tree.
There are many, many, many different balanced search trees.
They're not super, most of them are not super different from each other.
I'm going to talk about one of the more popular ones which are called Red Black
Trees. So, these were invented back in the '70s.
These were not the first balanced binary search tree data structures, that honor
belongs to AVL trees, which again are not very different from red black trees,
though the invariants are slightly different.
Another thing you might want to look up and read about is a very cool data
structure called splay trees, due to Sleator and Tarjan,
These, unlike red black trees and AVL trees, which only are modified on
insertions and deletions, which, if you think about it, is sort of what you'd
expect. Splay trees modify themselves, even when
you're doing look ups, even when you're doing searches.
So, they're sometimes called self-adjusting trees for that reason.
And it's super simple, but they still have kind of amazing guarantees.
And then finally, going beyond the, just the binary tree paradigm many of you might
want to look up examples of B trees or also B+ trees.
These are very relevant for implementing databases.
Here what the idea is, in a given node you're going to have not just one key but
many keys and from a node, you have multiple branches that you can take
depending where you're searching for falls with respect to the multiple keys that are
at that node. The motivation in a database context for
going beyond the binary paradigm, is to have a better match up with the memory
hierarchy. So, that's also very important, although a
little bit out of the scope here. That said, what we discuss about red-black
trees, much of the intuition will translate to all of these other balance
tree data structures, if you ever find yourself in a position where you need to
learn more about them. So, red black trees are just the same as
binary search trees, except they also always maintain a number of additional
invariants. And so, what I'm going to focus on in this
video is, first of all, what the invariants are, and then how the
invariants guarantee that the height will be logarithmic.
Time permitting, at some point, there will be optional videos more about the guts,
more about the implementations of red black trees namely how do you maintain
these invariants under insertions and deletions.
That's quite a bit more complicated, so that's appropriate for, for optional
material. But understanding what the invariants are
and what role they play in controlling the height is very accessible, and it's
something I think every programmer should know.
So, there, I'm going to write down four invariants and really, the bite comes from
the second two, okay, from the third and the fourth invariant.
The first two invariants you know, are just really cosmetic.
So, the first one we're going to store one bit of information additionally at each
node, beyond just the key and we're going call this bit as indicating whether it's a
red or a black node. You might be wondering, you know, why red
black? Well, I asked my colleague, Leo Guibas
about that a few years ago. And he told me that when he and Professor
Sedgewick were writing up this article the journals were, just had access to a
certain kind of new printing technology that allowed very limited color in the
printed copies of the journals. And so, they were eager to use it, and so
they named the data structure red black, so they could have these nice red and
black pictures in the journal article. Unfortunately, there was then some snafu,
and at the end of the day, that technology wasn't actually available, so it wasn't
actually printed the way they were envisioning it but the name has stuck.
So, that's the rather idiosyncratic reason why these data structures got the name
that they did, red black trees. So, secondly we're going to maintain the
invariant that the roots of the search tree is always black, it can never be red.
Okay. So, with the superficial pair of
invariants out of the way, let's go to the two main ones.
So, first of all, we're never going to allow two reds in a row.
By which, I mean, if you have a red node in the search tree, then its children must
be black. If you think about for a second, you
realize this also implies that if a notice red, and it has a parent, then that
parent has to be a black node. So, in that sense, there are no two red
nodes in a row anywhere in the tree. And the final invariant which is also
rather severe is that every path you might take from a root to a null pointer, passes
through exactly the same number of black nodes.
So, to be clear on what I mean by a root null path, what you should think about is an
unsuccessful search, right? So, what happens in an unsuccessful
search, you start at the root depending on whether you need to go smaller or bigger,
you go left or right respectably. You keep going left right as appropriate
until eventually you hit a null pointer. So, I want you to think about the process
that which you start at the root and then, eventually, fall off the end of the tree.
In doing so, you traverse some number of nodes.
Some of those nodes will be black some of those nodes will be red.
And I want you to keep track of the number of black nodes and the constraints that a
red black tree, by definition, must satisfy, is that no matter what path you
take through the tree starting from the root terminating at a null pointer, the
number of black nodes traversed, has to be exactly the same.
It cannot depend on the path, it has to be exactly the same on every single root null path.
Let's move on to some examples.
So, here's a claim. And this is meant to, kind of, whet your
appetite for the idea that red black trees must be pretty balanced.
They have to have height, basically logarithmic.
So, remember, what's the most unbalanced search tree?
Well, that's these chains. So, the claim is, even a chain with three
nodes can not be a red black tree. So, what's the proof?
Well, consider such a search tree. So, maybe, with the key values one, two and three.
So, the question that we're asking is, is
there a way to color the node, these three nodes, red and black so that all four of
the invariants are satisfied. So, we need to color each red or black.
Remember, variant two says, the root, the one has to be black.
So, we have four possibilities for how to use the color two and three.
But really, because of the third invariant, we only have three possibilities.
We can't color two and three both red, cuz
then we'd have two reds in a row. So, we can either make two red, three
black, two black, three red, or both two and three black.
And all of the cases are the same. Just to give one example, suppose that we
colored the node two, red, and one and three are black.
The claim is invariant four has been broken and invariant four is going to be
broken no matter how we try to color two and three red and black.
What is invariant four says? It says, really on any unsuccessful
search, you pass through the same number of black nodes.
And so, one unsuccessful search would be, you search for zero.
And if you search for a zero, you go to the root, you immediately go left to hit a
null pointer. So, you see exactly one black node.
Namely one. On the other hand, suppose you searched
for four, then you'd start at the root, and you'd go right, and you go to two,
you'd go right, and you go to three, you'd go right again, and only then will you get
a null pointer. And on that, unsuccessful search, you'd
encounter two black nodes, both the one and the three.
So, it's a violation of the fourth invariant, therefore, this would not be a
red black tree. I'll leave that for you to check, that no
matter how you try to code two and three red or black, you're going to break one of
the invariants. If they're both red, you'd break the third
invariant. If at most one is red, you'd break the
fourth invariant. So, that's a non-example of a red-black tree.
So, let's look at an example of a red-black tree.
One, a search tree where you can actually
color the nodes red or black so that all four invariants are maintained.
So, one search tree which is very easy to make red black is a perfectly balanced one.
So, for example, let's consider this three
nodes search tree has the keys three, five, and seven and let's suppose the five
is the root. So, it has one child on each side, the
three and the seven. So, can this be made a red black tree?
So, remember what that question really means.
It's asking can we color theses three nodes some combination of red and black so
that all four of the invariants are satisfied?
If you think about it a little bit, you realize, yeah, you can definitely color
these nodes red or black to make and satisfy for the invariants.
In particular, suppose we color all three of the nodes, black.
We've satisfied variant number one, we've colored all the nodes.
We've satisfied variant number two, and particularly, the root is black.
We've satisfied invariant number three. There's no reds at all, so there's
certainly no two reds in a row. And, if you think about it, we've
satisfied invariant four because this tree is perfectly balanced.
No matter what you unsuccessfully search for, you're going to encounter two black
nodes. If you search for, say, one, you're going
to encounter three and five. If you search for, say, six, you're going
to encounter five and seven. So, all root null paths have exactly
two black nodes and variant number four is also satisfied.
So, that's great. But, of course, the whole point of having
a binary search tree data structure is you want to be dynamic.
You want to accommodate insertions and deletions.
Every time you have an insertion or a deletion into a red black tree, you get a
new node. Let's say, an insertion, you get a new
node, you have to color it something. And now, all of a sudden, you got to worry
about breaking one of these four invariants.
So, let me just show you some easy cases where you can accommodate insertions
without too much work. Time permitting we will include some
optional videos with the notion of rotations which do more fundamental
restructuring of search trees so that they can maintain the four invariants, and stay
nearly perfectly balanced. So, if we have this red black tree where
everything's black, and we insert, say, six, that's going to get inserted down
here. Now, if we try to color it black, it's no
longer going to be a red black tree. And that's because, if we do an
unsuccessful search now for, say, 5.5, we're going to encounter three black
nodes, where if we do an unsuccessful search for one, we only encounter two
black nodes. So, that's not going to work.
But the way we can fix it is instead of coloring the six black, we color it red.
And now, this six is basically invisible to invariant number four.
It doesn't show up in any root null paths.
So, because you have two black nodes in all roots in all paths before, before the
six was there, that's still true now that you have this red six.
So, all four invariants are satisfied once you insert the six and color it red.
If we then insert, say, an eight, we can pull exactly the same trick, we can call
it an eight red. Again, it doesn't participate in invariant
four at all so we haven't broken it. Moreover, we still don't have two reds in
a row, so we haven't broken invariant number three either.
So, this is yet another red black tree. In fact, this is not the unique way to
color the nodes of this search tree, so that it satisfies all four of the
invariants. If we, instead, recolor six and eight
black, but at the same time, recolor the node seven, red, we're also golden.
Clearly, the first three invariants are all satisfied.
But also, in pushing the red upward, consolidating the red at six and eight,
and putting it at seven instead, we haven't changed the number of black nodes
on any given path. Any black, any path that previously went
through six, went through seven, anything that went through eight, went through
seven so there's exactly the same number of red and black nodes on each such path
as there was before. So, all paths still have equal number of
black nodes and invariant four remains satisfied.
As I said, I've shown you here only simple examples, where you don't have to do much
work on an insertion to retain the red black properties.
In general, if you keep inserting more and more stuff and certainly if you do the
deletions, you have to work much harder to maintain those four invariants.
Time permitting, we'll cover just a taste of it in some optional videos.
So, what's the point of these seemingly arbitrary four invariants of a red black
tree? Well, the whole point is that if you
satisfy these four invariants in your search tree, then your height is going to
be small. And because your height's going to be
small, all your operations are going to be fast.
So, let me give you a proof that if a search tree satisfies the four invariants,
then it has super small height. In fact, no more than double the absolute
minimum that we conceivably have, almost two times log base two of N.
So, the formal claim, is that every red-black tree with N nodes, has height O
of log N, were precisely in those two times log base two of N + 1.
So, here's the proof. And what's clear about this proof is it's
very obvious the role played by this invariants three and four.
Essentially, what the invariants guarantee is that, a red black tree has to look like
a perfectly balanced tree with at most a sort of factor two inflation.
So, let's see exactly what I mean. So, let's begin with an observation.
And this, this has nothing to do with red black trees.
Forget about the colors for a moment, and just think about the structure of binary
trees. And let's suppose we have a lower bound on
how long root null paths are in the tree. So, for some parameter k, and go ahead and
think of k as, like, ten if you want. Suppose we have a tree where if you start
from the root, and no matter how it is you navigate left and right, child pointers
until you terminate in a null pointer. No matter how you do it, you have no
choice but to see at least k nodes along the way.
If that hypothesis is satisfied, then if you think about it, the top of this tree
has to be totally filled in. So, the top of this tree has to include a
perfectly balanced search tree, binary tree of depth k - 1.
So, let me draw a picture here of the case of k = three.
So, if no matter how you go from the root to a null pointer, you have to see at
least three nodes along the way. That means the top three levels of this
tree have to be full. So, you have to have the root.
It has to have both of its children. It has to have all four of its
grandchildren. The proof of this observation is by
contradiction. If, in fact, you were missing some nodes
in any of these top k levels. We'll that would give you a way of hitting
a null pointer seeing less then k nodes. So, what's the point is, the point is this
gives us a lower bound on the population of a search tree as a function of the
lengths of its root null paths. So, the size N of the tree must include at
least the number of nodes in a perfectly balanced tree of depth k - 1 which is
2^k - 1, So, for example, when k = 3, it's 2^3 (two cubed) - 1,
or 7 that's just a basic fact about trees,
nothing about red black trees. So, let's now combine that with a red
black tree invariant to see why red black trees have to have small height.
So again, to recap where we got to on the previous slide.
The size N, the number of nodes in a tree, is at least 2^k - 1, where k is
the fewest number of nodes you will ever see on a root null path.
So, let's rewrite this a little bit and let's actually say, instead of having a
lower bound on N in terms of k, let's have an upper bound on k in terms of N.
So, the length of every root null path, the minimum length of every root null
path is bounded above by log base two of quantity N + 1.
This is just adding one to both sides and taking the logarithm base two.
So, what does this buy us? Well, now, let's start thinking about red
black trees. So now, red black tree with N nodes.
What does this say? This says that the number of nodes, forget
about red or black, just the number of nodes on some root null path has to be the
most log base two of N + 1. In the best case, all of those are black.
Maybe some of them are red, but in the, in, the maximum case, all of them are
black. So, we can write in a red black tree with
N nodes, there is a root null path with at most log base two of N + 1, black nodes.
This is an even weaker statement than what we just proved.
We proved that it have some, somehow must have at most log based two, n + 1 total
nodes. So, certainly, that path has the most log
base two of N + 1 black nodes. Now, let's, now let's apply the two
knockout punches of our two invariants. Alright, so fundamentally, what is the
fourth invariant telling us? It's telling us that if we look at a path
in our red black tree, we go from the root, we think about, let's say, that's an
unsuccessful search, we go down to a null pointer.
It says, if we think of the red nodes as invisible, if we don't count them in our
tally, then we're only going to see log, basically a logarithmic number of nodes.
But when we care about the height of the red black tree, of course, we care about
all of the nodes, the red nodes and the black nodes.
So, so far we know, that if we only count black nodes then we're good, We only have
log base two of N + 1 nodes that we need to count.
So, here's where the third invariant comes in.
It says, well actually, black nodes are a majority of nodes in the tree.
In a strong sense, there are no two reds in a row, on any path.
So, if we know the number of black nodes is small, then because you can't have two
reds in a row, the number of total nodes on the path is at most twice as large.
In the worst case, you have a black route, then red, then black, then red, then
black, then red, then black, et cetera. At the worst case, the number of red nodes
is equal to the number of black nodes, which doubles the length of the path once
you start counting the red nodes as well. And this is exactly what it means for a
tree to have a logarithmic depth. So, this, in fact, proves the claim, if
the search trees satisfies the invariants one through four, in particular if there's
no two reds in a row and all root null paths have an equal number of black nodes,
then, knowing nothing else about this search tree, it's got to be almost
balanced. It's perfectly balanced up to a factor of
two. And again, the point then is that
operations in a search tree and the search trees are going to run in logarithmic
time, because the height is what governs the running time of those operations.
Now, in some sense, I've only told you the easy part which is if it just so happens
that your search tree satisfies these four invariants, then you're good.
The height is guaranteed to be small so the operations are guaranteed to be fast.
Clearly that's exactly what you want from this data structure.
But for the poor soul who has to actually implement this data structure, the hard
work is maintaining these invariants even as the data structure changes.
Remember, the point here is to be dynamic, to accommodate insertions and deletions.
And searches and deletions can disrupt these four invariants and then one has to
actually change the code to make sure they're satisfied again, so that the tree
stays balanced, has low height, even under arbitrary sequences of insertions and
deletions. So, we're not going to cover that in this
video. It can be done, without significantly
slowing down any of the operations. It's pretty tricky, takes some nice ideas.
There's a couple well-known algorithms textbooks that cover those details.
Or if you look at open source and limitations of balanced search trees, you
can look at code that does that implementations.
But, because it can be done in a practical way and because Red Black Tree supports
such an original array of operations, that's why you will find them used in a
number practical applications. That's why balanced search trees should be
part of your programmer tool box.