Splay trees
Splay trees are a specific type of binary search tree in which there is an operation called splaying, which grants the tree the ability to quickly access recently visited nodes.
The splay operation puts the last accessed node as the new root of the tree. Recently visited nodes always have a minimum height, therefore they are easy and quick to access again. We can say that splay trees optimize themselves by performing a mix of searches and tree rotations.
The average height is O(log(n)) and the worst (and most unlikely) scenario is O(n). The amortized time of each operation on a n-node tree is O(log(n)). The amortized time analysis is used when we don't always expect the worst scenario so we can consider different scenarios (not just the worst) in the overall time complexity of the algorithm.
Two common uses of splay trees are caches and garbage collections. In both cases, we get the benefits of quick access to recently visited nodes, so this particular implementation of the binary...
