Red-Black Binary Search Trees

Rules of Red-Black Binary Search Trees
Characteristics of Red Black Trees
Examples of working with Red Black Trees
Few more Examples of Insertions into Red Black Trees
MIT Lecture on AVL trees
Click here to suggest a better video
Click here to view videos suggested by visitors

A red-black tree is a type of binary search tree which tries to balance itself after every insertion and deletion of a node. A binary tree is said to be balanced when the heights of left subtree and right subtree differ by not more than 1. This ensures that the tree does not lean too much on either side so that data can be efficiently searched.

Each node in a Red-Black binary search tree stores an extra bit if information which indicates whether a node is of “red” color or “black” color. There are also a few constraints on how red and black nodes should be arranged. Every time a new node is inserted into the tree or a node is removed from the tree, a re-structuring is done in order to make the red-black tree to adhere to the below constraints:

  • Every node is either red or black
  • All NULL nodes are considered black
  • A red node should not have a red child
  • Every path from a given node to any of its descendant NULL nodes should go have the same number of black nodes

TODO: More info along with references.