## Introduction

A red-black tree is a binary search tree with one extra attribute for each node: the colour, which is either red or black. We also need to keep track of the parent of each node, so that a red-black tree’s node structure would be:

enum Colour{ red, black }; class RB_Node { Colour clr; int val; RB_Node left; RB_Node right; RB_Node parent; }

A red-black tree is a type of self-balancing binary search tree. However, a red-black tree is a structure that has to adhere to a very strict set of rules in order to make sure that it stays balanced. A red-black tree is a binary search tree which has the following properties:

- The root is black.
- Every node is either red or black.
- Every leaf (NULL) is black.
- If a node is red, then both its children are black.
- Every simple path from a node to a descendant leaf contains the same number of black nodes. Number of black nodes on any simple path from, but not including, a node x down to a leaf is called Black-height of the node.

Number of black nodes on any simple path from, but not including, a node x down to a leaf is called **Black-height** of the node. By property 5, the notion of black-height is well defined, since all descending simple paths from the node have the same number of black nodes.

Implementations of the red-black tree algorithms will usually include the sentinel nodes as a convenient means of flagging that you have reached a leaf node.

As with the binary search tree, we will want to be able to perform the following operations on red-black trees:

- insert a key value (insert)
- determine whether a key value is in the tree (lookup)
- remove key value from the tree (delete)
- print all of the key values in sorted order (print)

A red-black tree is binary search tree. Operations that don’t change the structure of a tree won’t affect whether the tree satisfies the red-black tree properties. So the lookup and print operations are identical to lookup and print for binary search trees. A red-black tree with n internal nodes has height at most 2lg (n + 1). So below operations will have time complexity of O(lgn)

- Search for Node
- Find minimum or maximum
- Find successor or predecessor

## Node Insertion

The goal of the insert operation is to insert key **K** into tree T, maintaining T’s red-black tree properties. A special case is required for an empty tree. If T is empty, replace it with a single black node containing K. This ensures that the root property is satisfied. If T is a non-empty tree, then we do the following:

- Use the BST insert algorithm to add K to the tree
- Color the node containing K red
- Restore red-black tree properties (if necessary). To restore red-black tree properties use coloring and/or rotation if necessary.

Recall that the BST insert algorithm always adds a leaf node. Because we are dealing with a non-empty red-black tree, adding a leaf node will not affect T’s satisfaction of the root property. Moreover, adding a red leaf node will not affect T’s satisfaction of the black property. However, adding a red leaf node may affect T’s satisfaction of the red property, so we will need to check if that is the case and, if so, fix it (step 3). Property 1 is violated if **K** is the root, and property 4 is violated if K’s parent is red. In fixing a red property violation, we will need to make sure that we don’t end up with a tree that violates the root or black properties.

For step 3 for inserting into a non-empty tree, what we need to do will depend on the color of K’s parent. Let P be K’s parent. We need to consider two cases:

- Case 1: K’s parent P is black

If K’s parent P is black, then the addition of K did not result in the red property being violated, so there’s nothing more to do.

Reference

- https://pages.cs.wisc.edu/~cs400/readings/Red-Black-Trees
- https://medium.com/basecs/painting-nodes-black-with-red-black-trees-60eacb2be9a5