# 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