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" <[EMAIL PROTECTED]> To: Jakarta Commons Developers List <[EMAIL PROTECTED]> 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: [EMAIL PROTECTED] >For additional commands, e-mail: [EMAIL PROTECTED] > > ____________________________________________________________ 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: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
