Indirection is a technique used in data structures in which a problem is split into multiple levels of a data structure in order to improve efficiency. Typically, a problem of size n is split into n/\log n problems of size \log n. For example, this technique is used in
y-fast tries. This strategy also works to improve the insertion and deletion performance of the data structure described above to constant amortized time. In fact, this strategy works for any solution of the list-labeling problem with O(\log n) amortized insertion and deletion time. . The new data structure is completely rebuilt whenever it grows too large or too small. Let N be the number of elements of the total order when it was last rebuilt. The data structure is rebuilt whenever the invariant \tfrac{N}{3}\le n\le 2N is violated by an insertion or deletion. Since rebuilding can be done in linear time this does not affect the amortized performance of insertions and deletions. During the rebuilding operation, the N elements of the total order are split into O(N/\log N) contiguous sublists, each of size \Omega(\log N). The list labeling problem is solved on the set set of nodes representing each of the sublists in their original list order. The labels for this subproblem are taken to be polynomial --- say m=N^2, so that they can be compared in constant time and updated in amortized O(\log N) time. For each sublist a doubly-linked list of its elements is built storing with each element a pointer to its representative in the tree as well as a local integer label. The local integer labels are also taken from a range m = N^2, so that the can be compared in constant time, but because each local problem involves only \Theta(\log N) items, the labels range m is exponential in the number of items being labeled. Thus, they can be updated in O(1) amortized time. See the
list-labeling problem for details of both solutions.
Order Given the sublist nodes X and Y, order(X, Y) can be answered by first checking if the two nodes are in the same sublist. If so, their order can be determined by comparing their local labels. Otherwise the labels of their representatives in the first list-labeling problem are compared. These comparisons take constant time.
Insert Given a new sublist node for X and a pointer to the sublist node Y, insert(X, Y) inserts X immediately after Y in the sublist of Y, if there is room for X in the list, that is if the length of the list is no greater than 2\log N after the insertion. It's local label is given by the local list labeling algorithm for exponential labels. This case takes O(1) amortized time. If the local list overflows, it is split evenly into two lists of size \log N, and the items in each list are given new labels from their (independent) ranges. This creates a new sublist, which is inserted into the list of sublists, and the new sublist node is given a label in the list of sublists by the list-labeling algorithm. Finally X is inserted into the appropriate list. This sequence of operations take O(\log N) time, but there have been \Omega(\log N) insertions since the list was created or last split. Thus the amortized time per insertion is O(1).
Delete Given a sublist node X to be deleted, delete(X) simply removes X from its sublist in constant time. If this leaves the sublist empty, then we need to remove the representative of the list of sublists. Since at least \Omega(\log N) elements were deleted from the sublist since it was first built we can afford to spend the O(\log N) time, the amortized cost of a deletion is O(1). ==References==