Redundant binary counters were studied by Clancy and
Knuth in 1977 and led to the discovery of finger search trees.
These counters reappear recently in several new data structures.
In particular we use them to design purely functional catenable
double-ended queues that have O(1) worst-case time bound
for each operation, purely functional finger search trees,
and priority queues.
In this talk I will describe these counters and some of the
data structures in which we use them.
(This is joint work with Bob Tarjan.)