Specialized Data Structures

The basic data structures thus far described all represent an unstructured set of items so as to facilitate retrieval operations. These data structures are well known to most programmers. Not as well known are high-powered data structures for representing more structured or specialized kinds of objects, such as points in space, strings, and graphs.

The design principles of these data structures are the same as for basic objects. There exists a set of basic operations we need to perform repeatedly. We seek a data structure that supports these operations very efficiently. These efficient, specialized data structures are as important for efficient graph and geometric algorithms as lists and arrays are for basic algorithms, so one should be aware of their existence. Details appear throughout the catalog.

• String data structures - Character strings are typically represented by arrays of characters, with perhaps a special character to mark the end of the string. Suffix trees/arrays are special data structures that preprocess strings to make pattern matching operations faster. See Section for details.   
• Geometric data structures - Geometric data typically consists of collections of data points and regions. Regions in the plane are usually described by polygons, where the boundary of the polygon is given by a chain of line segments. Polygons can be represented using an array of points , such that is a segment of the boundary. Spatial data structures such as kd-trees organize points and regions by geometric location to support fast search. See Section for details.     
• Graph data structures - Graphs are typically represented by either adjacency matrices or adjacency lists. The choice of representation can have a substantial impact on the design of the resulting graph algorithms, as discussed in Chapter . Implementation aspects of graph data structures are presented in Section .  
• Set data structures - Subsets of items are typically represented using a dictionary, to support fast membership queries. A variety of data structures for manipulating sets is presented in Section .