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