Nice video. I personally would have added rule #6: "a new node is always a red node".
@Z00CE
7 жыл бұрын
That's an insertion rule, not a property of red-black trees.
@acathosh
7 жыл бұрын
You would think that making a new node Red is exclusive to red black trees and a pretty basic property :o
@mwyt345
7 жыл бұрын
I agree with HK Normann, so he's probably smarter.
@AaronOrtiz
7 жыл бұрын
It is the question most newbies (like me) would ask if your video were the first they ever heard of a Red-Black tree.
@stephenhowe4107
5 жыл бұрын
I agree with this. Insertion always takes place at leaf nodes, so you make the new node black, immediately you violate the black height rule. In contrast, if you insert a red node, there is a good chance its parent is black, therefore no violations at all to fixup. The 1st situation would occur 100% of the time, the 2nd situation has no violations some of the time, therefore it is a no-brainer for new nodes to be red.
@temrenalican4570
7 жыл бұрын
It looks really complicated with the little sub tree swappings when you try to memorize them. Just know that after rotating the subtree's of the rotated nodes must preserve the binary search tree rules, so there's really only 1 way you can stick them in the tree. Don't try to memorize the cases
@mfteng1897
9 жыл бұрын
Excellent, very clear and definite. Thanks for sharing.
@pvr7130
10 жыл бұрын
Just what I needed! Thanks Zooce!
@Rishabh-op6kc
6 жыл бұрын
A Computer Engineer
@michaelsalam1475
6 жыл бұрын
Explanation was awesome, but it would have been much better if the pointer was a bit bigger or visible.
@1230986666
9 жыл бұрын
That was very well presented, thanks a lot!
@kayeskaykobad2670
9 жыл бұрын
Awesome tutorial thanks for taking the time to make it
@MrPoddilolli
8 жыл бұрын
Only engineers start with part 0 ehhm ehhm binary
@prashanthvaidya1358
7 жыл бұрын
Beautifully explained! Thank you so very much :)
@irofitosa8915
8 жыл бұрын
Thank u u helped me a lot to understand this Tree complete with this way with other trees I really like the video and ur explanation GD job
@korneliuspasztor7465
8 жыл бұрын
Finally someone that explains it from the very basic THX a lot! ^^
@pingpong9959
8 жыл бұрын
You should also upload RB tree deletion video. Btw, thanks for the upload
@chantellerae2462
9 жыл бұрын
Thank you so much for this tutorial, it really made me understand. Could you also explain deletion. Right now i can only delete leaf nodes.
@Z00CE
9 жыл бұрын
chantelle rae, for deletion, you first delete the node as if the tree is a simple BST (i.e. forget about the colors). Then you do a fix if you deleted a black node. There are quite a few cases here, too many to write out in a comment, so do a search for this (you'll definitely find a solution - there are a couple ways of doing it). In the meantime, when I find a moment to make a video about deletion, I'll do so. Thanks for watching!
@NithishJVNIT
8 жыл бұрын
that's good enough for day before exam preparations!! :D TYSM!! ^_^
@seyhahiem
6 жыл бұрын
nice explanation thank so much
@lalithahariharan3260
9 жыл бұрын
In case 2,after the rotation,x became the parent of p .but it is also violating the red rule right?
@stevefrt9495
6 жыл бұрын
Nide explanation, thanks
@ZipingL
8 жыл бұрын
well explained, good illustrations
@thapelo7911
7 жыл бұрын
Thanks, well explained!
@lindsayj9703
9 жыл бұрын
This was very helpful!
@KnightWhoSaysNi
9 жыл бұрын
who starts with part 0 ??? .......
@Z00CE
9 жыл бұрын
Vincent Proxy, wizards start with part 0...
@OnyxtheFortuitous
9 жыл бұрын
Peter van Meijl Yep.
@jordiaceituna1
9 жыл бұрын
every array
@KiraleosAkis
8 жыл бұрын
+Vincent Proxy Computer scientists.
@kushagraagarwal2460
7 жыл бұрын
:D
@jonnypasta
8 жыл бұрын
I think you miss something in the Properties, because according to them, a tree with all nodes black would be a valid Red-Black tree (it doesn't violate any of the rules you listed).
@Z00CE
8 жыл бұрын
There is a valid red-black tree with all black nodes, if the tree has one node. There are also insertion rules, which are the following: 1. The node being inserted must be a red node. 2. Insertion follows the rules of a binary search tree. The above two `rules` are not `properties` of a red-black tree, they are just rules about how to interact with a red-black tree. I hope this answers your question. Thanks for watching!
@jonnypasta
8 жыл бұрын
didn't catch the insertion rules, thanks!
@pellergin
8 жыл бұрын
At 8:32, The tree at the lower left hand side has a red uncle, isn't that violation?
@pellergin
8 жыл бұрын
+pellergin Oh nvm, a black node, may have a red uncle. Thanks for the video. The best I came across, introductory wise.
@mitrasree
6 жыл бұрын
Y O U A R E B R I L L I A N T !!! Tomorrow is my data structure exam and I can't thank you enough
@elvazheng809
8 жыл бұрын
I dont understand at 4:28. Why the uncle node cannot be red and we need to change it to black?
@anubhav111196
7 жыл бұрын
The problem was that parent node as well as child node was red which was a violation that's why.
@wing2yan
8 жыл бұрын
In case 1, how is it that you change the root color to red and leave it like that? Doesn't that violate the Red Black properties?
@Z00CE
8 жыл бұрын
+wing2yan Here I'm illustrating that you reevaluate from the "root" node. Notice the dotted line upwards from the root, indicating that this "root" node may be that actual root of the entire tree, or there could be more nodes above (i.e., this is the root of a subtree). Great question, thanks for watching!
@zaavanrichards3709
8 жыл бұрын
So suppose it was the root node, after the color correction, would you just change the color of the root to correct it?
@Z00CE
8 жыл бұрын
Correct!
@Knot2goodAtIt
9 жыл бұрын
nice metaphor with he families
@ripplecutter233
7 жыл бұрын
By 'nil node', do you mean the actual nil pointed to by the leaf, or the leaf that points to a nil?
@Z00CE
7 жыл бұрын
I mean the nil pointed to by the leaf. For conceptual purposes, we count the nil as a node.
@ripplecutter233
7 жыл бұрын
zooce +1 much obliged
@mrMS-mc7yq
7 жыл бұрын
i am Vietnamese. thanks so much
@tejas8048
7 жыл бұрын
very well explained. Thank you. Where can I find your first video after subscribing to these?
@Z00CE
7 жыл бұрын
Thanks for watching! Here's a link to my page: kzitem.info
@tejas8048
7 жыл бұрын
Thank you. Do you have something on interval tree ?
@renyjohnjose1992
8 жыл бұрын
is'nt root node supposed to black in the first case. as you have stated in propeties
@Z00CE
8 жыл бұрын
Yes, the root node must always be black. While handling violations, it may happen that the root becomes red, which is yet another violation which you must handle (simply by changing the color to black).
@yifei663
5 жыл бұрын
What's the tool to make this ?
@Hump4free
7 жыл бұрын
Good quality video. What software are you using for this?
@Z00CE
7 жыл бұрын
It's called Pixelmator.
@Videos-ee2dy
6 жыл бұрын
what if in case 2 the uncle is red plz some body help
@lostandlast2829
9 жыл бұрын
Nice!
@AaronOrtiz
7 жыл бұрын
22ond ordinal, not 20-second (duration) :)
@MODjack92
8 жыл бұрын
pleaseeeee keep up the good work, thnx (:
@DheerajPandey66
8 жыл бұрын
Point number 3 is incorrect. If there are children in red node they must be black children else they can point to null also(red node can be leaf)
@Z00CE
8 жыл бұрын
+Dheeraj Pandey let me clarify. According to property 2, null is considered as a black node. So if red is a "leaf" node, then both of its children must be null, and since property 2 says that null is a black node, then red can never be a leaf node. Also, you mention, "If there are children in red node they must be black children," which is the same as saying, "Every red node has two black child nodes." If this doesn't make sense, let me know and I'll try to explain further. Thanks for watching!
@Me1kaa
8 жыл бұрын
I can't implement dat? am i stupid?
@MODjack92
8 жыл бұрын
+Me1kaa no ... just take it easy (:
@ufpauer
7 жыл бұрын
Your case 3 is wrong, violated property 4! You should not change the uncle color, it must be black.
@Z00CE
7 жыл бұрын
The uncle doesn't change color (the uncle in this case is the node labeled 'Y').
@lalithahariharan3260
9 жыл бұрын
In case 2,after the rotation,x became the parent of p .but it is also violating the red rule right?
@amukher1
8 жыл бұрын
+lalitha hariharan Yes, it becomes case 3. So you apply case 3 to resolve the violation. Case 2 is always converted to case 3 and resolved.
Пікірлер: 71