Question, why do we rename the z, y, x nodes to abc? Why relabel when we can just work with z, y, x, or if you really like your abc then why not label them abc in the first place?
Nice video! But I think there is one case missed: when x is the right child of y and y is the left child of z, we need to first rotate the x-y link then follow the operations of CASE1.
Pseudo Code Insert(x) add(x) rebalanceInsert(x) if x is the root: make x black # depth decreases by 1 else: make x red y = parent of x, z = grandparent of x if y is red: s = sibling of y # recoloring is needed if s is black: # Case 1 a, b, c = restructure(x) # i think this means that zyx now = abc make b black make a red ake c red else: # Case 2 make y black make s black make z red rebalanceInsert(z)
Yes, that is the essence. The colors are encoded as bits during implementation. However, explaining all of this with 0s and 1s is a bit cumbersome. Good remark! :)
Thanks for the video, but in all the video you mentioned S to be black as an external node, however it wasn't an external node and in this case we will be breaking the black depth property, so then 'a' needs to be colored black. Hope you reply soon, I have an exam on Wednesday xD.
Sorry it is insufficient. In the case of a new node inserted that is red, if the parent is red and grandfather of course black and uncle is black (case 1 at 4:58): It further depends if x is on the outside of the tree or the inside, (*) If on the inside, an additional rotation in the direction of the outside takes place on node y. Now x is parent node. Then the final rotation takes place about z away from newly inserted node. But step (*) is critical and you have not talked about it, Insert always has a possible maximum of 2 rotations to fixup (sometimes 1 rotation, sometimes up to log (N) /2 * 3 recolorations. Delete always has a possible maximum of 3 rotations to fixup.
By design, fortunately, executing the steps of case 2 neither violates the depth property. Initially, the left and right subtree of x, the right subtree of y, and the right subtree of z do not violate any properties. After the execution of the steps, notice that the left and right subtree of x become the left and right subtree of a, respectively. Moreover, the right subtree of y becomes the left subtree of c. Finally, the right subtree of z becomes the right subtree of c. We have not increased the black depth for any of these subtrees (or nodes a, b and c) during these steps. Therefore, we are not violating the depth property. Good question! :)
Yes, if z is the root in case 2, we eventually color it black. "Repeat recoloring for z" means that we indeed repeat the algorithm. Looking at the pseudocode, this corresponds to the recusive call "rebalanceInsert(z)" at 11:42. Assuming that z is the root, it is colored black by the call "makeBlack(x)" at 11:02. Good question! :)
Doesn't he add a non existant child in each insert such as at 8:11 where the inserted 23 should have one single child? 29 has two children. One stays with 29 as 23's sibling, the other become's 23's child so why does 23 end up having _two_ children? Where'd that third node come from? Assuming this doesn't happen, would this imbalance the tree?
The additional external node is added to prevent the external property from being violated. The external nodes can be regarded as dummy nodes to prevent any external property violations. It is common practice to maintain these dummy nodes during Red-Black Tree operations. In order to prevent any confusion, I should have mentioned that too in the video. Regarding your second question, Red-Black Tree property violations eventually always result in an imbalanced tree. Thank you for your question! :)
Just watched the first red-black tree video, after 3 years the second part comes out
this was so helpful!! i might actually pass my exam now...
Question, why do we rename the z, y, x nodes to abc? Why relabel when we can just work with z, y, x, or if you really like your abc then why not label them abc in the first place?
Nice video! But I think there is one case missed:
when x is the right child of y and y is the left child of z, we need to first rotate the x-y link then follow the operations of CASE1.
Thanks for the explanation, it filled in some gaps and helped me understand it 👍
Pseudo Code
Insert(x)
add(x)
rebalanceInsert(x)
if x is the root:
make x black # depth decreases by 1
else:
make x red
y = parent of x, z = grandparent of x
if y is red:
s = sibling of y # recoloring is needed
if s is black: # Case 1
a, b, c = restructure(x) # i think this means that zyx now = abc
make b black
make a red
ake c red
else: # Case 2
make y black
make s black
make z red
rebalanceInsert(z)
So the point is that it just rebalances itself according to some rules, and colors there are just to make understanding of rules a bit simpler.
Yes, that is the essence. The colors are encoded as bits during implementation. However, explaining all of this with 0s and 1s is a bit cumbersome. Good remark! :)
Thanks for the video, but in all the video you mentioned S to be black as an external node, however it wasn't an external node and in this case we will be breaking the black depth property, so then 'a' needs to be colored black. Hope you reply soon, I have an exam on Wednesday xD.
thank you bro
good explanation, thanks!
thank you!
Case 1: s is black right rotate around z and interchange colour of z and y
Really a good video
when we inserted 23 how 29 become black and 31 red ?
nice video really helped
Bigup bro tnx
Sorry it is insufficient.
In the case of a new node inserted that is red, if the parent is red and grandfather of course black and uncle is black (case 1 at 4:58):
It further depends if x is on the outside of the tree or the inside,
(*) If on the inside, an additional rotation in the direction of the outside takes place on node y. Now x is parent node.
Then the final rotation takes place about z away from newly inserted node.
But step (*) is critical and you have not talked about it,
Insert always has a possible maximum of 2 rotations to fixup (sometimes 1 rotation, sometimes up to log (N) /2 * 3 recolorations.
Delete always has a possible maximum of 3 rotations to fixup.
when we inserted 5, why does it have two children? it replaced one child of 7, so it should have only one child??
That's the rule - leafs must be empty nodes, so you add to nils to 5
When we insert an element, we normally insert like BST. then we arrange based on reb black tree properties
@@tyapka this one will be disliked by me since it may be not a good answer for this ques
At 5:40, (s is black), then we're not introducing double red. But wouldn't it violates the black depth? How can we remedy that?
By design, fortunately, executing the steps of case 2 neither violates the depth property.
Initially, the left and right subtree of x, the right subtree of y, and the right subtree of z do not violate any properties. After the execution of the steps, notice that the left and right subtree of x become the left and right subtree of a, respectively. Moreover, the right subtree of y becomes the left subtree of c. Finally, the right subtree of z becomes the right subtree of c. We have not increased the black depth for any of these subtrees (or nodes a, b and c) during these steps. Therefore, we are not violating the depth property.
Good question! :)
6:26 if z is root, what does it mean by repeating the algorithm? simply color z to black again?
Yes, if z is the root in case 2, we eventually color it black.
"Repeat recoloring for z" means that we indeed repeat the algorithm. Looking at the pseudocode, this corresponds to the recusive call "rebalanceInsert(z)" at 11:42. Assuming that z is the root, it is colored black by the call "makeBlack(x)" at 11:02.
Good question! :)
why could you not insert the "23" at the right of 7?
Doesn't he add a non existant child in each insert such as at 8:11 where the inserted 23 should have one single child? 29 has two children. One stays with 29 as 23's sibling, the other become's 23's child so why does 23 end up having _two_ children? Where'd that third node come from? Assuming this doesn't happen, would this imbalance the tree?
The additional external node is added to prevent the external property from being violated. The external nodes can be regarded as dummy nodes to prevent any external property violations. It is common practice to maintain these dummy nodes during Red-Black Tree operations. In order to prevent any confusion, I should have mentioned that too in the video. Regarding your second question, Red-Black Tree property violations eventually always result in an imbalanced tree.
Thank you for your question! :)
thank you!