Deletion algorithm for a Red Black tree

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开发者_StackOverflow中文版)

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?

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)

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".

You can refer to following code.

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