What are Self-Adjusting Data Structures?

Question

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?

Answer 1

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.