# Draft: util/addon: use AVL trees

Just a proof of concept which replaces linked lists with AVL trees. Might be useful if `wlr_addon_find()`

performance will ever end up being a bottleneck.

The implementation is largely based on the corresponding Wikipedia article.

- Lookup is now O(log n) instead of O(n)
- Insertion is now O(log n) instead of O(1)
- Deletion is now O(log n) instead of O(1)
- Set cleanup is now O(n log n) instead of O(n)
- Due to unnecessary rebalancing; this can probably be optimized

- None of this was benchmarked