Insertion for Red-Black Trees ( incl. Examples ) - Data Structures

Подписаться 4,1 тыс.

Просмотров 57 тыс.

50% 1

Previous video on recognizing Red-Black Trees: • Red-Black Trees - Data...
Deletion for Red-Black Trees: • Deletion for Red-Black...
Thanks for subscribing!
---
This video is about the insertion operation for the Red-Black Tree, a self-balancing binary search tree.
In the video the following concepts are explained:
- How insertion for Red-Black Trees works (including examples for each case);
- An intermediate exercise (for each case an exercise);
- Pseudocode for the insertion operation;
- The performance of the insertion operation for Red-Black Trees.
---
If you thought this video was useful, make sure to give it a like!
If you have any questions, use the comment section.
If you want to see more videos like this one, make sure to subscribe.
This video has been published by MisterCode.

Опубликовано:

29 сен 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 33

@moisesacero4995 4 года назад

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?

@Momo-bb2fn 4 года назад

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)

@charlesstrickland8839 5 лет назад

Just watched the first red-black tree video, after 3 years the second part comes out

@stephenhowe4107 6 месяцев назад

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.

@muyuan5935 5 лет назад

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.

@Buom_01 2 года назад

I confirm it

@Crossathletik Год назад

true

@thando6109 Год назад

this was so helpful!! i might actually pass my exam now...

@tyapka 4 года назад

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.

@MisterCode 3 года назад

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! :)

@varadthokal1406 4 года назад

when we inserted 5, why does it have two children? it replaced one child of 7, so it should have only one child??

@tyapka 4 года назад

That's the rule - leafs must be empty nodes, so you add to nils to 5

@rasathuraisivaram8301 3 года назад

When we insert an element, we normally insert like BST. then we arrange based on reb black tree properties

@rasathuraisivaram8301 3 года назад

@@tyapka this one will be disliked by me since it may be not a good answer for this ques

@jihadshaito9116 3 года назад

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.

@alaafathy5361 3 года назад

when we inserted 23 how 29 become black and 31 red ?

@DrCaesarsPalace_MD Год назад

Thanks for the explanation, it filled in some gaps and helped me understand it 👍

@jordanbecker7006 Год назад

thank you bro

@soufianebaeloul3382 3 года назад

Bigup bro tnx

@olenaqwerty7895 3 года назад

good explanation, thanks!

@Jaykumar-po4wq 2 года назад

Case 1: s is black right rotate around z and interchange colour of z and y

@jordyfra 4 года назад

thank you!

@ioanadobos2840 4 года назад

thank you!

@ShivamYadav-rx3hy 5 лет назад

nice video really helped

@parasite6731 5 лет назад

Really a good video

@second_second_ 3 года назад

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?

@MisterCode 3 года назад

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! :)

@second_second_ 3 года назад

6:26 if z is root, what does it mean by repeating the algorithm? simply color z to black again?

@MisterCode 3 года назад

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! :)

@herrschultz7413 4 года назад

why could you not insert the "23" at the right of 7?

@rx_lang 4 года назад

Because 23 is bigger than 10 (the root), so 23 has to go to the right of 10.

@Momo-bb2fn 4 года назад

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?

@MisterCode 3 года назад

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! :)