Skip to content

Advanced Data Structures

ISBN-10: 0521880378

ISBN-13: 9780521880374

Edition: 2008

Authors: Peter Brass

List price: $99.99
Shipping box This item qualifies for FREE shipping.
Blue ribbon 30 day, 100% satisfaction guarantee!
Buy eBooks
what's this?
Rush Rewards U
Members Receive:
Carrot Coin icon
XP icon
You have reached 400 XP and carrot coins. That is the daily max!


Advanced Data Structures presents a comprehensive look at the ideas, analysis, and implementation details of data structures as a specialized topic in applied algorithms. This text examines efficient ways to realize query and update operations on sets of numbers, intervals, or strings by various data structures, including search trees, structures for sets of intervals or piece-wise constant functions, orthogonal range search structures, heaps, union-find structures, dynamization and persistence of structures, structures for strings, and hash tables. Instead of relegating data structures to trivial material used to illustrate object-oriented programming methodology, this is the first volume to show data structures as a crucial algorithmic topic. Numerous code examples in C and more than 500 references make Advanced Data Structures an indispensable text.
Customers also bought

Book details

List price: $99.99
Copyright year: 2008
Publisher: Cambridge University Press
Publication date: 9/8/2008
Binding: Hardcover
Pages: 474
Size: 6.25" wide x 9.25" long x 1.00" tall
Weight: 1.628

Pach is a distinguished researcher at NYU, his book "Combinatorial Geometry," 1995, Wiley, is considered "the bible" in the area of discrete geometry. He has also published several books with Springer-Verlag.William O.J. Moser is a Springer author as well. He has been awarded the CMS 2003 Distinguished Service Award for his sustained and significant contributions to the Canadian mathematical community.

Elementary Structures
Double-Ended Queue
Dynamical Allocation of Nodes
Shadow Copies of Array-Based Structures
Search Trees
Two Models of Search Trees
General Properties and Transformations
Height of a Search Tree
Basic Find, Insert, and Delete
Returning from Leaf to Root
Dealing with Nonunique Keys
Queries for the Keys in an Interval
Building Optimal Search Trees
Converting Trees into Lists
Removing a Tree
Balanced Search Trees
Height-Balanced Trees
Weight-Balanced Trees
(a, b)- and B-Trees
Red-Black Trees and Trees of Almost Optimal Height
Top-Down Rebalancing for Red-Black Trees
Trees with Constant Update Time at a Known Location
Finger Trees and Level Linking
Trees with Partial Rebuilding: Amortized Analysis
Splay Trees: Adaptive Data Structures
Skip Lists: Randomized Data Structures
Joining and Splitting Balanced Search Trees
Tree Structures for Sets of Intervals
Interval Trees
Segment Trees
Trees for the Union of Intervals
Trees for Sums of Weighted Intervals
Trees for Interval-Restricted Maximum Sum Queries
Orthogonal Range Trees
Higher-Dimensional Segment Trees
Other Systems of Building Blocks
Range-Counting and the Semigroup Model
kd-Trees and Related Structures
Balanced Search Trees as Heaps
Array-Based Heaps
Heap-Ordered Trees and Half-Ordered Trees
Leftist Heaps
Skew Heaps
Binomial Heaps
Changing Keys in Heaps
Fibonacci Heaps
Heaps of Optimal Complexity
Double-Ended Heap Structures and Multidimensional Heaps
Heap-Related Structures with Constant-Time Updates
Union-Find and Related Structures
Union-Find: Merging Classes of a Partition
Union-Find with Copies and Dynamic Segment Trees
List Splitting
Problems on Root-Directed Trees
Maintaining a Linear Order
Data Structure Transformations
Making Structures Dynamic
Making Structures Persistent
Data Structures for Strings
Tries and Compressed Tries
Dictionaries Allowing Errors in Queries
Suffix Trees
Suffix Arrays
Hash Tables
Basic Hash Tables and Collision Resolution
Universal Families of Hash Functions
Perfect Hash Functions
Hash Trees
Extendible Hashing
Membership Testers and Bloom Filters
The Pointer Machine and Alternative Computation Models
External Memory Models and Cache-Oblivious Algorithms
Naming of Data Structures
Solving Linear Recurrences
Very Slowly Growing Functions
Author Index
Subject Index