Held: Monday, 18 November 2013

Back to Outline 41 - Implementing Dictionaries with Arrays or Lists. On to Outline 43 - Detour: The Digital Commons.

Summary

We consider binary search trees, a somewhat more efficient implementation of dictionaries.

Related Pages

• Lab: Binary Search Trees
• Code: https://github.com/Grinnell-CSCS207/bst
• EBoard (HTML) (PDF)

Overview

• About binary search trees.

Administrivia

• Reminder: Tomorrow we're going to the Digital Commons roundtable, Burling First Floor Lounge.
• Homework cancelled.
• Exam ready in draft form. We'll do a quick overview.
• Upcoming extra credit opportunities:
  • Digital Commons talk, Tonight, 7:30 p.m., JRC 101
  • CS Department Talk, Wednesday, November 20, noon, Unknown topic
  • CS Table Friday, Unknown topic
  • Typhoon Halyan Relief benefit show, Sunday, November 24th from 7-9pm in Harris. (If the entry fee is a burden, let me know and I'll give you the money.)
  • "Data Sovereignty: The Challenge of Geolocating Data in the Cloud", November 25, 4:15 JRC 101
  • "Gold Fever" by Andrew Sherburne '01 or so, 7:00 p.m., Monday, November 25, ARH 302
  • Tuesday, November 26, 4:15 p.m., JRC 209 a gaming event with the game [d0x3d!]

About binary search trees

• Linked structures.
• Two links from every node. One to the "smaller" values, one to the "larger" values.
• When used to implement ditionaries, store a key/value pair in each node.
• Note: While association lists only require that we be able to compare value for equality, binary search trees require that we have a way to order values.