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

1. Every node of a red-black tree is either red or black
2. the color of the root node is always black
3. all leaf node or terminal or null nodes are black
4. every red node has both children colored in black
5. in every simple path from a given node to its leaf node has an equal no of black nodes