数据结构dsch09 engNEW c++.pptVIP

Search Basics Important Terms Record: the set of information that consists of an element to be put in the structure Key: The element of a record that we will search on Keys must be totally ordered Each key must be unique Example: Each record might consist of all the information for a given employ The key for each record would be the SSN Note: For our purposes, only the key matters Search table Definition: A search table is a set made from data of same type Operations on search table: Query of specified data element Retrieval of properties of specified data element Insert a element to table Delete a element in table Static search table(there are only first two operations above) Dynamic search table(all of operations above) Static Search table template class Type class Node { friend class dataListType; public： Node ( const Type value ) ： key ( value ) { } Type getKey ( ) const { return key; } void setKey ( Type k ) { key = k; } private： Type key; …; }; Static Search table template class Type class Node { friend class dataListType; public： Node ( const Type value ) ： key ( value ) { } Type getKey ( ) const { return key; } void setKey ( Type k ) { key = k; } private： Type key; …; }; Sequential search table Efficiency Analysis Efficiency ASL = log2n - 1 Index table search Efficiency Binary Search Trees Binary Search Tree Search tree property all keys in left subtree smaller than root’s key all keys in right subtree larger than root’s key result: easy to find any given key inserts/deletes by changing links Example and Counter-Example A Binary Search Tree of States The data in the dictionary will be stored in a binary tree, with each node containing an item and a key. A Binary Search Tree of States Storage rules: Every key to the left of a node is alphabetically before the key of the node. A Binary Search Tree of States Storage rules: Every key to the left of a node is alphabetically before the key of the node. A