AVLTrees

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).

Benchmark

An overview of performance is shown below. Times are shown for an average of 1000 operations made at N elements in the structure.

Table

Row │ n         insert[us]   delete[us]    search[us]
     │ Any       Float64?     Float64?      Float64?  
─────┼────────────────────────────────────────────────
   1 │ 1000          152.67        32.02    0.00222892
   2 │ 10000         174.1         63.86    0.00227912
   3 │ 100000        299.6        165.86    0.00235597
   4 │ 1000000       629.11       524.92    0.00304124
   5 │ 10000000      964.76       912.39    0.025

Plot