A red-black tree is a binary tree that satisfies the following red-black properties: 1. Every node is either red or black. 2. The root is black. 3. Every leaf (NIL) is black. 4. If a node is red, then both its children are black. 5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.
Thank you! This was so much easier to understand then my school textbook. You speak clearly and concisely. Great visuals and loved the short video time!
Note: Leafs with value Null (aka NIL) are by default Black. This means a representation of a tree with a red "Leaf" can correctly be a Red-Black Tree since its children are Null, which are Black.
A red-black tree is a binary search tree with one extra bit of storage per node: its color, which can be either RED or BLACK. By constraining the node colors on any simple path from the root to a leaf, red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately balanced.
I am struggling for few hours ow to understand Red-black trees, and your videos are finally the ones that made it clear to me. Thanks and congrats! You won a new subscriber :)
I was confused that the Node 5 is black. However, when I watched the video again, It just said all red nodes have black nodes children, but not all black nodes have red children. So, the reason why Node 5 is black is to have the same black height. Right?
I'm not sure what you mean when you say they have a guaranteed height of O(log n) -- I thought O() is used to characterize performance -- and you could just say that the guaranteed height is < log n...
It is, but the definition of O(n) is more general than that. Most functions f(x) are equal to O(g(x)) for some g(x), and in a balanced binary search tree such as a red-black tree, height is a function of the number of nodes.
when it says that all paths from a node to its NIL descendants contain the same number of black nodes, how many black nodes does node(9) have? Does it have 1? if so doesn't node(8) have 2 black nodes to NILL?
Am I right in saying that the example is not a R-B Tree because it's not balanced? There is a difference in height of 2 between the left and right sub trees from the root. The video is like 5 years old now, but I just wanted to ask for my own clarity :)
i don't know if it would be still helpfull, but R-B tree doesn't have to be AVL tree (the condition you have mentioned). R-B trees have different conditions for "being balanced"
due to the criteria 3 + criteria 4, it must always be the case that it is roughly balanced since worst case longest path alternates black and red nodes while the shortest one has full black -> height ratio between the two children of a node can never be worse off than 1:2
but why do nodes turn red sometimes? wasnt explained it NVM seems you explain it in diff video. Thats just the algorithm, we insert each node as red but change it to black if we have to match the rules.
One of the best sources to learn and revise. Kindly add more videos on concepts like AVL trees, Splay trees etc. Also, can you do a video on random sampling, which is hot topic of interviews these days and I see no one has made on it on RUclips yet.
Good video. I wish you revisited the unbalanced example that is the reason for using a red-black tree (binary search tree with all children nodes being lesser).
For point 4. "All paths from a node to its NIL descendants contain the same number of black nodes" is that meaning counting from _any_ node to a nil or specifically from the root to a nil? Because if it's the latter, then in the given example that makes sense (5 to nil = 2, 12 to nil = 2, 19 to nil = 2), but then what happens if I insert "24" to this tree and it's added to the right of the red "23"? As far as I can tell we no longer have root to nil counts being 2, but 3 if we were to look for "24" (e.g. 19 to 24 to nil = 3). It seems I have misunderstood the meaning behind this particular point?
@Mark McDonnell When inserting there are specific rules to follow as well. Are you sure you got those right? Otherwise you don’t end up with a valid rb tree
@@nabinkhadka7168 He pronounces it as if there aren't any "o"s in the word. It isn't correct or considered to be a normal pronunciation in most of the anglophone world. It's not bad or ugly, but it isn't correct and is indicative of his dialect and region. I would imagine he is from some place in the south of the US, though there are other pockets of similar dialects in the U.S (I don't know about other countries, maybe Canadians do that too sometimes.) I don't say this to shame him or anything, he speaks perfectly fine and I sort of like that pronunciation a little bit, I am only saying this because it seems like English might not be your first language so I just wanted to help. That's all :)
to be honest, I did not understand everything in this video. E.g. 1:50 . All paths from a node..... then you add "1" and a "2" next to the five. Don't know what are you counting there, dont know what the numbers are related to?! If you count the NILs then just put the 1 to the left NIL and the 2 to the right NIL....
Update: I see. A "Nil" node is black. I don't understand 2:27 about the Black Height. Not counting the root, the black height of the tree should be 1 instead of 2?
I still remember in past, I had to go through a long list to find his video. Now, when I searched it, it came on top! :D
if only you could go through a red black tree instead
@@ThomasEdits GO SLEEP, UNI TOMORROW
Studying for a Data Structures Final and your videos are really about to save me. Thanks man
A red-black tree is a binary tree that satisfies the following red-black properties:
1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL) is black.
4. If a node is red, then both its children are black.
5. For each node, all simple paths from the node to descendant leaves contain the
same number of black nodes.
Y’all be qouting CLRS for real
y u repeating the vid is 4 min long
dude you just nailed it simple short precise and a clear explanation no trash talking respect from india man
Thank you! This was so much easier to understand then my school textbook. You speak clearly and concisely. Great visuals and loved the short video time!
Note: Leafs with value Null (aka NIL) are by default Black. This means a representation of a tree with a red "Leaf" can correctly be a Red-Black Tree since its children are Null, which are Black.
A red-black tree is a binary search tree with one extra bit of storage per node: its
color, which can be either RED or BLACK. By constraining the node colors on any
simple path from the root to a leaf, red-black trees ensure that no such path is more
than twice as long as any other, so that the tree is approximately balanced.
Y’all be qouting CLRS for real
I am struggling for few hours ow to understand Red-black trees, and your videos are finally the ones that made it clear to me. Thanks and congrats! You won a new subscriber :)
Great videos, very clear and understandable. Keep up the good work!
Totally agree :D
rut
really understandable tutorial? I agree!
1:57
u say root funny, but thanks for the clear and concise explanation!
I love the way the video is made. Perfect!!
I was confused that the Node 5 is black. However, when I watched the video again, It just said all red nodes have black nodes children, but not all black nodes have red children. So, the reason why Node 5 is black is to have the same black height. Right?
This is AWESOME. Love this video, hope you become more famous
Best and simplest explanation on insertion of R-B tree on youtube. Please upload video on deletion.
Absolutely killing it, dude. Keep going and don't stop. Easy subscribe. Thx.
yeah man I feel ya even subscribed my grandma without her knowing
Aren't 9,13 and 23 leaf nodes.. Can I know why they are in red and not in black ? Please help me understand..
The leaf nodes are actually their NIL children.
Thanks for the answer. Isn't the same case for 5 as well? Can I know why 5 is seen as a leaf node when it is having NIL children?
5 isn't a leaf. Just because a node is black doesn't mean it's a leaf (see: 8, 12, 19).
Thank you
These videos are amazing keep up the good work and you'll make it big in no time
I'm not sure what you mean when you say they have a guaranteed height of O(log n) -- I thought O() is used to characterize performance -- and you could just say that the guaranteed height is < log n...
It is, but the definition of O(n) is more general than that. Most functions f(x) are equal to O(g(x)) for some g(x), and in a balanced binary search tree such as a red-black tree, height is a function of the number of nodes.
when it says that all paths from a node to its NIL descendants contain the same number of black nodes, how many black nodes does node(9) have? Does it have 1? if so doesn't node(8) have 2 black nodes to NILL?
Me watching on 2x "red-black trees in 2 minutes"
No words ... hoW to be thankful
Great tutorial🔥👍
Why the 5 on the left side isn't red?
excellent series!
I wish you had also included deletions in your r-b trees series. Good explanations though.
upload more man you are amazing
Am I right in saying that the example is not a R-B Tree because it's not balanced? There is a difference in height of 2 between the left and right sub trees from the root. The video is like 5 years old now, but I just wanted to ask for my own clarity :)
i don't know if it would be still helpfull, but R-B tree doesn't have to be AVL tree (the condition you have mentioned). R-B trees have different conditions for "being balanced"
Insert and Delete require rotations and recolorations, sometimes both.
very well explained in short time
This (and your other videos) were very helpful! Thank you very much.
Wonderful one! Btw, where is the node-removing part? Thanks.
I know you mentioned that the RBTs are balanced, but it should also be one of the criteria at 1:15
due to the criteria 3 + criteria 4, it must always be the case that it is roughly balanced since worst case longest path alternates black and red nodes while the shortest one has full black
-> height ratio between the two children of a node can never be worse off than 1:2
but why do nodes turn red sometimes? wasnt explained it NVM seems you explain it in diff video. Thats just the algorithm, we insert each node as red but change it to black if we have to match the rules.
One of the best sources to learn and revise. Kindly add more videos on concepts like AVL trees, Splay trees etc. Also, can you do a video on random sampling, which is hot topic of interviews these days and I see no one has made on it on RUclips yet.
What about node 5? That node is black and has two black children (both nil). It seems like it should be red as well.
I had the same question.... Please somebody explain
Good video. I wish you revisited the unbalanced example that is the reason for using a red-black tree (binary search tree with all children nodes being lesser).
Clearly explained, thank you!
what are the other ways to balance a BST besides red black trees?
Can you clarify what a NIL descendant is instructor ?? We need more context and clarity.
"NIL" is just the term used for any empty (not used) slots
if a node does not have a left-child, the left-child is "NIL" / NULL
to the point and clear enough
but how do we determine whether a node is red or black?
For point 4. "All paths from a node to its NIL descendants contain the same number of black nodes" is that meaning counting from _any_ node to a nil or specifically from the root to a nil?
Because if it's the latter, then in the given example that makes sense (5 to nil = 2, 12 to nil = 2, 19 to nil = 2), but then what happens if I insert "24" to this tree and it's added to the right of the red "23"?
As far as I can tell we no longer have root to nil counts being 2, but 3 if we were to look for "24" (e.g. 19 to 24 to nil = 3).
It seems I have misunderstood the meaning behind this particular point?
@Mark McDonnell When inserting there are specific rules to follow as well. Are you sure you got those right? Otherwise you don’t end up with a valid rb tree
frate ti adooroo sei un grande
why is node red and black? have the colour any meaning?
Please make a video on deletion too
What is a NIL node?
I liked everything except the way you pronounce root... Otherwise very helpful!
I've always said it weird. :)
What is weird about the way he pronounces root? Sounds normal to me.
"rewt" vs "ruet"
I didn't mind that at all. It added character to the (already well done) explanation. :)
@@nabinkhadka7168 He pronounces it as if there aren't any "o"s in the word. It isn't correct or considered to be a normal pronunciation in most of the anglophone world. It's not bad or ugly, but it isn't correct and is indicative of his dialect and region. I would imagine he is from some place in the south of the US, though there are other pockets of similar dialects in the U.S (I don't know about other countries, maybe Canadians do that too sometimes.) I don't say this to shame him or anything, he speaks perfectly fine and I sort of like that pronunciation a little bit, I am only saying this because it seems like English might not be your first language so I just wanted to help. That's all :)
nice and simple.it was all i needed thanks
Thank you so much! ☺
to be honest, I did not understand everything in this video. E.g. 1:50 . All paths from a node..... then you add "1" and a "2" next to the five. Don't know what are you counting there, dont know what the numbers are related to?! If you count the NILs then just put the 1 to the left NIL and the 2 to the right NIL....
This line " red nodes have black children ".
Shouldn't 5 be red?
Nice video.
Can you also make one on Tries please?
will add it to the list 👍🏼 taking a small break to finish some other projects, but will be back.
Update: I see. A "Nil" node is black.
I don't understand 2:27 about the Black Height. Not counting the root, the black height of the tree should be 1 instead of 2?
nil is a black node, so you have to count them as well
Wow great job! I love this!
Why is node 5 black?
GREAT videos man!
why is the height two when there's only one black root in the paths to the NIL nodes not counting the root
Because every NIL leaf is itself black and is therefore counted in the black height of a node
Awesome video thanks for sharing!
Hi, I'm teacher at a public university in Brazil. May use your material?
Sure! Just let them know where you found it.
This is great! Thanks for sharing!
Thank you very much
Good summary of CLRS 3e chapter 13.1.
Great useful content! Thanks
Thank you!!
Great video!
y is 5 not red?
Can R-B Tree contain only black nodes ?
Yes, e.g. if the tree only has a root
Why do NILs have no values (and are not represented as regular Nodes)?
"NIL" is just the term used for any empty (not used) slots
if a node does not have a left-child, the left-child is "NIL" / NULL
very elegant.
thank you
nice video,thanks bro
You actually don't explain why a node is red.
I think it arises naturally from the 4th rule
To have the same number of black nodes you need to add red nodes
10q Mr Michael
succinctly, like
thanks mic
thank you. made easy!!
still no answer why a node is red
I might be wrong, but you sound just like the Khan Academy guy for calculus...
Thank YOu
thanx
this is gonna be called Red-block tree soon
red-afroamerican tree 4Head
Thanks sir
This is helpful but the talking is very slow.
pls upload more videos
You know, every node has a black parent at height 1
>Every leaf (NIL) is black
has 3 red leaf nodes, wut
root (r-uu-t)
Nice!!
nice
I'm literally looking at 3 red nill nodes...?
where?
Notice we’re all still alive. Heaven on Earth is real. Germanic Europe approaches
AVL > R-B :)
i hate my life. why i have to learn this nub trees
interesting )
What is the point of these!? I don't get why you would want to manage more information and increase complexity.
So your professors can grill you 😅
if you watch at 2x speed he says root right 😂
ROOT ROOT ROOT ROOT ITS PRONOUNCED ROOT IM SORRY THANK YOU FOR THE VIDEO BUT PLS
he said my children were black
😊
比较基础