# Red-Black tree with index

I want to create a Red-Black Tree, with 2 values, (index, value) and I want to insert into the RB_tree based on the index.

So if I have the function: $$\text{insert}(root, value, index)$$ it will insert the value at $$index$$. However, because I insert based on the other indexes, if I insert at the index $$1$$ let's say, and I have already inserted at that index, then I would have to add to all the other node's indexes $$+1$$. The insert function is used only with valid indexes so, $$index\in[0, size(RB\_tree)]$$. What should I do to keep the insertion $$O(\log n)$$ and still have the indexes?

• See the first part of the answer to this question. The answer is about AVL trees but the same approach should work for general Red-Black trees. When you want to insert an element with index $i$ you can first add $1$ to all the keys that are greater than or or equal to $i$ (by using the Shift$(i,1)$ operation), and then insert the element as usual. Commented Nov 13, 2019 at 15:48
• @Steven and the complexity for that, would be still $O(\log n)?$ Commented Nov 13, 2019 at 16:53
• @Steven and for that operation "push down", for the $v$ node would mean do the same thing but for the $v$ node, and the meaning of "left operation are symmetric" means that I should also do $push\_down$ but in the left rotation, right? Commented Nov 13, 2019 at 17:09
• Yes, all the complexities would still be $O(\log n)$ in the worst case, including that of the Shift operation. Yes, "push down" for $v$, means to do exact same thing that you did for node $u$ but for $v$ (add $x_v$ to the offsets of $v$'s children and to $v$'s key, then $x_v$ to $0$). Left rotations are symmetric means that you just swap the role of $v$ (that in the right rotation was $u$'s left child) to be the right child of $u$. Then, you proceed similarly: "push down" the offset on $u$, "push down" the offset on $v$ (so that $x_u = x_v = 0$), and perform the left rotation as usual. Commented Nov 13, 2019 at 18:57
• @Steven and one more thing, when do I actually increment that field $x_v$ that will cumulate in search and insert? Commented Nov 13, 2019 at 18:59