1 hour

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

- Basic knowledge of
- And above all, a curiosity to learn and explore..!

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

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.

10 minutes

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

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

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

15 minutes

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

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

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 Tree traversal video should be displayed here

Pictorial Representation of Basic RBT

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**

- 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**.

- 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 Basic RBT

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.

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.

25 minutes

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

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

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

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.

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 Basic RBT

Pictorial Representation of properties of Basic RBT

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

- 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 properties of Basic RBT

Let Z be the node to be inserted.

- Insert Node and color it red.
- Recolor and rotate nodes to fix violations

Case 1.Z is the root node.

- Color the node as black.

- Recolor the parent and grandparent of Z to fix violations.

- Rotate parent of Z.

- Rotate the grandparent of Z and recolor the parent and grandparent of Z to fix violations.

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

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.

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.
- 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) 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.)

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.

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.

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.

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

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.

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.

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.

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?

- root property is black
- every leaf is black
- children of red node are black
- 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

10 minutes

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.

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.

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.

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

You can explore more about tree traversal through following resources: