E
E
Evgeny Trofimov2016-06-13 14:44:59
Programming
Evgeny Trofimov, 2016-06-13 14:44:59

What exactly is the algorithm for inserting an element into a red-black tree?

I'm trying to figure out how to add an element to a red-black tree.
Here's the video, where everything is shown step by step - https://www.youtube.com/watch?v=PhY56LpCtP4
But I don't quite understand some of the actions that are performed there...
I.e. an algorithm like this ( I took it from here )
1) If the father of the new element is red and his uncle is red, we repaint the father and uncle black, and the grandfather red. If the grandfather is a root, then we leave it black.
2) If the father of the new element is red and his uncle is black, we perform a rotation. (and for some reason we also perform repainting if the root turns black, but nothing is written about this)
Untitled-2.png
Well, i.e. here, for example, if you perform a right turn around A - A will become a red root. And what to do in this case? Repaint the whole tree? Those. in this case, A and B were repainted ...
Then, on the video - the same questions.
For example, here, when we got a red root as a result of a left turn.
fe92431db02f476d8bffc42457662963.png
Or here, where after adding 5, you need to make a left turn around 3, resulting in a red child of the red dad. (red 4 - father, red 5 - son)
9d713991311e4311a8bdbc7099842da9.png
I.e. I do not quite understand what needs to be done in such a situation, tk. the violation occurred after the rotation, not when a new element was added. And what should be done? For 5, for example, the father is red, and the uncle is black, which means it seems like you need to perform a turn, but in the video 4 and 3 are simply repainted ..

Answer the question

In order to leave comments, you need to log in

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question