Re: Fast arrays

From: Paul E. Black (p.black_at_acm.org)
Date: 01/13/05 

Date: Thu, 13 Jan 2005 13:41:46 -0500

On Wed, 12 Jan 2005 21:15:30 -0500, Rick Decker wrote:

> Paul E. Black wrote:
>> On Wed, 12 Jan 2005 12:34:08 -0500, Rick Decker wrote:
>>
>>>Przemyslaw Wesolek wrote:
>>>
>>>>Looking for "arrays" (i.e. structures with indexed access) which have
>>>>time complexity O(log n) for insertions and deletions, I found the
>>>>page:
>>>>
>>>> http://caladan.nanosoft.ca/fastarray.php
>>>>
>>>>The author describes tree data structure, which has this property.
>>>>Knuth name is mentioned as a person, who could describe something
>>>>similar. Unfortunatelly, I couldn't find any other references to Knuth
>>>>regarding this structure.
>>>
>>>... it looks as if the
>>>author has rediscovered a structure covered in section 6.2.3, "Balanced
>>>Trees," in volume 3 (_Sorting and Searching_) of Knuth.
>>
>> True, Knuth describes tree balancing, but the author applied a balanced
>> tree to implement an array ADT with time complexity Theta(log n) for
>> insertions and deletions (and lookup).
>
> Which seems to be a lot like what Knuth's doing in the subsection "Linear
> list representation" and the one that follows. Look at Fig. 24. (Well,
> it's Fig.24 in my 1973 edition--it's the one titled "RANK fields, used for
> searching by position.")

Rick,

I concur, thanks for pointing that out. I didn't notice it.
Algorithm C appears to be essentially the same as Elaan's. (Maybe
someone should tell her.)

By the way, it is Fig. 24 in my 1998 edition, too (page 471).

-paul- 

-- 
Paul E. Black (p.black@acm.org)