A really nice video to watch, even when I was tired and couldn't focus well I was able to still understand, I still recommend for whoever is studying trees or other data structures to go to Wikipedia and read about it, it's story and so on
I would really appreciate it if you did a video on the delete operation of the red black tree but other than that the video is pretty good and explains everything in detail
9:40 This is exclusively for a mutable tree where you need the parent pointer on the node. If you want to create an immutable persistent version then you can't have the parent two way binding as you would need to touch every node in the tree during a mutation which would ruin the time complexity. Check out path copying for folks interested in an immutable persistent version!
Your videos are very useful and easy to understand, respect for your efforts! Regarding the current one, I have two questions, both concerning the handleLeftSituations and handleRightSituations. - First about the recoloring by invoking the flipColor method. I tried to write it myself, as an exercise and in my understanding, the nodes, that change colors in left(right) heavy situations should be the GrandParent(GP) and the Parent(P), as it is in your example, but in left-right(right-left) situations the GrandParent(GP) and the Node(N) should be recolored. - Second - the last row - invoking of recolorAndRotate method and the parameter we pass. Let's consider the handleLeftSituations case. I think it should be the other way around - passing GP as a parameter in case of left heavy situation and passing P in case of left-right situation. I created the following trees: 1) Left Heavy Situation - We have Root(key 64) -> left child is our GP(key32) -> left child is our P(key 16) -> left child is the node we insert N(key 8). After the rotation(right rotation), we have the tree now as R(64) -> left child is P(16) -> left child is N(8) and P(16) -> right child is GP(32). So now if we pass our current P(16) in recolorAndRotate method, we will pass a node, that is already processed and I think we should pass N(8)'s newly assigned GP(64), our Root(64), which is now our P(16)'s newly assigned parent. 2) Left - Right Situation - We have R(64) -> right child is our GP(512) -> left child is our P(128) -> right child is the node we insert N(256). After the first rotation(left) we have R(64) -> right child GP(512) -> left child N(256) -> left child P(128) and after the second rotation we have R(64) - > right child N(256) -> left child P(128) and N(256) -> right child is GP(512). If we pass our current GP(512) we will pass a node that is already processed and I think we should pass our N(256)'s newly assigned P(64), which is our Root(64). Perhaps I miss the moment when you reassign the Node and Parent variables to point to the otherone's address in memory, i.e. swapping those variables' values. Of course, I assume that I am completely wrong in my understanding, as I am new to this. Hopefully I managed to explain what I mean without pictures or drawings. Apology for the long comment and I will be happy to read your answer, as I had hard time in attempts to understand if(where) I do the things wrong.
Hello! Thanks a lot, happy to help :) Yes, your explanation was really clear! The part of the implementation you addressed is actually explained from 5:10 to 8:45. The code written accurately reflects this part and in it we explain all rotation / recoloring cases. Additionally, the rotation cases are explained more in depth in the AVL video: ua-cam.com/video/Jj9Mit24CWk/v-deo.html if you want to take a look at it as well! Cheers :)
Hey, thank you for your Videos. i think the question made at 8:36 was not answered in the remaining video. Generally speaking, why do we have to check after rotating, since the node on top(old parent in heavy left, new inserted node in left-right) is recolored to black, and can not cause a red-red problem?
Testing this class, I can see after creating root, at the second insertion , into the recolorAndRotate method, grandParent will be null, so the creation of the uncle will raise a NullPointerException... I am wrong?
I think you give a really good introduction but i think i need to study it once again in order to grasp everything. You should actually write and mark the points that are important in the video, also the thing that you don't give enough emphasis on the words that are important.
@@geekific it was my mistake the final tree was perfect but man I have a big problem rn can you help me? I'm doing a report on trees performance on inserting and there is some configuration of the tree the implementation just cant handle and the exception is thrown "Cannot read field 'left' because 'this.parent' is null" or "cannot read parent.color because parent is null" out of 10000 elements it can only insert like 17 and boom NullPointerException parent is null do you have some idea what it might be? I have no time to implement another RB Tree and fixing it is really giving me a hard time
I just debugged it the problem is in this line: recolorAndRotate(node.isLeftChild() ? parent : grandparent); he checks if node is a left child but node is the newly inserted node who rotated left and then right and became the root of the size 3 tree. He has no parent
Hey, at around 10:40 I mentioned that it was covered in previous videos as it is similar to the BST and AVL traversal. Feel free to check this video: ua-cam.com/video/zIX3zQP0khM/v-deo.html at around 6:27 for the explanation and 11:04 for the implementation. Cheers :)
Oh my God😵💫😵💫😵💫😵💫😵💫 Dear Sir, pls say me honestly, do your bear in mind right now all this mechanics and its java implementation??😮 My guess is that even most ppl from MAANG cannot show code for redblack tree from the top of their heads. It's educational to understand it but I doubt that the majority can show it at request. Looks like a star ability:) (extra ability). Am I right or wrong? 🤔
Yeah, it is not straightforward, like I can tell you all the mechanics and how they work, but I will not be able to come up with the perfect implementation from 1st try of course.
With real world data, Red-Black trees are not generally more performant than AVL trees. The conclusion of this study is worth a quick glance: benpfaff.org/papers/libavl.pdf
Hey, thanks for sharing it was a good read! Ripped straight from the document shared: "In two of our experiments red-black performance was better than AVL performance and in the other one it was the reverse; in one, splay trees were better than either". So, it all boils down to the data you are using, but on average (2-3 out of 4 datasets) we can say that RBT will perform better! Oh, and by the way we never mentioned in the video explicitly that RBT and better AVL trees and we never made a comparison between them! Cheers!
@@geekific yup didn't mean to imply you stated Red-Black was better than AVL. Just thought I'd mention it since I wasn't sure myself before looking into it. Great video!
This series is the best explanation i found on youtube
OMG I love this video, you really have no idea how much! Everything was explained so clearly. Shame there is no deletion tutorial :D
Glad to read this :) Working on it!
Underrated ... Amazing explanation
One of the best explanation of Red black tree.
Thanks a lot! Glad it was helpful :)
this was really helpful ..lot of the videos just give the theory ..this goes through the code as well
Really glad it helped!
A really nice video to watch, even when I was tired and couldn't focus well I was able to still understand, I still recommend for whoever is studying trees or other data structures to go to Wikipedia and read about it, it's story and so on
Awesome! Glad I could be of help :)
I would really appreciate it if you did a video on the delete operation of the red black tree but other than that the video is pretty good and explains everything in detail
It is on my todo list :) Stay tuned and glad you liked the video!
Please make the video with delete operation
Are you from morroco?
Hi there, Can we have a video for deleting process of red-black tree? Thanks!
Will add it to my list of upcoming videos! Stay Tuned!
9:40 This is exclusively for a mutable tree where you need the parent pointer on the node. If you want to create an immutable persistent version then you can't have the parent two way binding as you would need to touch every node in the tree during a mutation which would ruin the time complexity.
Check out path copying for folks interested in an immutable persistent version!
Your video is awesome! Especially helpful for java beginners like me to understand these advanced data structures! Keep it up!!!
Glad it was helpful :)
Your videos are very useful and easy to understand, respect for your efforts! Regarding the current one, I have two questions, both concerning the handleLeftSituations and handleRightSituations.
- First about the recoloring by invoking the flipColor method. I tried to write it myself, as an exercise and in my understanding, the nodes, that change colors in left(right) heavy situations should be the GrandParent(GP) and the Parent(P), as it is in your example, but in left-right(right-left) situations the GrandParent(GP) and the Node(N) should be recolored.
- Second - the last row - invoking of recolorAndRotate method and the parameter we pass. Let's consider the handleLeftSituations case. I think it should be the other way around - passing GP as a parameter in case of left heavy situation and passing P in case of left-right situation.
I created the following trees:
1) Left Heavy Situation - We have Root(key 64) -> left child is our GP(key32) -> left child is our P(key 16) -> left child is the node we insert N(key 8). After the rotation(right rotation), we have the tree now as R(64) -> left child is P(16) -> left child is N(8) and P(16) -> right child is GP(32). So now if we pass our current P(16) in recolorAndRotate method, we will pass a node, that is already processed and I think we should pass N(8)'s newly assigned GP(64), our Root(64), which is now our P(16)'s newly assigned parent.
2) Left - Right Situation - We have R(64) -> right child is our GP(512) -> left child is our P(128) -> right child is the node we insert N(256). After the first rotation(left) we have R(64) -> right child GP(512) -> left child N(256) -> left child P(128) and after the second rotation we have R(64) - > right child N(256) -> left child P(128) and N(256) -> right child is GP(512). If we pass our current GP(512) we will pass a node that is already processed and I think we should pass our N(256)'s newly assigned P(64), which is our Root(64).
Perhaps I miss the moment when you reassign the Node and Parent variables to point to the otherone's address in memory, i.e. swapping those variables' values. Of course, I assume that I am completely wrong in my understanding, as I am new to this. Hopefully I managed to explain what I mean without pictures or drawings.
Apology for the long comment and I will be happy to read your answer, as I had hard time in attempts to understand if(where) I do the things wrong.
Hello! Thanks a lot, happy to help :) Yes, your explanation was really clear! The part of the implementation you addressed is actually explained from 5:10 to 8:45. The code written accurately reflects this part and in it we explain all rotation / recoloring cases. Additionally, the rotation cases are explained more in depth in the AVL video: ua-cam.com/video/Jj9Mit24CWk/v-deo.html if you want to take a look at it as well! Cheers :)
Hey, thank you for your Videos. i think the question made at 8:36 was not answered in the remaining video. Generally speaking, why do we have to check after rotating, since the node on top(old parent in heavy left, new inserted node in left-right) is recolored to black, and can not cause a red-red problem?
I found it super helpful!
Thanks a bunch fellow!
Just got a new subscriber.
Thanks for the support! Glad I could help :)
If I can ask you something, I'd like to see how deletion can be implemented in this type of tree. I've been struggling against it...
is there a vedio for the the deletion process ?
Working on it, Stay Tuned!
Can’t wait ❤
can you make a video of red black tree deletion process? please
Hi, I really like your implementation of red-blakc tree, please let me know if I can find the deletion))
i am doing a project in university, my topic is Red-balck tree implementation, deadline is dec 18th)
deletion would really help me :D
Testing this class, I can see after creating root, at the second insertion , into the recolorAndRotate method, grandParent will be null, so the creation of the uncle will raise a NullPointerException... I am wrong?
You can check the testing we did here: ua-cam.com/video/hmSFuM2Tglw/v-deo.html, hope this helps!
@@geekific it has helped, thanks :)
I think you give a really good introduction but i think i need to study it once again in order to grasp everything. You should actually write and mark the points that are important in the video, also the thing that you don't give enough emphasis on the words that are important.
Glad you liked it! Thanks, will keep that in mind for future videos :) Cheers!
By executing toString method on each node it get a lot of red red conflicts ! Is this algorithm correct?
At 9:52 we are excluding the parent variable from the toString() method to avoid infinite loops. Are you doing that?
@@geekific it was my mistake the final tree was perfect but man I have a big problem rn can you help me? I'm doing a report on trees performance on inserting and there is some configuration of the tree the implementation just cant handle and the exception is thrown "Cannot read field 'left' because 'this.parent' is null" or "cannot read parent.color because parent is null" out of 10000 elements it can only insert like 17 and boom NullPointerException parent is null do you have some idea what it might be? I have no time to implement another RB Tree and fixing it is really giving me a hard time
I just debugged it
the problem is in this line: recolorAndRotate(node.isLeftChild() ? parent : grandparent); he checks if node is a left child but node is the newly inserted node who rotated left and then right and became the root of the size 3 tree. He has no parent
if (node != this.root && parent.color == RED) in recolorAndRotate method this condition is also a problem bcs you dont check if parent != null
Looks easier than an avl tree , however been searching for javascript implementation.
If the concepts are clear, implementing it in any language is just a matter of time :)
god i had to turn on mono audio for your video my left ear is still ringing . xD
We fixed this in future videos, sorry about that!
What about traversal
Hey, at around 10:40 I mentioned that it was covered in previous videos as it is similar to the BST and AVL traversal. Feel free to check this video: ua-cam.com/video/zIX3zQP0khM/v-deo.html at around 6:27 for the explanation and 11:04 for the implementation. Cheers :)
And find method.
Can u upload red black tree python implementation pls
I was actually thinking about expanding the channel beyond Java! However, this will have to wait a bit. Sorry about that, and Stay Tuned!
I don't understand, might need to watch again :-(
Let me know how I can help!
out of curiosity, are you Lebanese?
yup :P
@@geekific Haha. We have such a unique dialect. Anyways, this was a great review for me of the Advanced data structures course. God bless Paul Atiyye.
Oh my God😵💫😵💫😵💫😵💫😵💫
Dear Sir, pls say me honestly, do your bear in mind right now all this mechanics and its java implementation??😮
My guess is that even most ppl from MAANG cannot show code for redblack tree from the top of their heads. It's educational to understand it but I doubt that the majority can show it at request. Looks like a star ability:) (extra ability). Am I right or wrong? 🤔
Yeah, it is not straightforward, like I can tell you all the mechanics and how they work, but I will not be able to come up with the perfect implementation from 1st try of course.
With real world data, Red-Black trees are not generally more performant than AVL trees. The conclusion of this study is worth a quick glance: benpfaff.org/papers/libavl.pdf
Hey, thanks for sharing it was a good read! Ripped straight from the document shared: "In two of our experiments red-black performance was better than AVL performance and in the other one it was the reverse; in one, splay trees were better than either". So, it all boils down to the data you are using, but on average (2-3 out of 4 datasets) we can say that RBT will perform better!
Oh, and by the way we never mentioned in the video explicitly that RBT and better AVL trees and we never made a comparison between them! Cheers!
@@geekific yup didn't mean to imply you stated Red-Black was better than AVL. Just thought I'd mention it since I wasn't sure myself before looking into it. Great video!
Yep I know! Thanks again for sharing and thanks for the feedback bro :)
private void handleLeftSituations(Node node, Node parent, Node grandParent) {
if (!node.isLeftChild()) {
rotateLeft(parent);
}
// parent is child now
parent.getParent().flipColor();
grandParent.flipColor();
rotateRight(grandParent);
if (node.getParent() != null) {
recolorAndRotate(node.isLeftChild() ? parent : grandParent);
}
}
private void handleRightSituations(Node node, Node parent, Node grandParent) {
if (node.isLeftChild()) {
rotateRight(parent);
}
parent.flipColor();
grandParent.flipColor();
rotateLeft(grandParent);
if (node.getParent() != null) {
recolorAndRotate(node.isLeftChild() ? grandParent : parent);
}
}
How is it?