|Hide textShow text Hide pseudo-codeShow pseudo-code|
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.
1 While the recursion returns, keep track of
2 If rotation is needed in p, do one of the following rotations: