I think splay trees would be good for this: https://en.m.wikipedia.org/wiki/Splay_tree