What is a Red-Black Tree?

An introduction to “red-black” trees, their properties, and the total time they take to perform the operations of insertion, deletion, and searching. Learn how AVL differs from red-black trees.

We'll cover the following

Introduction

Red-black trees are another type of self-balancing binary search tree with some additions; the nodes in red-black trees are colored either red or black. Colored nodes help with rebalancing the tree after insertions or deletions. You will go through the insertion and deletion functions of red-black trees just like you 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., a red parent cannot have a red child and vice versa.

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

  • The color of NULL nodes is considered Black.

From the perspective of implementation, your 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.