Any binary search tree must contain following properties to be called as a red-black tree.
1. Each node of a tree should be either red or black.
2. The root node is always black.
3. If a node is red, then its children should be black.
4. For every node, all the paths from a node to its leaves contain the same number of black nodes.
We describe the number of black nodes over any path from but not including a node x down to a leaf, the black height of the node is denoted by bh (x).
Red-black trees contain two main operations, namely INSERT and DELETE. When the tree is modified, the result might violate red-black properties. To restore the tree properties, we must change the color of the nodes as well as the pointer structure. We can change the pointer structure by using a technique called rotation which preserves inorder key ordering. There are two types of rotations: left rotation and right rotation.
When we do a left rotation on a node y, we suppose that its right child x is non null. The left rotation makes x as the new root of the subtree with y as x's left child and x's left child as y's right child.
Alike procedure is repeated vice versa for the right rotation.