commons-dev mailing list archives

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


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.



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

DATE: Sat, 25 Oct 2003 11:48:38
From: "J.Pietschmann" <>
To: Jakarta Commons Developers List <>

>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
>Could you explain a bit more?
>To unsubscribe, e-mail:
>For additional commands, e-mail:

Enter for a chance to win one year's supply of allergy relief!;6413623;3807821;f?
This offer applies to U.S. Residents Only

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message