What is a RedBlack Tree?
This lesson is an introduction to RedBlack 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 RedBlack Trees.
We'll cover the following
Introduction #
RedBlack Trees are another type of selfbalancing Binary Search Tree, but with some additions: the nodes in RedBlack Trees are colored either red or black. Colored nodes help with rebalancing the tree after insertions or deletions. We will go through the insertion and deletion functions of RedBlack trees just like we did with AVL Trees previously.
Properties of RedBlack 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 RedBlack tree.
Level up your interview prep. Join Educative to access 70+ handson prep courses.