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 lenght of longest path between left and right subtrees under any node is less than 1. Each node in a Red-Black binary search tree stores an extra bit if information which indicated 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 restructing 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.