## Red Black Tree

 Hide textShow text Hide pseudo-codeShow 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. 1 While the recursion returns, keep track of node p, p's child t and p's grandchild u within the path from inserted node to p. 2 If rotation is needed in p, do one of the following rotations: if (`p.left == t`) and (`p.left.left == u`), single rotation right in p; if (`p.right == t`) and (`p.right.right == u`), single rotation left in p; if (`p.left == t`) and (`p.left.right == u`), LR-double rotation in p; or if (`p.right == t`) and (`p.right.left == u`), RL-double rotation in p.