by
PETER BRASS
City College of New York
City College of New York
Preface
This book is a graduate-level textbook on data structures. A data structure is
a method1 to realize a set of operations on some data. The classical example
is to keep track of a set of items, the items identified by key values, so that
we can insert and delete (key, item) pairs into the set and find the item with a
given key value. A structure supporting these operations is called a dictionary.
Dictionaries can be realized in many different ways, with different complexity
bounds and various additional operations supported, and indeed many kinds of
dictionaries have been proposed and analyzed in literature, and some will be
studied in this book.
In general, a data structure is a kind of higher-level instruction in a virtual
machine: when an algorithm needs to execute some operations many times, it
is reasonable to identify what exactly the needed operations are and how they
can be realized in the most efficient way. This is the basic question of data
structures: given a set of operations whose intended behavior is known, how
should we realize that behavior?
There is no lack of books carrying the words “data structures” in the title, but
they merely scratch the surface of the topic, providing only the trivial structures
stack and queue, and then some balanced search tree with a large amount of
handwaving. Data structures started receiving serious interest in the 1970s, and,
in the first half of the 1980s, almost every issue of the Communications of the
ACM contained a data structure paper. They were considered a central topic,
received their own classification in the Computing Subject Classification,
No comments:
Post a Comment