Reputation: 123
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