What is a Red-Black Tree?

This lesson is an introduction to Red-Black trees, their properties, and the total time it takes to perform the operations of insertion, deletion, and searching.

We'll cover the following

Introduction

A Red-Black Tree is another type of self-balancing Binary Search Tree, just like the AVL Trees , but with some additions. The nodes in a Red-Black Tree are colored to either red or black. Colored nodes help in re-balancing the tree after insertion or deletion. There are also some cases used to balance the Red-Black Trees. We will also go through the insertion and deletion operations of the Red-Black Tree.

Properties of Red-Black Trees

  • Every node has either Red or Black 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.

  • Every path from the root to a leaf must contain the exact same number of black-colored nodes.

  • Every null node is considered to be black in color.

From the perspective of implementation, our node class will contain a boolean variable in addition that will store the information about the color of a node.

Given below is the basic structure of a Node which will be used to build a Red-Black Tree.

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