Consider a "dictionary" containing N items, where we support insert, delete, search-for, read-access, replace (write-access) in O(L) steps each, where L=logN. This is implementable using "balanced binary trees" such as "red black trees" or "Aa trees" which employ 2 pointers plus some small number (e.g. 1) of bits per data item. Also it can be done using "splay trees" using 2 pointers per item, and no extra bits needed, but speed guarantees now only amortized, not worst case (long pauses occasionally possible). If data items are same size as a pointer, this is a major WASTE OF MEMORY: 3X more consumed than the data itself. --------------- I now point out (which may or may not be a new observation -- I'd guess probably not new?) that there is a way to do this with far less memory wasted, and probably more efficient at the same time. (The reason for alleged "greater efficiency" is because of memory caching effects and the existence of special instructions on many processors for high speed shifts of arrays.) Let K>1 be a constant (or it could even grow slowly with N). Make each node of the tree contain not one, but rather an array of order L items consecutive in the ordering. Each node's array size is fixed, but the array may be only partly filled, knows how many items it contains. We agree that each node's array will always be within fraction 1/K of being full. To search for an item X, walk to right child if X>max array element, to left child if X<min, and binary search within the array, otherwise. To insert a new item, just do a linear insert into the array, if it is not already full; ditto for delete if contains enough items (occupancy count changed by +- 1). If it is desired to insert an item into an already-full node (or delete one from a node which has its minimum allowed occupancy; I'll focus here on insert), then we look for other nodes adjacent to this one in the ordering. We find the J closest nodes where J=1,2,...,K until finding one that is not full. Then we redistribute the array items within these J nodes to equalize their occupancy counts to within 1 and insert the new item. This all takes J times longer than a single search. If on the other hand all J=K of these nodes have full arrays, then we create a new node, redistribute items among the K+1 nodes' arrays, and insert the new item into the correct node's array, and finally, using standard balanced tree (or splay tree) methods, insert the new node into the tree. CONCLUSION: Search & access requires O(L) steps, L=logN. Insert takes O(L) steps usually, occasionally O(J*L) steps with 1<J<K, and even more rarely O(K*L) steps. Ditto delete. Here K is an arbitrary constant. If desired, we can guarantee the rareness of the longer-time kind of steps by adding "hysteresis" to the data structure, i.e. it is ok to delete until a node's array has fraction 2/K unfilled, but any multi-node redistribution is arranged to assure at most 1/K fraction unfilled. In that case, the longer-time steps can occur only a fraction K/L of the time at most, so the AMORTIZED-average time per operation is assured to be O((K/L)*K*L + L) = O(K*K+L). So we can choose K to be anywhere between 1 and sqrt(logN) while still assuring the amortized operation time is O(logN), and worst case operation time (using balanced trees) is O(logN)^2. With splay trees the worst case time could be as large as order N/L. In this case, the "waste" of memory is: 2 pointers and a few bits per K data items, which (provided K grows with N to infinity such as sqrt(logN)) asymptotically tends to ZERO waste of memory. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)