Red-Black Trees introduction
The red-black tree is a self-balancing binary search tree invented in 1972 by Renault Bayer, who called it an asymmetric binary tree. although a red-black tree is complex it has a good worst-case running time for its operation running and deletion which can be done in o(log n) time where n is equal to no of nodes
A red-black tree is a Binary search tree in which every node os colored with either Red or black It is a type of self-balancing BST
Structure of Red Black trees
struct redblacknode
{
enum {red,black}color;
int data;
struct redblacknode *left;
strcut redblacknode *right;
}
Properties of red-black tree
A Red-black tree is a BST in which every node has a color either red or black
the red-black tree has following properties
- Every node of a red-black tree is either red or black
- the color of the root node is always black
- all leaf node or terminal or null nodes are black
- every red node has both children colored in black
- in every simple path from a given node to its leaf node has an equal no of black nodes
