commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Bryce Alcock" <bear4...@lycos.com>
Subject Re: [Math] [collections] order-statistics tree (augmented red-black)
Date Tue, 28 Oct 2003 13:42:19 GMT

Sure,

Determining something like 90% or 75% (order-statics) is
O(n) time for n elements using most algorithms, however
there is a technique of augmenting a red-black tree with the element's RANK (its global order)
by doing this augmentation, and keeping track of the tree size, you can reduce the cost of
order-statistics to O(lg n) time.

Also, it requires a modification to both the insert and delete functions of the Red-Black
tree, because any rotate-right or rotate-left functions must "Repair the Augmented Data during
the rotation".

While I am not completely able to do this technique justice, there is a very good chapter
(Chapter 14 of Corman, Leiserson, Rivest, and Stein) that discuss this augmentation technique.
 

Maybe someone knows how to get an online copy of this chapter or a similar discussion.

I Hope this Clarifys first email.

Bryce
 



--

--------- Original Message ---------

DATE: Sat, 25 Oct 2003 11:48:38
From: "J.Pietschmann" <j3322ptm@yahoo.de>
To: Jakarta Commons Developers List <commons-dev@jakarta.apache.org>
Cc: 

>Bryce Alcock wrote:
>> I would like an order - statistics tree,
>> Which behaves with the same running times
>> as a standard red-black binary search
>> tree.
>...
>> 1. Are there any plans to do something like
>> this in either the Math, or Collections 
>> sections of Commons?
>
>I don't think so.
>
>I'm not quite familar with the term "statistics tree". If
>it's a modification to rbtrees which optimizes for a
>predetermined ad-hoc statistic for modification or read
>access it should probably go into the collections module.
>If the statistic is calculated on the fly from the access,
>then, well, it should probably also go into the collections
>module.
>
>Could you explain a bit more?
>
>J.Pietschmann
>
>
>
>---------------------------------------------------------------------
>To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
>For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
>



____________________________________________________________
Enter for a chance to win one year's supply of allergy relief!
http://ad.doubleclick.net/clk;6413623;3807821;f?http://mocda3.com/1/c/563632/125699/307982/307982
This offer applies to U.S. Residents Only

---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message