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

[@alanisromer9089]

y u repeating the vid is 4 min long

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

[@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

[@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

[@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

[@Salamandolo]

rut

[@ryanbarry7670]

really understandable tutorial? I agree!

[@RaleighLittles]

1:57

[@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?

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

[@ca4307]

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

[@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

[@yadhunandhanr7590]

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

[@NirajSingh-nv2jb]

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

[@ethanraymosqueda3780]

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?

[@billpetrak]

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

[@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

[@Cyber_Jutsu]

excellent series!

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

[@Kikiri197]

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"

[@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

[@Makwayne]

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

[@stephenhowe4107]

Insert and Delete require rotations and recolorations, sometimes both.

[@tecnaharmonix3416]

Please make a video on deletion too

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

[@Kevin-jf6jw]

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

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

[@shivanshpradhan8860]

very well explained in short time

[@mohammadmohammadian6706]

upload more man you are amazing

[@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

[@fasihkhan8633]

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

[@juliajeehyunkim]

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

[@leenlovesdancing3561]

Thank you so much! ☺

[@王冠信-o1c]

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

[@anukoolsrivastava4235]

to the point and clear enough

[@ruiqiliu3114]

Clearly explained, thank you!

[@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

[@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

[@ioanabiris3472]

Thank you!!

[@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

[@geezer2450]

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

[@KingUnity22]

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

[@bipinkori4060]

Thank you very much

[@palandersmuhlbradt5705]

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

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

[@ahmadrezamoodi6603]

nice and simple.it was all i needed thanks

[@chrisjasonmcqueen]

Awesome video thanks for sharing!

[@jeremylee4048]

thank you

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

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

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

[@marcofontana8308]

frate ti adooroo sei un grande

[@lingyongwang2817]

This is great! Thanks for sharing!

[@toastyshrimp1882]

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

[@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

[@alandawkins8297]

very elegant.

[@dogemaester]

Wow great job! I love this!

[@kaustubhpandey9654]

Great video!

[@ultrafalling]

Great useful content! Thanks

[@Do-Your-Work]

This line " red nodes have black children ".

[@jackkirby5287]

What is a NIL node?

[@daniellarson8291]

Shouldn't 5 be red?

[@melbexdeleon8951]

GREAT videos man!

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

[@alfredoespinozapelayo]

Why is node 5 black?

[@RedPandaDesu]

Good summary of CLRS 3e chapter 13.1.

[@dmytromarchuk3023]

succinctly, like

[@IjzerKeizer]

root (r-uu-t)

[@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

[@de9989]

nice video,thanks bro

[@trollerninja4356]

y is 5 not red?

[@oliveruhlar351]

Can R-B Tree contain only black nodes ?

[@77Raffi77]

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

[@mohamednofal5256]

thanks mic

[@hurrykrishna]

thank you. made easy!!

[@harrisonn9792]

Thank YOu

[@pustkaimrok]

still no answer why a node is red

[@fethiourghi]

thanx

[@rohitippili3834]

Thanks sir

[@buzayehuyitbarek3877]

10q Mr Michael

[@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

[@jordan1543]

spectacular, you may come to my bar mitzvah

[@MichaelSambol]

Send me the details. :)

[@marco.nascimento]

nice

[@dhruvamishra5857]

pls upload more videos

[@kafychannel]

interesting )

[@Nevverglow]

this is gonna be called Red-block tree soon

[@jmm00702]

red-afroamerican tree 4Head

[@ZandPyr]

This is helpful but the talking is very slow.

[@motoliao]

Nice!!

[@RobertPodosek]

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

[@TonyKaku-g8n]

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

[@FightTheByte_]

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

[@ondrejmatousek9723]

where?

[@fireguardianx]

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

[@hangchen]

😊

[@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 😅

[@vijaysaikonatham68]

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

[@adamday5045]

ruuuuuuuuuuut

[@antwanwimberly1729]

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

[@10bokaj]

ruuurt

[@MichaelSambol]

tomato / tomahto 😎

[@mati124]

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

[@isaacruelascastillo4952]

he said my children were black