In computer science, a red–black tree is a kind of Selfbalancing binary search tree. Each Vertex stores an extra bit representing “color” (“red” or “black”), used to ensure that the Tree remains balanced during insertions and deletions.
When the tree is modified, the new tree is rearranged [Tree rotation] and “repainted” to restore the coloring properties that constrain how unbalanced the tree can become in the worst case. The properties are designed such that this rearranging and recoloring can be performed efficiently.
Properties
 Every node is either red or black
 All
NIL
nodes are considered black A red node does not have a red child
 Every path from a given node to any of its descendant
NIL
nodes goes through the same number of black nodes
Space Complexity
\(\bigo{n}\)
Time Complexity
Function  Amortized  Worse case 

Search  \(\bigo{\log n}\)  \(\bigo{\log n}\) 
Insert  \(\bigo{1}\)  \(\bigo{\log n}\) 
Delete  \(\bigo{1}\)  \(\bigo{\log n}\) 
Algorithm
Insertion
Insertion begins by placing the new (non
NIL
) node, sayN
, at the position in the binary search tree of aNIL
node whose inorder predecessor’s key compares less than the new node’s key, which in turn compares less than the key of its inorder successor. (Frequently, this positioning is the result of a search within the tree immediately preceding the insert operation and consists of a node P together with a direction dir withP>child[dir] == NIL
.) The newly inserted node is temporarily colored red so that all paths contain the same number of black nodes as before.
Insertion may invalidate one or more Properties of the Redblack tree.
Cases

1: Parent is black
All Properties hold. No further work is necessary.

2: Parent and uncle are both red
The third Properties
Implementation
class red_black_tree():
def insert(key, value):
inserted_node = binary_tree_insert(key, value)
insert_fix(inserted_node)
def binary_tree_insert(value):
pass
def insert_fix(inserted_node):
pass