Reading 06: Red-Black Trees, Treaps

Readings

The readings for Monday, October 3 are:

1. Data Structures and Other Objects Using C++:

   • 11.5

2. Red-Black Trees Handout

3. Open Data Structures

   • Random Binary Search Trees
   • Red-Black Trees

4. Treap (A Randomized Binary Search Tree)

5. Data Structure Visualizations

   • Red-Black Tree

Questions

Once you have completed the readings, answer the following questions in the reading06/README.md file in your assignments repository:

1. Red-Black Trees utilize rotation operations to keep the trees balanced. Explain what happens during a left rotation.

2. The nodes in Red-Black Trees are colored red and black. What three invariants must Red-Black trees maintain in regards to these markings.

3. Explain how Treaps are both binary search trees and binary heaps by describing what happens when a value gets inserted into the data structure.

4. For both Red-Black Trees and Treaps, identify the average and worst case time complexities in terms of Big O for the following set operations:

   1. Search

   2. Insert

   3. Remove

   If the average and worst case time complexities are different, then explain the reason for the difference.

Submission

To submit your solution, you must initiate a Merge Request in your private assignments repository and assign it to the appropriate TA from the Reading 06 - TA assignment list.

$ cd path/to/repo                 # Go to your repository
$ git checkout master             # Make sure we are on master branch first
$ git pull                        # Make sure we have changes from GitLab
$ git checkout -b reading06       # Create reading06 branch
...                               # Do your work
$ git commit                      # Commit your work (can do this multiple times)
$ git push -u origin reading06    # Push branch to GitLab