Efficient Self-Adjusting Search Trees via Lazy Updates

Alexander Slastin, Dan Alistarh, Vitaly Aksenov

Self-adjusting data structures are a classic approach to adapting the complexity of operations to the data access distribution. While several self-adjusting variants are known for…