Thursday, October 20, 2005

Red-Black Trees

I found an interesting website for object oriented programming and other computer science concepts. I added OOPWEB.com in the links section also.

Cormen, p269 has the pseudocode for inserting a node in the Red-Black Tree. The else part in the pseudocode has been left out. I have made an attempt to write the else part as follows:

If p[x] = right[p[p[x]]]
Then y <- left[p[p[x]]]
If color[y] = RED
Then color[p[x]] <- BLACK
Color[y] <- BLACK
Color[p[p[x]]] <- RED
X <- p[p[x]]
Else if x = left[p[x]]
Then x<- p[x]
RIGHT-ROTATE(T,x)
Color[p[x]] <- BLACK
Color[p[p[x]] <- RED
LEFT-ROTATE(T, p[p[x]])


No comments: