Reading 05: Binary Search Trees, B-Trees

Readings

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

Alternative Readings

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

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

  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
$ git checkout -b reading05       # Create reading05 branch
...                               # Do your work
$ git commit                      # Commit your work (can do this multiple times)
$ git push -u origin reading05    # Push branch to GitLab