# Red-black tree

### # What is red-black tree?

Red-black tree is a type of self-balancing binary search tree, a data structure used to implement ordered sets and maps.
It is called red-black tree because each node in the tree is either red or black.
The basic idea behind the red-black tree is to maintain a balance between the left and right subtrees of each node, so that, the tree remains **roughly** balanced, even as elements are added or removed.
The following are the main properties of Red-Black Tree:

- Every node has a color, either red or black.
- The root of the tree is always black.
- There are no two adjacent red nodes (A red node cannot have a red parent or red child)
- Every path from a node (including leaf) to a null node has a same number of black nodes.

The height of a red-black tree is guaranteed to be **O(log n)**, where n is the number of elements in the tree. This makes the basic operations of insertion, deletion and search all run in **O(log n)** time

### # Compare to AVL tree

AVL Tree is strictly self-balanced tree, it makes searching operation always cost O(log n) time. When Red-black tree, in the worst case it could be O(n) (left skewed or right skewed tree).

### # Insertion

Tutorial

Apply the following rules when inserting elements to a Red-black tree

- If the tree is empty, create a new node as root node with
**back**color. - If the node is not empty, then create a new node as leaf node with
**red**color- check the color of new node’s parent
- If it’s
**black**color, then stop. - If it’s
**red**, then check the color of parent’s sibling- If it’s
**black**or null, then do suitable rotation and recolor. - If it’s
**red**then, recolor (both parent and parent sibling) and also check if parent’s parent of new node is**NOT**the root node, then recolor it and recheck.

- If it’s

- If it’s

- check the color of new node’s parent