ninjarubberband
ninjarubberband

Reputation: 123

Adding a .size attribute to nodes in Red-Black Binary tree (Pseudo code)

In my CS class I've been given the task to add a size attribute to nodes in a Red-Black Binary tree. The size of a node, is the number of nodes in its sub trees. This attribute has to be updated, when changes is made to the RB tree, more specifically in the left-rotate algorithm, Insert algorithm, and Insert fix up algorithm. These 3 algorithms are taken from CLRS, and are pseudo code.

I first modified the left-rotate algorithm to update the size of modified nodes. T is the tree, x is the node to rotate.
LEFT-ROTATE(T,x)

y = x.right
x.right = y.left
if y.left != T.nil:
    y.left.p = x
y.p = x.p
if x.p == T.nil
    T.root = y
else if x == x.p.left
    x.p.left = y
else 
    x.p.right = y
y.left = x
x.p = y

x.size = x.left.size + x.right.size 
y.size = y.left.size + y.right.size 

I added the last two lines myself, which updates the size.

Next up is Insert, where T is the tree and z is the node to be inserted: RB-INSERT(T,z)

y = T.nil
x = T.root
while x != T.nil
    y = x
    if z.key < x.key
        x = x.left
    else 
        x = x.right
    y.size++
z.p = y 
if y == T.nil
    T.root = z
else if z.key > y.key
    y.left = z
else y.right = z
z.left = T.nil
z.right = T.nil
z.color = RED
RB-INSERT-FIXUP(T,z)

Pretty easy fix, I just inserted y.size++ in the end of the while loop, as each time we go further down the tree, we update the parents size.

Now here comes my current problem, updating size in the RB-INSERT-FIXUP algorithm. I haven't added any code yet, but here is the algorithm to modify:

RB-INSERT-FIXUP(T,z)
while z.p.color == RED
    if z.p == z.p.p.left
        y = z.p.p.right
        if y.color = RED
            z.p.color = BLACK
            y.color = BLACK
            z.p.p.color = RED
            z = z.p.p
        else if z == z.p.right
            z = z.p
            LEFT-ROTATE(T,z)
        z.p.color = BLACK
        z.p.p.color = RED
        RIGHT-ROTATE(T,z.p.p)
    else(Same as then clase with "right and "left" exchanged)
T.root.color = BLACK

Assume in INSERT-FIXUP that LEFT-ROTATE and RIGHT-ROTATE also updates the sizes in their own algorithms.

So I have to update the size of relevant nodes that get moved around in INSERT-FIXUP. I'm not sure how to do it. From what I gather, it shouldn't even be necessary to update the sizes in FIXUP, since its calls to Left and right rotate, already updates the sizes. Am I right about that, or am I missing anything? It sounds logical to me, but the task tells me to modify it such that the size field is updated, so its pretty confusing if not modifying it, is the answer.

Upvotes: 0

Views: 422

Answers (0)

Related Questions