Re: [Caml-list] Why AVL-tree?

[Jonathan <jonikelee@gmail.com>]

On 06/15/2014 12:51 AM, Lukasz Stafiniak wrote:
> Here is a 2-imbalance AVL trees example from InvarGenT:
> https://github.com/lukstafi/invargent/blob/master/examples/avl_tree.gadt
> and the (inferred) types:
> https://github.com/lukstafi/invargent/blob/master/examples/avl_tree.gadti.target
>
> Regards,
> Lukasz

Thank you for those links, Lukasz.  I see from them that there is a 
difference between 2-imbalance AVL trees and gap trees.  In 2-imbalance 
AVL trees, as with standard AVL trees, the parent height is always 1 + 
the maximum child height.  In gap trees, a parent's height can in some 
cases be 2 above the height of both children, even though the childrens' 
heights never differ by more than 1.

I am wondering how important this difference is.  For example, with gap 
trees, there is at most one rebalancing needed per insertion or deletion 
operation.  My understanding of standard AVL trees is that they may 
require O(logN) rebalancings per insertion or deletion.  Do you know how 
the 2-imbalance property addition changes this rebalancing requirement 
for AVL trees?

Thanks again,
Jonathan

>
> On Tue, Jun 10, 2014 at 11:19 AM, <jonikelee@gmail.com> wrote:
>
>> I am coming here from the Coq mailing list, because of a link posted there
>> about this e-mail thread.  I have been working on Coq-verified and fully
>> proof-erased versions of AVL and red-black trees, as well as a variant I
>> didn't know existed before, until I read about "2-imbalance AVL trees" in
>> this
>> thread.
>>
>> The github address for my development is:
>>
>> https://github.com/jonleivent/mindless-coding
>>
>> and the "gaptree" development there may be the same as your "2-imbalance"
>> AVL
>> trees, though I can't be sure without more of an explanation (or maybe
>> just a
>> pointer to the source code) for the 2-imbalance AVL trees.
>>
>> Any further information or source pointers you can give me would be greatly
>> appreciated.
>>
>> Thanks
>> --Jonathan
>>
>> --
>> Caml-list mailing list.  Subscription management and archives:
>> https://sympa.inria.fr/sympa/arc/caml-list
>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs
>>