Jump to page content Jump to navigation

College Board

AP Central

AP Course Audit Web Site
Click for more information about College Board Online Events


Siemens Awards for Advanced Placement
Print Page
Home > AP Courses and Exams > Course Home Pages > Hash Table and Binary Search Tree Comparison

Hash Table and Binary Search Tree Comparison

by Rodney Hoffman
Occidental College
Los Angeles, California

More Nifty Assignments...

Assignment
Generate 100 random integers between 1 and 1000, inclusive. Build a binary search tree as you go, and at the same time, using the same numbers, build a hash table. Use a hash table of size 150 and hash function of (n % 150), and use linear probing to resolve collisions.

Now search both the binary search tree and the hash table 50 times each, looking for the numbers 20, 40, 60, 80, ..., 980, 1000. Collect statistics on your searches. For the binary search tree, count the number of nodes visited during each search. For the hash table, count the number of array positions examined during each search. At the end, for both data structures, report:
  • Smallest count among the 50 searches
  • Biggest count among the 50 searches
  • Average count among the 50 searches
  • Average count among successful searches
  • Average count among unsuccessful searches
  • Number of successful searches
Contribute
If you would like to contribute your suggestions for nifty assignments, please submit your ideas.


  MY AP CENTRAL
    Course and Email Newsletter Preferences
  AP COURSES AND EXAMS
    Course Home Pages
    Course Descriptions
    The Course Audit
    Sample Syllabi
    Teachers' Resources
    Exam Calendar and Fees
    Exam Questions
    AP Credit Policy Information
  PRE-AP
    Teachers' Corner
    Publications
  AP COMMUNITY
    About Electronic Discussion Groups
    Become an AP Exam Reader

Back to top