"Eric Mahurin" <eric.mahurin / gmail.com> wrote in message 
news:29256ea00709070604p65b34a6ex8cf147e8844e74cd / mail.gmail.com...
> On 9/7/07, Eugene Kalenkovich <rubify / softover.com> wrote:
>> "John Miller" <jfmiller28 / yahoo.com> wrote in message
>> news:bc100c94508cad46e34a0d22e95334f8 / ruby-forum.com...
>> > Hi All,
>> >
>> > This was the other interesting part of the quiz.  Every answer I saw
>> > balanced the tree giving each leaf the same weight.  The leaves on the
>> > other hand varied in length between 8 characters and 512k.  The
>> > suggested way to balance a Rope was based on the length of the leaves 
>> > in
>> > such a way that longer leaves were nearer the root because presumably
>> > they will be accessed more often.
>> >
>>
>> At least two implementations did this (James Koppel's and mine). OTOH 
>> this
>> added a lot of mess to the code, and a simple change on e.g. Eric's
>> implementation (to use length instead of depth) will achieve practically 
>> the
>> same.
>>
>> --EK
>
> I'd think you'd treat depth as log2(length) and do something similar.
> Instead of this for concatenation:
>
> balance = other.depth-@depth
> if balance>+1
>   ...
> elsif balance<-1
>   ...
>
> You could do something like this (using depth=log2(length) and a little 
> math):
>
> if other.length>2*@length
>   ...
> elsif @length>2*other.length
>   ...


In reality all in-time short-cut  rebalancings will perform worse than the 
full one. For now I do not see any algorithm better than in original 
article, though it  is also not ideal (but good on memory usage)

>
> On the other hand, I don't know that it is a good assumption that
> you'll be accessing longer leaves more often than shorter leaves.
> This assumes random access of the elements in the rope.  For example,
> if you are using a rope for a text editor buffer, there will be a
> you'll only be accessing a small part of the rope you'll be accessing
> while typing stuff in.  And at that point, you'll probably be dealing
> with short leaves since things are changing around where you are
> editing.  You may want the most recently used closer to the root of
> the tree.
>

Everything is about probability of access to particular symbol. You can 
optimize for particular scenario (in this one - you do not want any 
rebalancing at all),  but these optimizations will behave miserably in any 
other cases

--EK