AVL tree

[femtotrader]

Hi,

Following JuliaFinance/MarketObservables.jl#12 (comment) I wonder what is current status of AVL tree Julia implementation.

Kind regards

PS : Github topic https://github.com/topics/avl-tree

#16

[femtotrader]

A quite old Julia implementation of AVL tree is available at https://github.com/torgausen/JuliaAVL
It's a 7 years old code which seems to have been forked recently https://github.com/wherrera10/JuliaAVL
I don't know what is current status of this fork. Is it currently usable? I'm wondering if tests are passing.
Maybe @wherrera10 can tell us.

[StephenVavasis]

Just to recap what I wrote in JuliaFinance/MarketObservables.jl#12: I do not expect that AVL trees would significantly outperform the 2-3 trees used in the sorted containers that already exists in DataStructures.jl. Rather, I expect that a significant performance boost would come from a good implementation of the cache-oblivious B-tree data structure by Bender, Demaine, and Farach-Colton.

[wherrera10]

I forked this for possible use in a simplified, less featured version, not to update it, sorry.

…

On Mon, May 20, 2019 at 3:34 AM femtotrader ***@***.***> wrote: A quite old Julia implementation of AVL tree is available at https://github.com/torgausen/JuliaAVL It's a 7 years old code which seems to have been forked recently https://github.com/wherrera10/JuliaAVL I don't know what is current status of this fork. Is it currently usable? Does tests are passing? Maybe @wherrera10 <https://github.com/wherrera10> can tell us. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#503?email_source=notifications&email_token=ACPOK7HYOR5T54VID3RJZLTPWKSFNA5CNFSM4HN5C4Z2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODVY25WI#issuecomment-493989593>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ACPOK7AIK22JK6WN3CP3DMLPWKSFNANCNFSM4HN5C4ZQ> .

[simonschoelly]

Is there a reason, why you would need an AVL tree instead of a RedBlack tree?

[femtotrader]

https://www.geeksforgeeks.org/red-black-tree-vs-avl-tree/

AVL trees provide faster lookups than Red Black Trees because they are more strictly balanced.

Fast lookup is an important property to have.

[anoojpatel]

Looks like this is implemented in (DataStructures.jl)[https://github.com/JuliaCollections/DataStructures.jl/blob/master/src/avl_tree.jl]. This issue should be closed, as it shows up first when searching for AVL Trees in Julia.

[p-casgrain]

Current implementation of AVLTree in DataStructures.jl appears to be the analogue of a SortedSet rather than a SortedDict. Precisely, the current definition of AVLTree{T} assumes that each node is keyed by an object of type T but contains no additional data, which is in contrast to the typical definition of an AVLTree. Of course, it is possible to wrap this implementation in such a way that the type T includes both a Key and Value, but this is inconvenient, particularly when the Value may be large. I propose AVLTree{T} is either (a) reimplemented as a Key-Value based data structure (i.e. as AVLTree{K,V}) or that (b) such a data structure is added and named AVLDict, for example.

There already exists a Julia implementation of the data structure described above at AVLTrees.jl, which we could potentially just integrate into DataStructures.jl

[femtotrader]

I did a quick benchmark (but I'm not a benchmark specialist) to compare both implementations.
https://github.com/femtotrader/AVLTreeBenchmarks.jl
AVLTrees.jl clearly wins on search operations