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. Times are shown for an average of 1000 operations made at N elements in the structure.
| N | insert [us] | delete [us] | lookup [us] |
|---|---|---|---|
| 103 | 86.039 | 67.768 | 67.433 |
| 104 | 152.533 | 87.305 | 89.556 |
| 105 | 260.794 | 107.378 | 114.014 |
| 106 | 424.0 | 123.648 | 124.587 |
| 107 | 659.088 | 135.373 | 134.609 |
