What is a Red-Black Tree?

This lesson is an introduction to Red-Black trees, their properties, and the total time they take to perform the operations of insertion, deletion and searching. We will also do a small comparison between AVL and Red-Black Trees.

We'll cover the following

Introduction #

Red-Black Trees are another type of self-balancing Binary Search Tree, but with some additions: the nodes in Red-Black Trees are colored either red or black. Colored nodes help with re-balancing the tree after insertions or deletions. We will go through the insertion and deletion functions of Red-Black trees just like we did with AVL Trees previously.

Properties of Red-Black Trees #

  • Every node is either Red or Black in color

  • The root is always colored Black

  • Two Red nodes cannot be adjacent, i.e., no red parent can have a red child and vice versa

  • Each path from the root to null contains the same number of Black colored nodes

  • The color of null nodes is considered Black

From the perspective of implementation, our node class will contain the addition of a Boolean variable that will store the information about the color of a node. Here is a basic structure of a Node which will be used to build a Red-Black tree.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.