CSC1120 Homework 14

Objective

Develop a strong understanding of Red-Black Tree invariants, and practice identifying and correcting violations using rotations and recoloring. This assignment emphasizes reasoning and step-by-step correctness over large implementations.

Background

A valid Red-Black Tree satisfies:

1. Every node is either red (R) or black (B)
2. The root is black
3. A red node cannot have a red child
4. Every path from a node to a null leaf has the same black-height
5. The tree maintains BST ordering

Part 1: Invariant Check

For each tree below:

• State whether it is valid or invalid
• If invalid, list the violated invariant(s)
• Give a 1--2 sentence explanation

Tree A

        10B
       /   \
     5R     15B
    /
  2R

Tree B

        20R
       /   \
     10B   30B

Tree C

        25B
       /   \
     10B   40B
    /         \
   5R         50R

Tree D

        15B
       /   \
     10R   20R
    /   \
   5B   12B
        /
      11R

Part 2: Rotation Identification

For each structure:

1. Identify the case (LL, LR, RL, RR)
2. State the required rotation(s)
3. Draw the resulting tree after the fix

Case 1

      30B
     /
   20R
  /
10R

Case 2

      30B
     /
   10R
     \
     20R

Case 3

      10B
        \
        30R
       /
     20R

Part 3: Insert-and-Fix Trace

Given the initial tree:

        20B
       /   \
     10B   30B

Insert the following values in order:

5, 1, 15

For each insertion:

1. Insert using standard BST rules
2. Color the new node red
3. Identify any violations
4. Apply recoloring and/or rotations
5. Draw the tree after each fix

Show all intermediate steps clearly.

Part 4: Coding Task

Implement the following method:

boolean isValidRedBlackTree(RedBlackNode root)

Your implementation should verify:

• The root is black
• No red node has a red child
• The tree satisfies BST ordering
• All root-to-leaf paths have the same black-height

Focus on clarity, correctness, and clean structure.

Submission Requirements

• Clearly drawn trees (handwritten or digital)
• Brief explanations for Part 1
• Labeled rotations for Part 2
• Step-by-step trace for Part 3
• Code for Part 4

Goal

By completing this assignment, you should be comfortable:

• Recognizing Red-Black Tree violations
• Classifying rotation cases
• Applying fixes step-by-step without relying on full implementations