Red-Black Tree

Preview

1. What is the main purpose of using a Red-Black Tree data structure?
2. What are the characteristics of a Red-Black Tree in terms of balancing and height?
3. How is a Red-Black Tree different from a Binary Search Tree?
4. What is the time complexity for inserting, deleting, and searching in a Red-Black Tree?
5. How is the color of a node in a Red-Black Tree determined and maintained during insertion and deletion?

Explain

Red-Black Tree is a self-balancing Binary Search Tree in which each node has one additional color attribute, either red or black, to ensure that the tree is balanced over time. The balance is achieved by applying specific rules during the insertion and deletion operations that ensure that the height of the tree remains logarithmic, O(log n), where n is the number of elements in the tree.

The main properties of Red-Black Tree are:

1. Every node is either red or black.
2. The root is always black.
3. Every leaf (NULL) is black.
4. If a node is red, then both its children are black.
5. Every simple path from a node to a descendant leaf contains the same number of black nodes.

An example of a Red-Black Tree:

Let’s say we want to insert the following elements in a Red-Black Tree: 30, 40, 50, 20, 60, 70, 10, 25.

1. We start by creating a new node for 30 and color it black since it is the root of the tree.
   30(B)

2. Insert 40 as its right child and color it red.
   30(B)
   
   40(R)

3. Insert 50 as the right child of 40 and color it black.
   30(B)
   
   40(B)
   
   50(R)

4. Insert 20 as the left child of 30 and color it black.
   30(B)
   /
   20(B) 40(B)
   
   50(R)

5. Insert 60 and color it red as the right child of 50. Then, apply a Left Rotation on node 40 to fix the violation of the Black Height property.
   30(B)
   /
   20(B) 50(B)
   /
   40(R) 60(R)

6. Insert 70 as the right child of 60 and color it black.
   50(B)
   /
   30(R) 60(B)
   / \
   20(B) 40(B) 70(R)

7. Insert 10 as the left child of 20 and color it red. Then, apply a Right Rotation on node 30 and a Left Rotation on node 50 to fix the double violation of the Red-Black Tree properties.
   50(B)
   /
   30(R) 60(B)
   / \
   20(B) 40(B) 70(R)
   /
   10(R)

Keypoint

1. A red-black tree is a balanced binary search tree.
2. It has the same performance characteristics as AVL tree.
3. Each node has a color attribute of either red or black.
4. The root node is always black.
5. All leaves are null and black.
6. If a node is red, then both its children are black.
7. Every path from a given node to any of its descendant null leaves contains the same number of black nodes.
8. Insertion and deletion operations maintain the necessary properties of a red-black tree.
9. The worst-case time complexity for search, insertion, and deletion is O(log n) in a red-black tree.
10. Red-black tree is used in many data structures such as TreeMap, TreeSet, etc.

Review

1. What is a Red-Black Tree?
   Answer: A Red-Black Tree is a self-balancing binary search tree with each node colored either red or black, ensuring that the tree is height-balanced and closely resembles a balanced tree.

2. What is the maximum height of a Red-Black Tree with N nodes?
   Answer: The maximum height of a Red-Black Tree with N nodes is 2*log(N+1).

3. How are nodes colored in a Red-Black Tree?
   Answer: Nodes in a Red-Black Tree are colored either red or black, with the color chosen based on certain conditions: the root is always black, all leaves are black, and if a node is red, then both its children must be black.

4. What are the operations that can be performed on a Red-Black Tree?
   Answer: The operations that can be performed on a Red-Black Tree include insertion, deletion, searching, traversal, and rotation.

5. How does rotation help balance a Red-Black Tree?
   Answer: Rotation helps balance a Red-Black Tree by re-positioning nodes to maintain the red-black property while preventing the height of the tree from exceeding log(N) with N nodes. Rotation can be performed in two ways: left-rotation and right-rotation.