The readings for Monday, September 26 are:

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

• 12.1, 10.3 - 10.5, 11.3
2. Data Structure Visualizations

#### TL;DR

The focus of the reading is binary search trees and B-Trees.

### Alternative

If you do not have the primary textbook, you can use the following free alternative texts instead:

1. Data Structures & Algorithm Analysis

• 5.4 Binary Search Trees

• 10.5 B-Trees

2. Open Data Structures

Unfortunately, the alternative texts do a poor job of covering B-Trees. You may wish to try to borrow a copy of the primary textbook for that information.

## Questions

1. What is the difference between a binary heap and a binary search tree? Can a binary tree consisting of at least two nodes be both a binary heap and a binary search tree? Explain.

2. A binary search tree is considered an ordered or sorted binary tree. Given a binary search tree, explain how you would print out all of the values in the binary tree in sorted order. What is the complexity of this process in terms of Big O?

3. A binary search trees is often used to implement the set and map abstract data types. Identify the average and worst case time complexities in terms of Big O for the following set operations:

1. Search

2. Insert

3. Remove

Why are the average and worst case time complexities different?

4. B-Trees are often used in databases such as CouchDB, SQL Server, MongoDB, and SQLite. Explain how B-Tree is different from a binary search tree and how these differences make it an attractive data structure for implement large data storage systems.

## 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 05 - TA assignment list.

#### Development Branch

To facility the Merge Request workflow, you must do your development in its own branch:

\$ 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