Red Black Tree 1 The Rules

okay let's take a look at another way to balance trees these are called red black trees red black trees are a way of keeping a tree always balanced and the idea is that you label every node is either red or black I'm not going to use red or black because I don't have red and black markers but you'll see what I mean and in fact of course when we write code we don't label them red and black we have a boolean value that we set to either true or false to note whether something is red or black but we label every node as red or black and then every time we add something to the tree we check our tree against a set of rules and depending on the violation we do either a color flip or a rotation to correct the issues with our tree so let's take a look at first of all of the rules that we have to follow and there are six of them that we need to know the first is that every node is either red or black there's no alternative you can either be red or you can be black next the root is always black and if the root is not black we make it black we force it to be black new insertions are always read we always start with insertions that are read if we insert something as the root node we insert it as read but we immediately make it black every path from root to leaf so every possible path that we can take through our tree has the same number of black black nodes no path can have two consecutive red nodes and finally any null node is considered to be black so two things to notice here every path from root to leaf has the same number of black nodes that means that a path or different paths from root to leaf can have different numbers of red nodes that's okay it's specifically black nodes and no path can have two consecutive red nodes but a path can have two consecutive black nodes that's also okay so these are our six rules remember them if I set you an exam question about red black trees which is quite likely I often ask you a question which one of the six rules people often forget every node is red or black or that nulls are black but these are the six rules from red black trees every time we add to our red black trees we come back to these rules we take a look at them and we ask our do our trees violate these rules what happens if our tree violates these rules well we have to fix the tree let's take a look at how we do that fix there's two more rules for fixing the tree so we need to rebalance based on whether if we have a black ant we rotate black aren't we rotate if we have a red ant we color flip so I don't have black and red so I'm going to use alternate colors I'm going to use red for red and I'm going to use blue for black ok so after we do either a rotation or a color flip after that we then need to resolve the colors on the tree and you'll see what I mean by this when I go through an example but the rule is that after a rotation the three nodes that we're working on end up as black red red okay so the parent is black and the two children are red in contrast after a color flip the three nodes that we're working on the parent ends up red and the children end up as black it doesn't matter what color the edges are okay this is complex and we'll go through an example which I hope will clarify it but you need to remember that if you have a black aren't you rotate and if you have a red aren't you color flip after a rotation we set the color of the nodes so the parent is black and the children are red and after a color flip or as a color flip all we do is we set the parent to be red and the two children to be black

Channel: RobEdwards

Views: 52,143

Rating: 4.9679632 out of 5

Keywords: data structures, computer science, cs310

Id: nMExd4DthdA

Length: 8min 9sec (489 seconds)

Published: Thu Nov 10 2016