1
$\begingroup$

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?

Improve this question
$\endgroup$
11
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Commented Nov 13, 2019 at 15:48
  • $\begingroup$ @Steven and the complexity for that, would be still $O(\log n)?$ $\endgroup$
    – C. Cristi
    Commented Nov 13, 2019 at 16:53
  • $\begingroup$ @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? $\endgroup$
    – C. Cristi
    Commented Nov 13, 2019 at 17:09
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Commented Nov 13, 2019 at 18:57
  • $\begingroup$ @Steven and one more thing, when do I actually increment that field $x_v$ that will cumulate in search and insert? $\endgroup$
    – C. Cristi
    Commented Nov 13, 2019 at 18:59

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.