Deletion algorithm for a Red Black tree

Question

Guys I'm trying to implement deletion algorithm for a Red Black tree and I'm having problem with understanding line three of this algorithm (from a book "Introduction to Algorithms" second edition):

1 if left[z] = nil[T] or right[z] = nil[T]
2 then y ← z
3 else y ← TREE-SUCCESSOR(z)
4 if left[y] ≠ nil[T]
5 then x ← left[y]
6 else x ← right[y]
7 p[x] ← p[y]
8 if p[y] = nil[T]
9 then root[T] ← x
10 else if y = left[p[y]]
11 then left[p[y]] ← x
12 else right[p[y]] ← x
13 if y 3≠ z
14 then key[z] ← key[y]
15 copy y's satellite data into z
16 if color[y] = BLACK
17 then RB-DELETE-FIXUP(T, x)
18 return y

First of all there is nowhere in this book explained what the TREE-SUCCESSOR is suppose to look like (no algorithm for that) but I found this page: and if I feed this algorithm whit 11,2,1,7,5,8,14,15,4 and then try to delete 7 it finds predecessor but if I try to delete 11 it finds successor. And that what I can't understand. Why sometimes it takes predecessor and sometimes successor? What criteria are taken into consideration while making this decision? A node's color?
Thank you.

P.S. I also do not quite understand what it's written in line number 13. Does it mean that if y has three colors (neither black nor red) or something else?

Answer 1

tree successor (as the opposite of tree-predecessor [which is in that book i believe]) is generally defined for binary search trees as the node with the next highest key. How it determines it is dependent on the type (red-black in this case) and Im almost positive your book leaves the successor method as an exercise. (i remember the problem :P)

Answer 2

I think you're reading CLRS 2nd edition.

TREE-SUCCESSOR is introduced in Chapter 12 section 2 - "12.2 Querying binary search tree". And contrary to what Jesse Naugher says, it's not dependent on the type of binary search trees.

Line 13 you quoted is a typo. It should be "if y != z".

Answer 3

You can refer to following code.

http://code.google.com/p/cstl/source/browse/src/c_rb.c