Red-Black Trees

[00:00:00]
>> So the next thing is a red black tree. I'm not gonna cover this one in detail, just because there's 75 rules to it, and I would rather move on to more exciting algorithms. And so, we already know a tree balance algorithm. So just to kind of give you the basics of a red black tree, there's a few rules to it.

[00:00:16]
One, the root and nil nodes, nil is important, they actually count the empty spot as a node itself, so you kind of always have to keep that in your mind, are black. They're always black, that's just the way it goes. Number 2, all nodes are either red or black.

[00:00:40]
Okay, makes sense, right, red black tree, but kind of silly if you could have something else. Number 3, you cannot have a red parent + red child. You can't have that situation, but you can have black black. You just cannot have red red, that's pretty much, I don't think there's any other rules, I always have to think about that.

[00:01:05]
But that's about it, and obviously, number 4, they maintain the binary search tree. Right, they're still a binary search tree, they still work that way, so we stay right there. So, if you think about it, if we have a root, it will be black. And, yeah, I don't know how did I forget that.

[00:01:22]
All paths have same number of black children. So, that should be pretty easy. So, this one always, when I was thinking about it and implementing it, in my head, this seems like an incredibly difficult problem, right? Cuz how do you know all paths have this? That feels really difficult.

[00:01:50]
But when you go through and actually do it, you calculate the black height at every level, it gets a little bit easier and the rotations aren't that hard. And there's a whole bunch of coloring, dances you do, and a bunch of different stuff. But, just to kind of give you the general idea, and so, we can just talk about the runtime, is roots always black?

[00:02:04]
And then, you can have red children, or I can have a black child right here. And then remember, nil nodes are black. Don't forget that, that's a very important kind of sidestep. On this side, you could imagine I have red, which means I can have two black nodes, I cannot have red nodes at this point.

[00:02:23]
They cannot have parent-child red noding relation, which means that I can also have more red, and then, I can have the empty nodes right here, which also means right here and right here. So I want you to think about this. Is this a red black tree? Does it follow all of our five rules?

[00:02:51]
>> I know.
>> What doesn't follow?
>> The left side has one less black no than the right side.
>> Let's find out 1, 2, 1, 2 or 2, I know it's kind of wild. In other words, what that means is that, you can get into a situation where the worst case scenario is one side is twice as high as the other side.

[00:03:20]
Cuz you have all black on one side and you have red black, red black, red black. And so, you can have twice the height on one side, half the height on the other side. Now, the rotations work in such a way that every single time you insert, you always insert it as a red child.

[00:03:33]
If you have red red, you have to do a coloring, or you have to do a flipping depending on the uncle and the color of the uncle. Kind of confusing that's why you can actually run into this specific situation is that is how you'd run into it, all right?

[00:03:44]
So, there you go, that is all I'm gonna really say about red black trees. Because again, it would just take a long time to get all the way through, very exciting. But that means that searching is still log n, because remember, it could be 2h, or in other words, 2log n, cuz it's going to be relatively balanced.

[00:04:03]
They're never gonna get into a situation where it's not much further apart. And if you double one side versus the other, you still are at h, right? Because we'd always drop the constant. So we're still at h, we're still sitting at the log n area, very nice. Insertions, deletions, all the same things, all right?