5.16 Red Black tree | Introduction to Red Black trees | Data structure

the topic is red black please in this video we will see what is need of red black tree how red black trees are different from AVL trees what is red black trees some properties of red black trees as well as I will give you some examples and we will see all those red black trees or not right now see first of all we will see what is the need of Fred black we see we have already discussed many types of trees BST binary tree avian tree B 3 B plus tree he pre as well right so what is the need of red black Pring we have already many types of trees fine see first of all tree is what it is a data structure you can say data structure means it's a way of organizing the data or you can say a way of organizing the data efficiently in such a way that we can access the data in less time we can insert something we can delete something in a less time obviously we want that if we are going to store data somewhere then we want that we can search something from that data in a very less time we can insert we can update that data or we can delete something from that data in a less time that is obviously we want right so if you are dealing with a large data and it if it comes on how to store that data then we need something we need some data structures many data structures we have discussed array linked lists stacks queues now trees right so every data structure is having its own advantages and drawbacks somewhere we are using array data structure somewhere we are using linked list data structure means it's better to use linked list and somewhere it is better to use arrays somewhere it is better to use trees it depends on many types of factors like one factor is one you can say that frequent operations what type of frequent operations you are going to perform on that data right see in pre data structures it is red black tree is basically a binary search tree so the prerequisite of this video is water you should know what is a binary search tree right so you can check out the video in this I button fine now what is a binary search Tracy in the in that case always the left sub-tree of an old would contain the value less than that node and the right subtree of the node contains value greater than that node see if you say that see somewhere it is written that that left child of a node is having value less than that owed and right child is having value greater than that node if you followed that property in that case suppose Here I am drawing that BST this is a node it means left child look this should be less than ten suppose I am taking seven right child should be greater than ten suppose I am taking 15 now this property is applied in all the nodes on all the nodes now for seven left-side child should be less than seven suppose I am taking three right child of seven should be greater than seven now I am taking here eleven but is this a BST no it is not a BST you should say that the left subtree because he's 11 is greater than seven but 11 is greater than ten also but to the left of n the value should be less than ten it means this is the left subtree for this ten this would be the right subtree for the strength right so in this left subtree slot left subtree of any node should contain values less than that node and right subtree should contain values greater than that node so it's better to say that rather than left child and right child it is better to say left subtree and right subtree fine now see I'm taking these both are binary search trees now as we know that in binary search tree the searching or you can say insertion and deletion is going to take order of log n time in average case low to base two and an in average case in best case it is order of one in worst case it is order of n right in average case it is order of log n right so you can say the searching of any data in binary search tree is going to take less time that is why I obviously we are using three data structures right ha see suppose I am taking this is one BST this is another BS you to type so BST we have now see if and I want to search for a number 19 in both the trees in this case 90 means we will compare with the root 90 is greater than this root greater than 10 so we will go to this path in this root means we are not going to check all these elements right again 15 90 is greater than 15 so we will go to this root we are not going to compare this with this 13 that is why here we need not to compare this element with all the data present in the BST that is why the searching is going to take less time or you can say it is going to take order of H time the time complexity would be according to the height of the BST and basically it is what height is log n base is 2 so that is why time complexity would be order of log n 2 right this is the average case you can say fine now in this case suppose I am searching for 19 that is greater than 10 we will go to here greater than 15 there there than there there there anything after that it will give you that the ninth is not present in that way but here the time complexity would be you have compared this element with all the elements present in the BST so it is equal to order of n so this is the worst case right and we want that the time taken or the time complexity would be as less as possible so that is why rather than this this is what a right skewed BST we want that the tree the BST or the tree should be balanced see this is what a balanced BST you can see so whenever we will insert the data we all we always want that the tree would be balanced so that all the operations like insertion deletion deletion searching find minimum and maximum all these operations should take all these operations will take time complexity order of log n only that is very less than order of n fine now okay we will need water balanced tree now and red black tree is also a self-balancing binary search tree but now you can say that also we have a tree that is a BL this is also a self balanced but you can say a height balanced tree then why we need red black tree right because in a real real so it also guarantees that the time complexity would be order of log n right in all the cases in worst case in best case in average case in BST in worst case it is order of n because the BST can be left skewed or right skewed something like this or it may be between this this this and this suppose something like this here we have this tree so this is also a BST here you can write down the numbers according to the BST that follow that rule only this is between this and this this is not a left or right skewed and this is not a balanced tree right but we want that the tree should be balanced so that the time complexity would be less order of log n but AVL tree guarantees that the time complexity would be log n only because this is what height height balanced tree so why we are using red black trees how red black trees are different from AVL trees see now main difference is what in AVL tree you need to do many rotations sometimes if tree is very large so maybe you require more than 2 3 4 5 6 or many rotations to balance that tree suppose at this point of times tree is something like this here this is a tree having multiple nodes this is some there is some node we have and in this case we need to do some rotations so after rotating this after doing this balance suppose this trees the upper trees what unbalanced so you need to do rotations at this part after balancing this part suppose there is the trees unbalanced at this part at upper level so you need to balance here also right so I don't know how many rotations would be required maybe we require the rotation up to the root node right but in red black trees maximum two rotations would be required and the tree would be balanced right and sometimes even the rotary rotations would not be required and recoloring would be required recoloring means as the name suggests the nodes would be either red or black so you need to change the color only if the node is red just changes to change it to black something like this we will discuss these rules in the next video when we are going to discuss the insertion part right so sometimes only recoloring would be sufficient no rotation would be required and if rotations are required then only you know you can say maximum maximum two rotations would be required rotations plus recoloring may be required but not more than two rotations so very less rotations would be required in a red black raised to balance that tree but see red black trees you can say roughly height balanced and AVL trees strictly height balanced tree so you can see AVL tree is more balanced than red black trees but red black trees guarantees you to give the time complexity order of log n for although you can see searching insertion deletion these kind of operations and that that's exactly we want the time complexity would be this one right so we can go for red black trees in the case when you are you are going to perform insertion and deletion operation very frequently see searching is faster in AVL tree because it is strictly height balanced tree but insertion and deletion is faster in red-black trees because here we require few rotations and in AVL trees we require many rotations right so depends on the situation depends on the operations you want to perform on the tree we are going to choose the trees it's not like that red black trees are best and these are not good right it depends on the situation fine in a separate video I will discuss the difference between AVL tree and red black trees properly right now I guess you have got that why we need red black trees fine now we will discuss how red black trees are different from AVL trees right now we will discuss what is red black trees and properties of red black trees so these are some properties of red black trees see it is a self-balancing binary search tree we have discussed what is binary search tree and what is self balancing means it is going to balance itself by doing some rotations or recoloring that thing we will discuss in the next video the rule of rotation and recoloring that thing I will discuss in the next video and we will do the insertion in the red black trees right now next is obviously it is a red black tree so every node is either red or black right it means every node is having a special bit which shows the color of the node right a one bit you can say zero means black and one means red only one extra bit would be required with each node and other than this bit each node is containing what obviously the node is same as binary tree we have discussed the key or you can say the data left pointer right pointer right plus this also one bit for storing the color of the node that is also mandatory right how to write down the node that structure of the node that you will discuss in the implementation part right now next is what C root is always black or you can say the head node is always black so now in this case see suppose this is a tree this is I'm taking root node obviously we have one not only so that would be the root node so this is always black suppose I am taking here the number 10 right or you can relate it with real-life example obviously in the tree we have something like this then here also we have some so these are what child of the Sten and these are child of this node right suppose array of seven five so for these this is the grandparent or you can say the head of the family and see when a person gets angry then you can say the face of that person becomes red right and we consider here that if a person is calm or cool then the face of that person is black so the head of the family always try to remain calm right but you can say the grandparents you can relate it with that they do yoga and all and that is why they always remain calm they usually don't get angry that is why the root or the head node will always be black not red right now next is what every leaf see this property is very important every leaf which is new is black here in this case if you are not considering red black place this is a binary tree here the leaf node are this this and this these are not having any child node but in red black trees what we consider is see here if this is a node means this is the leaf node it is having no left child no right side so here we consider nil this is nil this is nil and see obviously this this color is what it should be black note red it should be black so every leaf which is new is black so it is also having no left no right so it is nil it is named so we usually draw red black tree something like this see we are not going to consider these nodes as a part of the part of the tree they is what external nodes right generally we don't count these nodes in this tree but these are help helpful we will when we will insert and delete the data from the tree fine so now every leaf node which is nil is black which is nil is black it's not like that this is leaf road and this would be black know here we are not considered these as leaf nor leaf node would be these nodes the nil nodes these are considered as internal nodes of the red black trees right this thing you need to take care so now suppose this is a tree here this root is always black and we have taken these nil nodes every leaf which is nil is black right so see here also this node is also having no left child it means basically we can consider it with the pointer left pointer right pointer those are null pointers so here I am drawing these as a node that is nil nodes right simply you can say so here also the left is nil for 20 both left and right could be nil so these nil would be black right now see next is if Rho node is red then it's children are black it means here you can in another term you can say there should not be no red red parent-child relationship or you can say that no adjacent node can be read something like this see this root is black black right so this and this can be black can be red right because constraint is only on the red nodes not on the black color on the black nodes constraint is this one that thing will discuss right so now suppose this is red and this is red fine but this if I say this is red this is not true because if node is red see this node is red so it's children should be black so this and this cannot be red that is for sure so this should be black and this should also be black right here also you can say if this is red so this cannot be red right because if you draw this as red means these two are adjacent nodes and these two are red that is not possible so this should be black right now if this is black then the six and eight these can be red or black according to this rule but obviously we need to take care of this property also right suppose if I'm taking this is black and this also I am taking black and black now check the next property see every path from a node to any of its descendant nil node has same number of black nodes right any path from any node right suppose I'm taking first of all from the root node from the root node check out the paths one path is this one one path is this one one is we can go to this nail we can go to this nail then this this this this and this means one two three four five six seven eight nine paths can be there from the truth node right so in all these paths from root to the nil or any node you are considering here I am taking with the from the root right so all these paths should contain same number of black nodes now check we will not consider these we will not count these because obviously these are all the black nodes so if you will consider this thing so plus one black node that is fine but we will not consider we will not count these nodes in the path now count from here a roof will be black one and two in this path two black nodes are there in this path all also one and two black nodes are there this is red we are not going to consider this one now in this path till this black see one two three black nodes there and in this pot soul so three to this path also three and here also we have one two three right here we have one one only one and in this path we have 1 2 and 1 and 2 for this path so each path is not having same number of black nodes so this is not a red black tree now to make it as a red black tree what you can say see if I suppose if I make this is red this is red you can make it right because the parent is black if the parent is red then you need to take care that its children should be black but if the parent is black then children can be red or black right but with this you need to take care of other property as well so now in this path c1 2 and here also we have 2 black nodes that is fine but problem is what from here to here to this nil node we have only one black node so this is still not a red black tree now suppose here also rather than this nil I draw here one more node and so see it is a BST so here this should contain value less than 15 right but it should be greater than 10 you need to take care of this thing also right so suppose I am taking here to N and this is black right so to this also having one nil and right also having nil now check out this path to this nail 1 and 2 black to this nail we have 1 and 2 black here also we have 2 black and 2 black now I guess in every path we have same number of black nodes so now this is a red black tree now the question may be is every AVL tree can be a red black tree see if a tree is AVL tree and you color it red and black according to the rules then it would be a red black tree so you can say AVL trees are subset of red black trees right but if a tree is red black tree then it is not true that that would be a real tree maybe if you remove the coloring so it is not compulsory that that that tree would be AVL tree because these trees are roughly height balanced and AVL trees strictly height balanced tree right now I'm going to give you some examples and we will see are those trees red black trees or not if not which property they are violating fine so let us take these three examples are these red black trees or not first of all this thing check out this thing see here you can say first of all it is a BST or not right so you have to check out that condition first thing you can say that root is what here red but root should be black so this is not a BST no need to check out other conditions right first is violated it means it is not a red black tree next is this one here see I have all the nodes are black right and obviously this is a BST because it is following a BST property right now but this is not a red black tree why so which property this is violating see see first property is what every node is either black or red it is not compulsory that there should be one red or black something like this all may be black because on red only we have the restriction if the node is red then children should be black on the black layer we have don't we don't have any restriction we have this restriction we will check out this thing also now root is black root is black every leaf which is nil is black so obviously I'm not throwing those nil that are black consider that thing right if node is red then it's children are black black but here known a red node is there now this property see every path from any node to its descendant null nodes or nil nodes must contain same number of black nodes now check out this path to its nil nodes one two three black nodes here also one two three fine here we have one two three fine but to this path here also we have one nil right so check out through this new one and two we have only two black this condition is violated so this is not a red black tree but suppose I draw here something like this here I now eleven this is black now this is a red black tree even we don't have any red color in this tree still this is a red black tree because it is following all the properties of red black tree so one thing you can say it is what other than red black tree it is what a perfect binary tree we have already discussed binary tree and its types you can check out that video here what is perfect binary tree each node is having exactly two children and these leaf node should be at the same level so here you can say every perfect binary tree that contains only black nodes is also a red black tree so now this is a red black tree right this is a red black tree now check out this thing is this a binary tree binary search tree sorry see it is if it is following all the properties of this one red black tree if you are not checking this BST property because it is not following the binary search tree property other than that see root is black root is always black every leaf is a snail is black obviously these are black if node is red then it's children are black these are black and it's nil note that are always black you can check out the paths from here to here to black node from here to here to black node from here to here to black node and here also obviously we are having what Nellie I am NOT drawing that thing you need to take care of this thing because always we are going to draw that tree something like this rather then drawing the nail everywhere right so through this path also we have to black so you can say this is a red black tree but you need to check out that this is a BH - you're not this is not a binary search tree see to the left of ten we have eleven that is not possible to the left of N in the left subtree we should have values less than ten so this is not a red black tree right see rather than writing all here nil for every node for every leaf node what you can say one node can be NIM that can be sentinel node and you can connect see the left pointer of this to this the right pointer of this to this left point of this to this nil right pointer to this nil so you need only one sentinel node that also you can implement something like this or rather than this you can consider for each leaf node for each these leaf node one nil node that is also fine right now we will take some other examples now check out for this tree is this red black tree it is a BST yes root is black PS but see this is red this is also red but if our node is red then its children should be black so this is violating this property though this one right if I write here black then then s it is a red black tree right this property is also followed now check out this one check out the path from here to here we have one two two black nodes from here to here also two black nodes from here to here we have also one two two black nodes so every path is having same number of you can say that black nodes say this condition you can check out from any node see suppose I am taking this node from this node check out the path to its descendant nil nodes so here we have this path because here we have two nil nodes here we have two nil nodes so one to this node that is one black node from here to here also one from here to here one from here to here one right so this is also having you know same number of black nodes on each path so this is what a red black tree now see if I draw here one more node and which is what suppose black and this is one now this is not a red black tree because in this path we have one two three black nodes and here we have two so this is violating this condition this last condition suppose I'm changing the color to red now this is a red black tree right so now can you can you extend this further can you here draw one more node see we cannot draw red because to address in red are not possible if you do the coloring black right suppose zero I'm taking so in this node B one two and three three black nodes but here we have only two black node so this is not possible right so now here one more point about red black tree is what we are drawing that point from this property only because this because of this property we cannot add here one more node neither red nor black right so here you can say the longest path from the root is no more than twice the length of the shortest path or you can say see the path from root to its farthest leaf node farthest means to its extreme leaf node right is no more than twice as long as the path from root to its nearest leaf node now see that we nearest leaf node of this root is this one right if you don't consider this then here you can say these are leaf node that is nil and right so nearest are these one these two so the path is two right now the extreme leaf node or the farthest leaf notice this one or you can say here we have nil and these ones it or you can see the extreme and the maximum distance from the root these are the nodes so check out the path here what is the path having for this to this then this to this that is for it means 2 into 2 that is for it cannot be more than 4 so you can say it cannot be more than twice then this path right that is one more you can say that point about red black trees I hope you are getting this property see here we can add some node here right so these nodes can be what red these cannot be black because if these nodes are black then 1 2 & 3 in this path 3 black nodes are there and here we have only 2 black notes obviously we are not considering these nil nodes right so here you can say red and red that is possible right but this is also what this path is also having what value 4 here we can say nil nil nil but here further we cannot insert any node either red or black red we cannot insert because it is a red red this condition will be violated we cannot insert black because if you insert black then here 1 2 1 2 & 3 3 node would be there black would be there to this path and here we have only two nodes so that is one more point and that point has been you know driven from this point only the longest path from root to its leaf node cannot be you know more than twice the length of the shortest path so now this is question for you you need to tell me is this red black tree or not if not then which property this tree is violating you can write down your answer in the comment box right so this is now just fine I guess for the introduction part of red black trees in the next video we'll discuss the how to perform insertion in red black trees all right so I'll so in the next video till then bye bye I take it

Channel: Jenny's lectures CS/IT NET&JRF

Views: 241,845

Rating: 4.8691168 out of 5

Keywords: data structure tutorials, data structure and algorithms, what is red black tree, red black tree in data structure, introduction to red black tree in data structure, properties of red black tree, avl tree vs red black tree, red black tree insertion, red black tree deletion, ugc net computer science preparation, gate cs lectures, jenny data structures, jennys lecture, jayanti khatri lamba, jenny's lectures cs/it NET&JRF, c programming tutorials, cs it youtube channels

Id: 3RQtq7PDHog

Length: 33min 0sec (1980 seconds)

Published: Thu Oct 24 2019