TRAKLA2

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:

1. if (p.left == t) and (p.left.left == u), single rotation right in p;
2. if (p.right == t) and (p.right.right == u), single rotation left in p;
3. if (p.left == t) and (p.left.right == u), LR-double rotation in p; or
4. if (p.right == t) and (p.right.left == u), RL-double rotation in p.