Red-black trees in 4 minutes - Intro

[@arpitchristy9788]

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

[@ThomasEdits]

if only you could go through a red black tree instead

[@dennisekiller]

@@ThomasEdits GO SLEEP, UNI TOMORROW

[@DarkDay2012]

Studying for a Data Structures Final and your videos are really about to save me. Thanks man

[@EskyDinpuiaChhangte]

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.

[@letsgoo4663]

Y’all be qouting CLRS for real

[@Lanaohla]

y u repeating the vid is 4 min long

[@ata500]

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!

[@sj1997]

dude you just nailed it simple short precise and a clear explanation no trash talking respect from india man

[@Tourach74]

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 :)

[@MichaJabczynski]

Great videos, very clear and understandable. Keep up the good work!

[@thomasjinton3862]

Totally agree :D

[@ante1337]

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.

[@EskyDinpuiaChhangte]

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.

[@letsgoo4663]

Y’all be qouting CLRS for real

[@ryandavis7506]

Absolutely killing it, dude. Keep going and don't stop. Easy subscribe. Thx.

[@regisschulze6678]

yeah man I feel ya even subscribed my grandma without her knowing

[@yadhunandhanr7590]

I love the way the video is made. Perfect!!

[@juliajeehyunkim]

This is AWESOME. Love this video, hope you become more famous

[@ca4307]

u say root funny, but thanks for the clear and concise explanation!

[@fasihkhan8633]

No words ... hoW to be thankful Great tutorial🔥👍

[@Salamandolo]

rut

[@ryanbarry7670]

really understandable tutorial? I agree!

[@RaleighLittles]

1:57

[@NirajSingh-nv2jb]

Best and simplest explanation on insertion of R-B tree on youtube. Please upload video on deletion.

[@CaveDave]

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....

[@geezer2450]

This (and your other videos) were very helpful! Thank you very much.

[@ToonGnarizard]

excellent series!

[@shivanshpradhan8860]

very well explained in short time

[@mohammadmohammadian6706]

upload more man you are amazing

[@ruiqiliu3114]

Clearly explained, thank you!

[@firezdog]

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...

[@matthewrenze5922]

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.

[@Makwayne]

Me watching on 2x "red-black trees in 2 minutes"

[@mrmansir3734]

I know you mentioned that the RBTs are balanced, but it should also be one of the criteria at 1:15

[@ThomasEdits]

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

[@dogemaester]

Wow great job! I love this!

[@melbexdeleon8951]

GREAT videos man!

[@muralikrishnaraju]

Aren't 9,13 and 23 leaf nodes.. Can I know why they are in red and not in black ? Please help me understand..

[@MichaelSambol]

The leaf nodes are actually their NIL children.

[@muralikrishnaraju]

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?

[@MichaelSambol]

5 isn't a leaf. Just because a node is black doesn't mean it's a leaf (see: 8, 12, 19).

[@muralikrishnaraju]

Thank you

[@jbob2015]

These videos are amazing keep up the good work and you'll make it big in no time

[@honglichen4670]

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?

[@anukoolsrivastava4235]

to the point and clear enough

[@ahmadrezamoodi]

nice and simple.it was all i needed thanks

[@rishabhjain2404]

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 KZbin yet.

[@chrisjasonmcqueen]

Awesome video thanks for sharing!

[@lingyongwang2817]

This is great! Thanks for sharing!

[@randomhappyguy6719]

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?

[@Vipe12358]

nil is a black node, so you have to count them as well

[@Mattamorphosis]

Q: Why is the longest path no more than twice the length of the shortest path? A: Consider an arbitrary red-black tree. Notice the following: Each red node has a black node as its child. Therefore, the number of red nodes is less than or equal to the number of black nodes in a root-to-leaf path (justification: each red node can be paired up with a black node, and there could exist unpaired black nodes). Now, consider the shortest path in the tree. Since each path has the same number of black nodes, the shortest path must contain the least amount of red nodes. The longest path, on the other hand, contains the most amount of red nodes. Due to our upper bound on the number of red nodes, and the fact that the shortest path could theoretically contain no red nodes, then there are at most twice as many nodes in total in the longest path versus the shortest path.

[@ultrafalling]

Great useful content! Thanks

[@stephenhowe4107]

Insert and Delete require rotations and recolorations, sometimes both.

[@billpetrak]

I wish you had also included deletions in your r-b trees series. Good explanations though.

[@leenlovesdancing3561]

Thank you so much! ☺

[@marcofontana8308]

frate ti adooroo sei un grande

[@Do-Your-Work]

This line " red nodes have black children ".

[@kaustubhpandey9654]

Great video!

[@jackc451]

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 :)

[@eklipina]

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"

[@thomasfischer9289]

What about node 5? That node is black and has two black children (both nil). It seems like it should be red as well.

[@oliverm4633]

I had the same question.... Please somebody explain

[@RedPandaDesu]

Good summary of CLRS 3e chapter 13.1.

[@drrpedpeppadsa]

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).

[@王冠信-o1c]

Why the 5 on the left side isn't red?

[@ethanray19]

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?

[@tecnaharmonix3416]

Please make a video on deletion too

[@Kevin-jf6jw]

Wonderful one! Btw, where is the node-removing part? Thanks.

[@TheLoyalpain]

I liked everything except the way you pronounce root... Otherwise very helpful!

[@MichaelSambol]

I've always said it weird. :)

[@nabinkhadka7168]

What is weird about the way he pronounces root? Sounds normal to me.

[@antoniojg-b8284]

"rewt" vs "ruet"

[@codyromano7868]

I didn't mind that at all. It added character to the (already well done) explanation. :)

[@valeskavictoria1278]

@@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 :)

[@de9989]

nice video,thanks bro

[@ayushagarwal4253]

Nice video. Can you also make one on Tries please?

[@MichaelSambol]

will add it to the list 👍🏼 taking a small break to finish some other projects, but will be back.

[@antwanwimberly1729]

Can you clarify what a NIL descendant is instructor ?? We need more context and clarity.

[@ThomasEdits]

"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

[@mrmansir3734]

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.

[@bipinkori4060]

Thank you very much

[@KingUnity22]

but how do we determine whether a node is red or black?

[@markmcdonnell]

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?

[@harbl2479]

@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

[@alandawkins8297]

very elegant.

[@daniellarson8291]

Shouldn't 5 be red?

[@hurrykrishna]

thank you. made easy!!

[@toastyshrimp1882]

what are the other ways to balance a BST besides red black trees?

[@pedroalbertogomes3809]

Hi, I'm teacher at a public university in Brazil. May use your material?

[@MichaelSambol]

Sure! Just let them know where you found it.

[@crunkbucha4667]

why is the height two when there's only one black root in the paths to the NIL nodes not counting the root

[@lzurzolo]

Because every NIL leaf is itself black and is therefore counted in the black height of a node

[@Jeff-zc6rr]

You actually don't explain why a node is red.

[@iulianalexandrudragan5531]

I think it arises naturally from the 4th rule

[@Craffunky]

To have the same number of black nodes you need to add red nodes

[@palandersmuhlbradt5705]

why is node red and black? have the colour any meaning?

[@ioanabiris3472]

Thank you!!

[@Nevverglow]

this is gonna be called Red-block tree soon

[@jmm00702]

red-afroamerican tree 4Head

[@trollerninja4356]

y is 5 not red?

[@jackkirby5287]

What is a NIL node?

[@TonyKaku-g8n]

You know, every node has a black parent at height 1

[@alfredoespinozapelayo]

Why is node 5 black?

[@oliveruhlar351]

Can R-B Tree contain only black nodes ?

[@77Raffi77]

Yes, e.g. if the tree only has a root

[@Aerosmithism]

Why do NILs have no values (and are not represented as regular Nodes)?

[@ThomasEdits]

"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

[@mohamednofal5256]

thanks mic

[@pustkaimrok]

still no answer why a node is red

[@buzayehuyitbarek3877]

10q Mr Michael

[@fireguardianx]

I might be wrong, but you sound just like the Khan Academy guy for calculus...

[@jeremylee4048]

thank you

[@IjzerKeizer]

root (r-uu-t)

[@player6769]

if you watch at 2x speed he says root right 😂

[@dmytromarchuk3023]

succinctly, like

[@RobertPodosek]

>Every leaf (NIL) is black has 3 red leaf nodes, wut

[@FightTheByte_]

I'm literally looking at 3 red nill nodes...?

[@ondrejmatousek9723]

where?

[@dhruvamishra5857]

pls upload more videos

[@motoliao]

Nice!!

[@ZandPyr]

This is helpful but the talking is very slow.

[@mati124]

i hate my life. why i have to learn this nub trees

[@rohitippili3834]

Thanks sir

[@vijaysaikonatham68]

Your concept is wrong , because in red black trees root and leaf nodes should have same color

[@KublaiKhan2025]

At 1:31 the leafes 9, 13, 23 are NOT black

[@isaacruelascastillo4952]

he said my children were black

[@matejbolta]

AVL > R-B :)

[@harrisonn9792]

Thank YOu

[@waleedkhan6819]

ROOT ROOT ROOT ROOT ITS PRONOUNCED ROOT IM SORRY THANK YOU FOR THE VIDEO BUT PLS

[@antwanwimberly1729]

Notice we’re all still alive. Heaven on Earth is real. Germanic Europe approaches

[@thezman2759]

What is the point of these!? I don't get why you would want to manage more information and increase complexity.

[@MichaelSambol]

So your professors can grill you 😅

[@fethiourghi]

thanx

[@marco.nascimento]

nice