Red Black Trees 2 Example of building a tree

[@mohsinak5317]

Rob, it has to be said.... This is really the best and one of the simplest video about RBT which of course covers all the scenarios. Thanks a ton. Big thumps up for this.

[@mikexrag]

This playlist on RBTs is EXCELLENT. You explain everything so concisely, patiently, and methodically- the students at SD State are lucky to have you.

[@tarunsharma2971]

Confusing but the way you're teaching is just on another level .

[@VeraVeraniego]

Man, I've tested this method on some random inputs and it works just fine, god, there's no words to describe how grateful I am, you made me understand this Data Structure topic.

[@OGSilentMan]

wow this seems complicated to learn at first but Mr. Rob Edwards is so helpful in teaching the ideas and concepts! LOVE FROM INDONESIA

[@tearycruise9188]

Just wanted to say that after watching this video and the first video (the rules of RB trees), I actually learned more than I did in my 3 hour lecture class. Thank you so much for making everything clear and going step-by-step while explaining everything that you do. It helps a ton! Many thanks again!

[@niyazshkl9584]

I just want to say: Thank you so much. I have learned everything so clearly from this video than 1 full week from my university class.

[@firstignitor]

the finest teacher I've ever met online. thanks sir for your great work. how I wish you were my Data structures and algorithms lecturer. the book which made me cry but now everything's looks to be simple and easy thanks

[@adityashukzy]

Very well-explained, Rob! Was easily able to follow! Also, fancy handwriting hehe. Kudos from India :)

[@alirezaalizadeh4080]

This is the best video i have ever seen !!! Thank you so much 🤩

[@georgegeorge581]

You are the reason I passed data structures , thank you !!

[@asadleon]

Best easy and beautiful explanation I have ever seen. Thanks a lot.

[@marisavka6388]

It's a clear explanation. Thanks for your time for this awesome work. It's really helped a lot

[@richythampi303]

Hands down the best and most simplest explanation on RBT! Thank you very much Sir!

[@123coolmik]

This is my new favourite series!

[@mohamedyahya9549]

you saved me on my night before my exam,if I passe I own you a lot mister, thank you very much

[@benjwill3828]

really good video, thank you very much. i watched a bunch of those videos and never completely understood the red black trees but this lecture is really clear and intuitive!! thanks!

[@dimitardraganov3538]

BEST data structures lessons. Thank you so much ! Great explanation !

[@kaituo1803]

Amazing video. Subscribed immediately after watching this one

[@benjamimo1]

Very good video! High production value, step by step changes and covered all cases in your example.

[@swindler1570]

Who else is studying for their final right now?

[@JohnWideCock]

me

[@frukzey530]

I have to implement it

[@reyhanfirmanda832]

only for final gang

[@swindler1570]

@@frukzey530 I had to build a 2 3 tree for my last project in that class. In a language I'd never used. :s

[@29battles10]

2020 finals my friend

[@jamespogg]

thank you! so simply explained! red aunt, color flip. black aunt, rotate!

[@Allchemyst]

Every video from this channel has been utterly fantastic. This channel is by far the most helpful and clear I've been able to find on YT. Only caveat with this one is that, as your average colorblind bastard, I really, really cannot follow the explanation here... The bright yellow marker would've made for a better contrast, I'd suggest.

[@testtest-lc4xz]

Best explanation I've seen.

[@KiasHafiz]

He's not left handed. This video is horizontally flipped. That's how he seemingly writes backwards so well, because he's actually writing forwards.

[@UrzaMancer]

I came here to post this, but if what you say is true, why does he write "left rotate" with the arrow pointing to the right?

[@rzaaeeff]

@@UrzaMancer that arrow doesn't represent direction of the rotation, it's just to denote ongoing process or the next step. FYI, he uses smth like this: www.learning.glass/

[@okishan]

@@UrzaMancer the arrow is going down. Not to the right or left. It's going down along the edge.

[@vd853]

So if when doing this and the root becomes red 17:44 you always set the root black and it's children red?

[@ricardoduran1169]

Well explained. Thanks edwards

[@Play-Date-Care]

Can anyone explain the color reset at 10:00, the aunt is black, why reset the color?

[@The_Celestial_Fox]

I will refer you to 5:27 for your answer. Hope that helps!

[@muditmalpani8704]

i have a black aunt, how do i rotate ?

[@NamanKashyap5]

Thank you so much ;) btw who are wondering how the video is made let me tell you, They are using a LightBoard setup.

[@umang9997]

Can we get a case where we have different number of black nodes in a path?

[@wow5212]

how did someone even come up with those rules. Im always impressed what humans can come up with

[@clynepeak]

Excellent video!

[@thomascook736]

This is a great video, helps with implementation, good stuff

[@ipolit-beats]

it is the coolest explanation ever, by the way, the table is superb nice ^_^

[@rodrigoresende8328]

this video makes it so damn easy it could teach a tree

[@NavneetKumar-lg3nv]

amazing explanation

[@daleprather3026]

Can you paint your face black next time? ;) Your videos are fantastic. This is the best one on youtube on red black trees.

[@blakef.8566]

Being colorblind makes this video harder to follow

[@CodeSuccessChronicle]

Please be strong....

[@elliesera2948]

That's tough! look toward a different lesson or better yet look into using some software that will provide a colorblind assistant graphic overlay for your desktop

[@marcuslin1792]

literally identify the colors when he swaps the pens lol

[@bama2619]

2:33 Example of Colorflip because we have two consecutive red elements(violation) and we have red aunt, after COLORFLIP we have to make the root black (3:25); 3:58 We INSERT 6 and we have got 2 red elements(violation). 4:17 Null is always black, and it is a black aunt of 6, so we need to ROTATE 5:25 We have RL rotation in red zone. This is like in AVL tree motion (by Abdul Bari), instead of double rotation we make one simple. 6:08 After rotation we need to fix (RESOLVE colors in parent-grandparent-aunt triangle) and get: B / \ R R within the triangle (always working within one triangle). 7:05 We INSERT 8 (adding is always red) and we have violation (two consecutive reds) and red aunt, so we COLORFLIP in the triangle of aunt, grandparent, parent. So we change colors into: R / \ B B 8:32 it is interesting that the children of the root can be black or red, alternatively one of them can be red or black. 3 states: all black, all red, one of them red(meaning another is black). And that is ok. As we can see. 8:56 = 4:17 9:38 LL-rotation (we drag over nail the one above two consecutive elements down raising the two red up) 10:47 After rotation we RESOLVE colors. We have three consecutive reds, so we need to make equal number of black nodes on the left and the right sides of the root to have the balance. (root is always black, then we can have red and then black) 10:51 INSERT 10, it is red. Again violation, again ROTATE and FLIPCOLORS in parent - grandparent -aunt triangle. 14:38 ROTATE two reds in LL-rotation (dragging), 5 is dragged over nail and will hang from 3. (Abdul Bari good note). 15:04 RESOLVE colors (black root, red layer, black layer). 15:53 checking validity of the tree ( counting black node on the left and on the right from the root, they should be equal, which is a balanced tree. 17:00 Valid RBT is not always valid AVL tree 17:10 Conclusion. BOOLEANS for colors, 6 rules for REBALANCING the RBT

[@FredoCorleone]

Where does he teach about the rotations?

[@ForzaAllegri]

great video, I would love to know how the 5 become right child of three.

[@arunprabakar6891]

Could you please add a scenario to violate black height property of rb tree and explain how to solve it?

[@kamithpiumal4887]

Best lecturer

[@whitecloud1271]

Is he writting on a some kind of glass??

[@zhangmeihao4044]

这个老师讲的好清晰！！！

[@DenisBrilliantov]

What is the definition of an aunt node?

[@sarasaeed8677]

Thanks for the video, but how do you the direction of rotation? like left-right or right? Thanks

[@jalindrinelastname7137]

Explains in a later video: kzbin.info/www/bejne/f6aqZIqJlqmoo8U That really was the question I had here, though: How can you call moving from 7>8>9 to 79 a rotation? If it were a chain, you'd have moved from attaching the 7 link to the 6 link to attaching the 8 link to the 6. That's not really a rotation at all -- at least it's a very bad metaphor, almost as bad as talking about red & black uncles & aunts. And there's obviously an intro to binary trees I'm missing b/c, um, why are we playing this game at all? Are the rules just so we have a properly arranged tree that searches in the proper Big O? Pretty sure that's yes, but how about say that and explain how it works?

[@AlexeySilichenko]

Great, thank you very much, it was very helpful!

[@ramseywalid2715]

Excellent!

[@kasrayazdani8628]

This was helpful. Thank you!

[@cometk.9878]

Thx professor it's really helpful!

[@pouyajamali6779]

great video

[@SachinVerma-xo4fj]

HI. Could you make up an example where number of black nodes in different paths are different. I have tried already with 10-11 nodes and could not reach back imbalance. ANy heads up?

[@akabaku]

You can use this service as a try - www.cs.usfca.edu/~galles/visualization/RedBlack.html

[@marksladen2901]

@@akabaku Thanks so much for posting this!!!!!

[@umang9997]

Can we get a case where we have different number of black nodes in a path?

[@tausal1]

great explanation!

[@PratikShende91]

amazing sir......nice video

[@dbf8014]

3:47 this one seems confusin to me the rotations

[@friendlylaser]

Took me 20 seconds to understand how is he writing mirrored text so it shows correctly on viewer side, haha. (The answer is - video is mirrored). This is very cool idea for blackboard for video lessons.

[@UberOcelot]

I can write backwards, but this is impressive!

[@halcyonramirez6469]

UberOcelot im sure mirrors or something was used. The prof didn't write in reverse

[@bridge_four]

I think cameras have that mirror effect. He's not really writing backwards.

[@sebastianlacki8483]

It's called Learning Glass pretty obvious but genious haha

[@damejelyas]

THEY PROBABLY FLIPED THEY VIDEO AT EDTING

[@techotopo]

you're pretty stupid

[@davidhanover8224]

thank you so much for this channel. was this sanctioned by the csu's? it seems borderline illegal to have these classes online for free!

[@kerednus1096]

thank you so much

[@menonaskatgmail]

Thank you

[@nishaindesilva3738]

Thank you sit first i found some anomalous result but soon adapt.I was also greatly absorbed by the colours though , they are great..

[@anibelle28]

thank you so much!!

[@pelin9376]

perfectly explained

[@CTde110]

If the confilict is in the left child's left subtree, you do a right rotation.

[@theodhorzhobro4646]

ig left leeft then right and if right right then left i was just gona ask that xD

[@elvissibetyu7228]

Thank you a lot

[@Sparksy]

the rotation is still a bit confusing

[@palwan7190]

why western teachers are too good

[@travel_with_dimpi]

Thanku Sir

[@tharunadithya8743]

RobBackwards suits you much better than RobEdwards😂 P.S.: Just 4 fun🙃

[@asherjohnson5372]

How can he write and read in reverse??

[@programmingeverything]

the whole world calls it uncle and you decided to use aunt. great

[@ShaktishaliGamer]

sir pleas uploading these kind of videos by the way you are cute xD

[@dhimanchattopadhyay5920]

excellent explanation, only one suggestion - if the background was white ,professor could have used black color for black node.

[@friedchickenboba9906]

Pink Blue Trees

[@ankitsharma8221]

best !

[@YusufPatoglu]

Even if you had black pen we still couldn’t see it lol

[@TheImpermanentTao]

i dont think this is a left leaning RBT in case anyone got confused like me

[@SearchingPeaceInside]

On addition of 8, tree was unbalanced at root, We need to rebalance it instead of adding 9 to it.. this explanation is wrong!!

[@TZCoder]

Dont think so why was it unbalanced?

[@stopplanet184]

@@TZCoder balance factor of node (3) becomes 2

[@DuyTran-ss4lu]

Up !!!

[@kaleynguyen3879]

is that you :)))

[@Terminex19]

Great explanation, but "poor implementation" color-wise for colorblind people. The other color combinations are better to follow along the examples. Things like red and green or yellor, or blue with green or yellow. Anyways, great content all around except for this particular topic.

[@annaportugal1657]

Im in love with you

[@najmhassan123]

[@Dgsrgv]

Its not the best... since he didnt mention the most important thing about color flipping: At which node are we doing the flipping. This is a very elementary mistake

[@v0rtex-]

The color flip only involves the immediate parent and its two children. Specifically, you would change the colors of the following nodes: - The parent node of the two consecutive red nodes (the red node with two red children) changes from black to red. - The two children of the parent node (which are red) change from red to black.

[@codingsavid6509]

Thanos

[@FredoCorleone]

Why someone should memorize all this other than passing an exam?

[@bhavishshetty5332]

interview,entrance exam,if u r going to be a lecture or willing to join R&D department of any company etc.

[@yusufklc7821]

l watching this while thinking how coul he can write with respect to our view.

[@Plauud]

daddy

[@damejelyas]

Aaaaaaaaaaaaaaaand Sub.

[@sbundaba4399]

You are supposed to balance the tree at (3:14 min). Please change it or delete the video.

[@任安明]

Sbu Ndaba what's wrong?

[@bridge_four]

No he's not, What are you even talking about, You don't take any action when there are two black nodes.

[@AA-xk1uv]

This is so fucking weird.

[@bryanstanford606]

racist

[@doingsneakypeakylike]

the color choice was very confusing

[@igniterook]

wrong

[@haydo8373]

no

[@AmirAli-gv7kn]

your concept is what you said