# Red-Black Trees introduction

Last Updated on

Table of Contents

[hide]

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 coloured 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 colour of the root node is always black
- all leaf node or terminal or null nodes are black
- every red node has both children coloured in black
- in every simple path from a given node to its leaf node has an equal no of black nodes