What do you mean by "self-adjusting" data structures? How are they different from other data structures? Where are they used?
Edit: Why would adjust a data structure if operations other than insert and delete are performed?
+8
A:
A self-adjusting data structure is a structure that can rearrange itself when operations are committed to it. Sometimes they rearrange themselves widely or minimally.
For example, AVL trees balance themselves every time a node is inserted or removed to ensure the tree, as a whole, is balanced and therefore guarantees a fast retrieval at the cost of insertion and deletion.
An example of a non-self-adjusting structure would be a naive binary tree, in which nodes stay where they were first inserted no matter what happens to the tree.
Addendum: Other structures adjust themselves based on reading, rather than inserting or deleting. These structures can be advanced and gather large amounts of statistics regarding access, or they can be more heuristic in nature. The goal of these structures is to make reading faster based on what was read in the past. A common example of such a structure is a cache, in which data that was accessed recently is accessible faster than data that hasn't been accessed yet.
Welbog
2009-05-20 01:10:00
Thanks. But why would a data structure need to adjust when operations other than insert or delete is performed?
kunjaan
2009-05-20 01:12:26
@kunjaan: it would depend on the structure. It's possible that a structure can keep records of how it is accessed, compute statistics based on that those records and rearrange itself to be accessed faster the most common ways it is accessed. A simple example would be caching, in which different data is stored in the cache depending on access rather than insertion or deletion.
Welbog
2009-05-20 01:14:24
Another (somewhat contrived) example might be a linked list where the number of times each node is located in a search is tracked and the list is reordered to move the most frequently searched for nodes towards the front of the list.
Lance Richardson
2009-05-20 03:08:07
@Lance: Thanks. That is also discussed in Eric's notes (link below)
kunjaan
2009-05-20 05:30:49
A:
I found a good lecture notes on these kinds of data structure. This is from Eric Demaine's Advanced Data Structure class at MIT: http://courses.csail.mit.edu/6.851/spring07/scribe/lec01_2.pdf
kunjaan
2009-05-20 02:31:55
A:
There is another meaning of "self-adjusting" in this context. You may have a data structure (a min-heap, say) which, given a set of input data, provides some output value such as the minimum element. It's common that you then want to make a small change in the input data, and update the heap to deliver the new minimum element. Ideally you'd like to do this in time proportional to the size of the change, rather than the total size of the heap.
Self-adjusting data structures support this type of "modify the input, recompute the output incrementally" behavior. See this recent paper from PLDI '10.
In some ways this is related to functional reactive programming, which shares the goal of efficient dependency tracking and incremental computation.
Rob Jellinghaus
2010-07-28 21:13:48