AVL self-balancing tree written in pure Julia.
Implemented on raw heap assigned storage with minimal overhead coming from balancing the tree itself. The tree node structure only has an additional Int8 keeping the balance factor. All balancing procedures are dynamically propagated (no height calculations during balancing).
An overview of performance is shown below (Julia 1.6.3). Times in nanoseconds. Average of 100 operations performed at tree size n using Int64 keys and data.
Row │ n insert delete search
│ Any Float64? Float64? Float64?
─────┼────────────────────────────────────────
1 │ 1000 18.0 19.0 0.182365
2 │ 10000 31.0 29.0 0.204204
3 │ 100000 52.0 46.0 0.222668
4 │ 1000000 74.0 68.0 0.247743
5 │ 10000000 111.0 99.0 0.25502
