Red Black Tree

Introduction

A red-black tree is a BST with two node types, namely red and black, and supporting operations that ensure the tree is balanced when a node is inserted or removed.

A tree with N nodes will have a height of O(log N).

Basic rules

• Every node is colored either red or black.
• The root node is black.
• A red node's children cannot be red.
• A null child is considered to be a black leaf node.
• All paths from a node to any null leaf descendant node must have the same number of black nodes.

Red Black Tree graph

To learn about Red Black Tree.Link