Red Black Trees

Introduction

Red Black Trees are a type of balanced binary search tree that use a set of rules to maintain balance, ensuring logarithmic time complexity for operations like insertion, deletion, and searching, regardless of the initial shape of the tree. Nodes are colored either red or black, and rules are made accordingly.

Requirements for a valid red black tree

• Each node is either red or black
• The root node is black
• No red nodes have red children
• Black height of tree is consistent across the tree

Diagram

More Information