Introduction to Red Black Tree

Estimated Time

1 hour

Introduction to Red Black Tree

Video introduction to Red Black Tree experiment should be displayed here..!

Prerequisites of the Experiment

Overview of the Experiment

The experiment features a series of modules with video lectures, hands-on practice exercises and quizzes to self analyze.

Learning Objectives of the Experiment

In this experiment, you will be able to do the following:

  • Structure, representation and Implementation of Red Black Tree.
  • Red Black Tree Properties.
  • Insert, Search and Delete operations on Red Black Tree, their algorithms, time and space complexity analysis.
  • Advantages of Red Black Tree over other self-balancing trees.

Pre-test of the Experiment

Estimated Time

10 minutes

Instructions for Pre-test

Pretest includes questions on basics of binary trees and balanced binary trees. All questions are single option correct.

Pre Test Quiz of the Experiment

Q1. What is an AVL tree?

(A) A tree which is unbalanced and is a height balanced tree.

(B) A tree with three children.

(C) A tree with atmost 3 children.

(D) A tree which is balanced and is a height balanced tree.

It is a self balancing tree with height difference atmost 1..

Q2. What is the maximum difference in heights between the leafs of a AVL tree is possible?

(A) log(n) where n is the number of nodes

(B) atmost 1

(C) 0 or 1

(D) n where n is the number of nodes

At every level we can form a tree with difference in height between subtrees to be atmost 1 and so there can be log(n) such levels since height of AVL tree is log(n).

Q3. What is the maximum height of an AVL tree with p nodes?

(A) p

(B) log(p)

(C) p/2

(D) log(p)/2

In all traversals mentioned in the question, left subtee is traversed before the right subtree.

Q4. Why do we need a binary tree which is height balanced?

(A) To avoid formation of skew trees

(B) To save memory

(C) To simplify storing

(D) To attain faster memory access

In real world dealing with random values is often not possible, the probability that u are dealing with non random values(like sequential) leads to mostly skew trees, which leads to worst case. hence we make height balance by rotations.

Basics of Red Black Tree

Estimated Time

15 minutes

Introduction to Red Black Trees

Welcome to this module on Red black Tree! Take a look at what you will go through the module.

  • What is Red Black Tree?
  • Representation of Red Black Tree
  • A quiz to check your understanding of structure of Red Black Tree

Basics

Welcome to Red Black Tree Experiment!

Video introduction to Red Black Tree experiment should be displayed here..!

What is Red Black Tree?

A Red-Black Tree is a binary search tree with one extra attribute for each node: the colour, which is either red or black. We also need to keep track of the parent of each node.

Basics of Red Black Tree

basics of Tree traversal video should be displayed here

Pictorial Representation of a Red Black Tree

Pictorial Representation of Basic RBT

Structure and Properties

Structure of Red Black Tree

Each node contains the following fields:
  • key
  • left – pointer to the root of left subtree.
  • right – pointer to the root of right subtree.
  • parent – pointer to the parent node.
  • color- color of the node, either RED or BLACK

Properties of Red Black Tree

  • Each node is either red or black.
  • The root of the tree is always black.
  • All leaves are null (Depicted as NIL in diagrams) and they are black.
  • If a node is red, then its parent is black.
  • Any path from a given node to any of its descendant leaves contains the same amount of black nodes. This is sometimes known as the black-depth.

Why do we impose such properties ?

  • Binary Search Tree in worst can can have a complexity of O(n) in insert and delete. The Red-Black trees guarantee a O(log(n)) in insert, delete (even in worst case).
  • They are balanced search trees and therefore balance themselves to always maintain a height of log(n),due to such restrictions.

Pictorial Representation of properties of a Red Black Tree

Pictorial Representation of properties of Basic RBT

Post Test Quiz of the Experiment

Q1. What is the special property of Red-Black trees and what should be the root always be?

(A) A pointer to next node.

(B) A color which is either green or black.

(C) A color which is either red or black and root should always be black color only.

(D) The height of the tree.

An extra attribute which is a color red or black is used. root is black because if it is red then one of red-black tree property which states that number of black nodes from root to null nodes must be same, will be violated.

Q2. When to prefer Red-black trees over AVL trees?

(A) When log(nodes) time complexity is needed.

(B) When more search operations are needed.

(C) When there are more insertions or deletions.

(D) When tree must be balanced.

Though both trees are balanced, when there are more insertions and deletions to make the tree balanced, AVL trees should have more rotations, it would be better to use red-black. but if more search is required AVL trees should be used.

Red Black Tree Insertion

Estimated Time

25 minutes

Introduction to rotations,insertions,deletions and search in red black trees

Welcome to this module on insertions in red black trees.! Take a look at what you will go through in this module.

  • Left and right rotations of trees.
  • Insertion of nodes in a red black tree.
  • Deletion of nodes in a red black tree.
  • Searching of nodes in a red black tree.
  • Interactive Exercise
  • A quiz to check your understanding of operations in red black trees

Rotation in Red Black Tree.

What is rotation in search trees ?

Tree rotation is an operation on a search tree that changes the structure without interfering with the order of the elements.

Why do we need to do rotations in Red Black Trees

The maximum height of the red black tree is O(log n). To Maintain this height, rotation operations is performed. Rotation alters the stucture of the tree by rearranging subtrees. There are two kinds of rotations performed.
  • Left Rotation
  • Right Rotation

Left Rotation Algorithm

Let the node to be rotated is x. Let the right subtree of node x be y.
  • Turn y's left subtree into x's right subtree.
  • Link the parent of x to y.
  • Put x as left subtree of y.
  • Set parent of x as y.

Right Rotation Algorithm

Let the node to be rotated is x. Let the left subtree of node x be y.
  • Turn y's right subtree into x's leftt subtree.
  • Link the parent of x to y.
  • Put x as right subtree of y.
  • Set parent of x as y.

Pictorial Representation of properties of a Left Rotation

Pictorial Representation of properties of Basic RBT

Pictorial Representation of properties of a Right Rotation

Pictorial Representation of properties of Basic RBT

Insertion in Red Black Tree.

Insertion Algorithm

Basics of Insertion algorithm video should be displayed here..!

Uncle and grandparent nodes in a red black tree

  • Let Z be the node being studied.
  • Uncle nodes refer to the sibling nodes of the parent node of Z.
  • Grandparent node refer to the parent node of the parent node of Z.

Pictorial Representation of uncle,parent and grandparent nodes in a red black tree

Pictorial Representation of properties of Basic RBT

Insertion Algorithm

Let Z be the node to be inserted.

  • Insert Node and color it red.
  • Recolor and rotate nodes to fix violations
There are 4 subcases to be handled to fix violations.
Case 1.Z is the root node.
  • Color the node as black.
Case 2.The uncle node of Z is red.
  • Recolor the parent and grandparent of Z to fix violations.
Case 3.The uncle node of Z is black and Z, parent node of Z and grandparent node of Z form a triangle.
  • Rotate parent of Z.
Case 4.The uncle node of Z is black and Z, parent node of Z and grandparent node of Z form a line.
  • Rotate the grandparent of Z and recolor the parent and grandparent of Z to fix violations.

Deletion

Deletion Algorithm

Basics of Deletion algorithm video should be displayed here..!

Recap of Deletion in a Binary Search Tree

In a Binary Search Tree, we end up deleting a node which is leaf or has one child.

The internal nodes are deleted by replacing it by its inorder successor.

Deletion in a Red Black Tree

Initially, we will delete a node just like we delete a node in a normal binary search tree. Here are the cases we will look at:
1) Red leaf node
2) Black node, with one red child node
3) Black leaf node

  • In fithe rst case, the normal binary search tree delete is sufficient. Removing a red node does not change the black depths of any node, nor create a red child for any red node.
  • In the second case, after we complete the binary search tree delete, we must simply recolor the child node of the deleted node to black. Changing this color adds one to the black depths of each node in the subtree of the deleted node, restoring the equality of the black depths of all external nodes. Also, changing a node to black does not violate any of the other Red-Black Tree specifications.
  • Neither of the strategies mentioned above are adequate for dealing with the third case. Instead, when we patch in the child of the deleted node in this case, in order to temporarily preserve the black depth property, we will color this child node a fictitious "double black" color.
  • Before we discuss how to deal with "double black" nodes, let's real quickly justify why the cases above are the only cases we will deal with. First off, we will only delete nodes with 0 or 1 child. Neither colored node can have one black child. If it did, the black height of the node's null child would not be proper. Further more, a red node can NOT have a red child. These observations narrow the cases to the situations listed above.
  • The remaining cases with this "double black" node can be categorized as follows:
  • 1) The sibling of the "double black" node is black and has a red child.
    2) The sibling of the "double black" node is black and both children are black.
    3) The sibling of the "double black" node is red.
    (Note that initially, even though the double black node is a null node, after starting the recoloring/restructuring process, we may create a double black node that is NOT null.)
  • To deal with each of these situations, let's first set up names for all of the important nodes:
  • 1) Let the child of the deleted node, which is colored "double black" be r.
    2) Let y be the sibling of r.
    3) Let z be a child of y, in each case, the specific child will be designated.
    4) Let x be the parent of y.
Case 1: y is black and has a red child z.
This case corresponds to the transfer operation in a 2-4 Tree delete. Take the nodes, x, y, and z and relabel them a, b, and c, in their inorder ordering. Place b where x used to be, and then have a and c be the left and right children of x, respectively. Color a and c black, and color b whatever color x USED to be. This eliminates the "double black" problem, so we can stop here.
Case 2: y is black and both of its children are as well.
This case corresponds to a fusion operation in a 2-4 Tree. We deal with this case by just recoloring, instead of making any structural changes to the tree. In particular, we will color r black, (changing it from "double black") and then color y red. What this does is subtract one from the black depth of every external node in the subtree of x. To compensate for this, we must change x from red to black. BUT, this only works if x was red to begin with!!! If it's not, to maintain the "black depth" at the external nodes in the subtree rooted at x, we must color x "double black." In essence, if this occurs, we have pushed the "double black" node up the tree, much like a fusion operation can propogate another fusion operation.

Searching in a Red Black Tree

Search in a Red Black Tree

Search in Red Black Tree is similar to search in Binary Search Tree. Let the node to be search be X.
  • If value of X is less than root node, we traverse recursively along the left subtree.
  • If the value of X is greater than the root node, we traverse recursively along the right subtree

Hands-on Demo on Red Black Tree

Hands-on Demo on Red Black Tree

Student is given a tree and starting node as the question.
Student needs to click the nodes of tree as they appear in DFT algorithm
Nodes follow a particular color scheme to differentiate between white,grey and black nodes.

Hands-on Practice on Red Black Tree

Hands-on Practice on Red Black Tree

Student is given a tree and starting node as the question.
Student needs to click the nodes of tree as they appear in DFT algorithm
Nodes follow a particular color scheme to differentiate between white,grey and black nodes.

Hands-on exercise on Red Black Tree

Hands-on exercise on Red Black Tree

Student is given a tree and starting node as the question.
Student needs to click the nodes of tree as they appear in DFT algorithm
Nodes follow a particular color scheme to differentiate between white,grey and black nodes.

Post Test Quiz of the Experiment

Q1. Time Complexity of insertion in Red Black Tree with n nodes is ______.

(A) None of the mentioned

(B) O(n)

(C) O(log n)

(D) O(1)

The rotation algorithm ensures the operation is done with O(log n) time complexity.

Q2. How do we impose restrictions?

  1. root property is black
  2. every leaf is black
  3. children of red node are black
  4. all leaves have same black

(A) Any one of the given three traversals is sufficient

(B) Either 2 or 3 is sufficient

(C) 1 and 3

(D) 2 and 3

All the operations ensure the the maximum height of the tree is log n. Hence all the operations take a logarithmic time complexity.

Post Test

Estimated Time

10 minutes

Introduction for Post test

Post test includes questions on entire experiment concepts. Read the questions given below and select the correct option from the ones provided. Please note that some questions may have more than one correct response.

Post Test Quiz of the Experiment

Q1. Time Complexity of insertion in Red Black Tree with n nodes is ______.

(A) None of the mentioned

(B) O(n)

(C) O(log n)

(D) O(1)

The rotation algorithm ensures the operation is done with O(log n) time complexity.

Q2. Breadth First Traversal of a tree can be used for ____________.

(A) Finding the shortest distance to every other node from the root in the tree.

(B) None of the Above.

(C) Finding strongly connected components in the tree.

(D) Finding cycles in the tree.

Breadth First traversal can be used to find the shortest distance to every other node from the root in the tree.

Q3. What is common in three different types of traversals (Inorder, Preorder and Postorder)?

(A) Root is visited before the right subtree.

(B) Left subtree is always visited before the right subtree.

(C) Root is visited after the left subtree.

(D) All of the above.

In all traversals mentioned in the question, left subtee is traversed before the right subtree.

Q4. A binary tree can be uniquely re-constructed from ____________.

(A) All of the above.

(B) Preorder and Postorder traversal.

(C) Inorder and Preorder traversal.

(D) Only Inorder traversal.

A binary tree can be uniquely reconstructed from its inorder and post order traversal.

Q5. The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g respectively. The postorder traversal of the binary tree is____________.

d e b f g a c

d e b f g c a

e d b g f c a

d e f g b c a

From the given preorder traversal, we know that the root of the tree is 'a'. Thus, 'a' must be the last element in the post order traversal. Now, after re-constructing the tree, we can easily find its post order traversal.

Further Readings and References of the Experiment

Explore Tree Traversal

You can explore more about tree traversal through following resources:

Theory

Practice

Quizzes