Red Black Trees

Defintion of a red black tree

A red black tree is structure that adds on to the base Binary search tree data structure.
The main purpose of the additonal componenets of a red black tree is to allow the BST
to now be self balancing when inserting and deleting nodes.
This allows this structure to be more efficent in many of the common methods associated
with the BST data sturucture.

Red black tree rules:

  • All nodes in the tree are assigned a color of red or black
  • The root node must be black
  • All leaves that are null nodes are black
  • A red node cannont have a red child
  • every path from a node to a leaf must have the same amount of black nodes along it


    • Further Information