Red Black Tree

Hide text Hide pseudo-code

Insert the given keys into the initially empty red black tree. If there are equal keys they are always inserted into the right branch of the existing node.

1. Search (top-down) and insert the new item u as in Binary Search Tree.

2. Return (bottom-up) and

2.1 If u is root, make it black and the algorithm ends or

2.2 if its parent t is black, the algorithm ends

2.3 If both u and its parent t are red, do one of the following:

2.3.1. [change colors] If t and its sibling v are red, change colors. Change t and v black and their parent p red. Continue the algorithm in p if necessary.

2.3.2. [rotations] If t is red and v black, do one of the rotations similar to that in AVL-tree. In addition, p and its new parent exchange their colors, however, this is done automatically here. After rotation, there will be no more two consequtive red nodes.

  Created Fri Oct 30 13:52:51 EET 2009 - Powered by SVG-hut