[Current] [News] [Glance] [Search] [Instructions] [Links] [Handouts] [Project] [Outlines] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [EIJ] [API]
Back to Dictionaries. On to Hash Tables.
Held Tuesday, November 28, 2000
Summary
Today we consider one interesting implementation of dictionaries: search trees. As the name suggests, search trees are trees that are designed to help you search for elements.
Notes
Overview
D / \ B F / \ / \ A C E G
Rebelsky / \ Ferguson Walker / \ / \ Chamberland Herman Stone Wolf / / \ Adelberg Flynt Jepsen / \ Hill MooreE \ MooreT
Dictionary
with binary search
trees, we'll build a wrapper class. This class will permit us to
Comparator
used to determine
large and small.
public interface BinarySearchable { /** * Get the ``middle'' key in the collection. * Pre: The collection is nonempty. * Post: Returns some designated element in the collection. */ public Object middle(); /** * Get elements in the collection that are smaller than the * middle element. * Pre: The collection is nonempty. * Pre: The collection has not been modified since the last call * to middle. * Post: Returns the smaller elements. */ public BinarySearchable smaller(); /** * Get elements in the collection that are larger than the * middle element. * Pre: The collection is nonempty. * Pre: The collection has not been modified since the last call * to middle. * Post: Returns the larger elements. */ public BinarySearchable larger(); /** * Determine if the collection is empty. */ public boolean isEmpty(); } // BinarySearchable
public boolean binarySearch(BinarySearchable stuff, Object findMe, Comparator order) { if (stuff.isEmpty()) return false; int compareVal = order.compare(findMe, stuff.middle()); if (compareVal == 0) return true; else if (compareVal < 0) return binarySearch(stuff.smaller(), findMe, compare); else ; if (compareVal > 0) return binarySearch(stuff.larger(), findMe, compare); } // binarySearch(BinarySearchable, Object, Comparator)
Wednesday, 23 August 2000
Thursday, 24 August 2000
Tuesday, 28 November 2000
Back to Dictionaries. On to Hash Tables.
[Current] [News] [Glance] [Search] [Instructions] [Links] [Handouts] [Project] [Outlines] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [EIJ] [API]
Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.
This page may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2000F/Outlines/outline.50.html
Source text last modified Tue Nov 28 09:20:06 2000.
This page generated on Tue Nov 28 09:43:29 2000 by Siteweaver. Validate this page's HTML.
Contact our webmaster at rebelsky@grinnell.edu