Things are a’changing

It’s always fun to come across some new data structures. When I studied computer science at the start of the 1990s, we had a lecture course that covered the standard data structures, but since those days there has been a lot more investigation of immutable data structures and also data structures that are more friendly to modern processor architectures.

The first data structure that I’ve recently come across is a suffix tree. Such trees can be constructed efficiently (in time linear in the size of the string), and can be used to answer questions such as whether the string contains a particular substring, and the longest common substring between two strings. This wikipedia article is very good at listing the uses and the following post explains the algorithm well, including a JavaScript implementation (if you view the page source). The following linked paper explains the links between the three historical algorithms for implementing such trees.

The second data structure is the Skip List, a data structure based on the binary tree but which uses a probabilistic balancing to avoid the complicated balancing algorithms that you find within the standard tree data structures. This post explains the details well.

Advertisements
This entry was posted in Computers and Internet. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s